Mathematics

Research

8 pages, 272 KiB

Open AccessArticle

Bi-Squashing S_2,2-Designs into (K₄ − e)-Designs

by Giovanni Lo Faro and Antoinette Tripodi

Mathematics 2024, 12(12), 1879; https://doi.org/10.3390/math12121879 - 17 Jun 2024

Viewed by 659

Abstract

A double-star

S_{q_{1}, q_{2}}

is the graph consisting of the union of two stars,

K_{1, q_{1}}

and

K_{1, q_{2}}

, together with an edge joining their centers. The spectrum for [...] Read more.

A double-star

S_{q_{1}, q_{2}}

is the graph consisting of the union of two stars,

K_{1, q_{1}}

and

K_{1, q_{2}}

, together with an edge joining their centers. The spectrum for

S_{q_{1}, q_{2}}

-designs, i.e., the set of all the

n \in N

such that an

S_{q_{1}, q_{2}}

-design of the order n exists, is well-known when

q_{1} = q_{2} = 2

. In this article,

S_{2, 2}

-designs satisfying additional properties are investigated. We determine the spectrum for

S_{2, 2}

-designs that can be transformed into

(K_{4} - e)

-designs by a double squash (bi-squash) passing through middle designs whose blocks are copies of a bull (the graph consisting of a triangle and two pendant edges). Here, the use of the difference method enables obtaining cyclic decompositions and determining the spectrum for cyclic

S_{2, 2}

-designs that can be purely bi-squashed into cyclic

(K_{4} - e)

-designs (the middle bull designs are also cyclic). Full article

(This article belongs to the Special Issue Advanced Graph Theory and Combinatorics)

► Show Figures

Figure 1

31 pages, 3625 KiB

Open AccessArticle

Edge Odd Graceful Labeling in Some Wheel-Related Graphs

by Mohammed Aljohani and Salama Nagy Daoud

Mathematics 2024, 12(8), 1203; https://doi.org/10.3390/math12081203 - 17 Apr 2024

Cited by 1 | Viewed by 1246

Abstract

A graph’s edge labeling involves the allocation of symbols (colors or numbers) to the edges of a graph governed by specific criteria. Such labeling of a graph G with order n and size m is named edge odd graceful if there is a [...] Read more.

A graph’s edge labeling involves the allocation of symbols (colors or numbers) to the edges of a graph governed by specific criteria. Such labeling of a graph G with order n and size m is named edge odd graceful if there is a bijective map

φ

from the set of edges

E (G) = {e_{1}, \dots, e_{m}}

to the set

{1, 3, \dots, 2 m - 1}

in a way that the derived transformation

φ^{*}

from the vertex-set

V (G) = {v_{1}, \dots, v_{n}}

to the set

{0, 1, 2, \dots, 2 m - 1}

given by

φ^{*} (u) = \sum_{u v \in E (G)} φ (u v) mod (2 m)

is injective. Any graph is named edge odd graceful if it permits an edge odd graceful allocation (Solairaju and Chithra). The primary aim of this study is to define and explore the edge odd graceful labeling of five new families of wheel-related graphs. Consequently, necessary and sufficient conditions for these families to be edge odd graceful are provided. Full article

(This article belongs to the Special Issue Advanced Graph Theory and Combinatorics)

► Show Figures

Figure 1

13 pages, 372 KiB

Open AccessArticle

Conditions for Implicit-Degree Sum for Spanning Trees with Few Leaves in K_1,4-Free Graphs

by Junqing Cai, Cheng-Kuan Lin, Qiang Sun and Panpan Wang

Mathematics 2023, 11(24), 4981; https://doi.org/10.3390/math11244981 - 17 Dec 2023

Cited by 1 | Viewed by 958

Abstract

A graph with n vertices is called an n-graph. A spanning tree with at most k leaves is referred to as a spanning k-ended tree. Spanning k-ended trees are important in various fields such as network design, graph theory, and [...] Read more.

A graph with n vertices is called an n-graph. A spanning tree with at most k leaves is referred to as a spanning k-ended tree. Spanning k-ended trees are important in various fields such as network design, graph theory, and communication networks. They provide a structured way to connect all the nodes in a network while ensuring efficient communication and minimizing unnecessary connections. In addition, they serve as fundamental components for algorithms in routing, broadcasting, and spanning tree protocols. However, determining whether a connected graph has a spanning k-ended tree or not is NP-complete. Therefore, it is important to identify sufficient conditions for the existence of such trees. The implicit-degree proposed by Zhu, Li, and Deng is an important indicator for the Hamiltonian problem and the spanning k-ended tree problem. In this article, we provide two sufficient conditions for K_1,4-free connected graphs to have spanning k-ended trees for k = 2, 3. We prove the following: Let G be a K_1,4-free connected n-graph. For k = 2, 3, if the implicit-degree sum of any k + 1 independent vertices of G is at least n − k + 2, then G has a spanning k-ended tree. Moreover, we give two examples to show that the lower bounds n and n − 1 are the best possible. Full article

(This article belongs to the Special Issue Advanced Graph Theory and Combinatorics)

► Show Figures

Figure 1

20 pages, 500 KiB

Open AccessArticle

Dual-Neighborhood Search for Solving the Minimum Dominating Tree Problem

by Ze Pan, Xinyun Wu and Caiquan Xiong

Mathematics 2023, 11(19), 4214; https://doi.org/10.3390/math11194214 - 9 Oct 2023

Viewed by 1193

Abstract

The minimum dominating tree (MDT) problem consists of finding a minimum weight subgraph from an undirected graph, such that each vertex not in this subgraph is adjacent to at least one of the vertices in it, and the subgraph is connected without any [...] Read more.

The minimum dominating tree (MDT) problem consists of finding a minimum weight subgraph from an undirected graph, such that each vertex not in this subgraph is adjacent to at least one of the vertices in it, and the subgraph is connected without any ring structures. This paper presents a dual-neighborhood search (DNS) algorithm for solving the MDT problem, which integrates several distinguishing features, such as two neighborhoods collaboratively working for optimizing the objective function, a fast neighborhood evaluation method to boost the searching effectiveness, and several diversification techniques to help the searching process jump out of the local optimum trap thus obtaining better solutions. DNS improves the previous best-known results for four public benchmark instances while providing competitive results for the remaining ones. Several ingredients of DNS are investigated to demonstrate the importance of the proposed ideas and techniques. Full article

(This article belongs to the Special Issue Advanced Graph Theory and Combinatorics)

► Show Figures

Figure 1

11 pages, 496 KiB

Open AccessArticle

Generalized Connectivity of the Mycielskian Graph under g-Extra Restriction

by Jinyu Zou, He Li, Shumin Zhang and Chengfu Ye

Mathematics 2023, 11(19), 4043; https://doi.org/10.3390/math11194043 - 23 Sep 2023

Viewed by 1085

Abstract

The g-extra connectivity is a very important index to evaluate the fault tolerance, reliability of interconnection networks. Let g be a non-negative integer, G be a connected graph with vertex set V and edge set E, a subset

S \subseteq V

[...] Read more.

The g-extra connectivity is a very important index to evaluate the fault tolerance, reliability of interconnection networks. Let g be a non-negative integer, G be a connected graph with vertex set V and edge set E, a subset

S \subseteq V

is called a g-extra cut of G if the graph induced by the set

G - S

is disconnected and each component of

G - S

has at least

g + 1

vertices. The g-extra connectivity of G, denoted as

κ_{g} (G)

, is the cardinality of the minimum g-extra cut of G. Mycielski introduced a graph transformation to discover chromatic numbers of triangle-free graphs that can be arbitrarily large. This transformation converts a graph G into a new compound graph called

μ (G)

, also known as the Mycielskian graph of G. In this paper, we study the relationship on g-extra connectivity between the Mycielskian graph

μ (G)

and the graph G. In addition, we show that

κ_{3} (μ (G)) = 2 κ_{1} (G) + 1

for

κ_{1} (G) \leq m i n {4, ⌊ \frac{n}{2} ⌋}

, and prove the bounds of

κ_{2 g + 1} (μ (G))

for

g \geq 2

. Full article

(This article belongs to the Special Issue Advanced Graph Theory and Combinatorics)

► Show Figures

Figure 1

11 pages, 268 KiB

Open AccessArticle

Endomorphism Spectra of Double-Edge Fan Graphs

by Kaidi Xu, Hailong Hou and Yu Li

Mathematics 2023, 11(14), 3214; https://doi.org/10.3390/math11143214 - 21 Jul 2023

Viewed by 979

Abstract

There are six classes of endomorphisms for a graph. The sets of these endomorphisms form a chain under the inclusion of sets. In order to systematically study these endomorphisms, Böttcher and Knauer defined the concepts of the endomorphism spectrum and endomorphism type of [...] Read more.

There are six classes of endomorphisms for a graph. The sets of these endomorphisms form a chain under the inclusion of sets. In order to systematically study these endomorphisms, Böttcher and Knauer defined the concepts of the endomorphism spectrum and endomorphism type of a graph in 1992. In this paper, based on the property and structure of the endomorphism monoids of graphs, six classes of endomorphisms of double-edge fan graphs are described. In particular, we give the endomorphism spectra and endomorphism types of double-edge fan graphs. Full article

(This article belongs to the Special Issue Advanced Graph Theory and Combinatorics)

► Show Figures

Figure 1

16 pages, 5131 KiB

Open AccessArticle

Fuzzy Domination Graphs in Decision Support Tasks

by Vladimir Sudakov and Alexander Zhukov

Mathematics 2023, 11(13), 2837; https://doi.org/10.3390/math11132837 - 24 Jun 2023

Cited by 2 | Viewed by 1186

Abstract

In decision support tasks, one often has to deal with uncertainty due to fuzzy judgments of the decision maker or the expert. This paper proposes methods that allow you to rank the alternatives based on fuzzy evaluations. This is achieved by using fuzzy [...] Read more.

In decision support tasks, one often has to deal with uncertainty due to fuzzy judgments of the decision maker or the expert. This paper proposes methods that allow you to rank the alternatives based on fuzzy evaluations. This is achieved by using fuzzy weighted summation, fuzzy implication, a computation graph showing the criteria, and a fuzzy dominance graph showing the alternatives. If the criteria have equal importance, then fuzzy graphs corresponding to the dominance of each of the criteria are used. An algorithm that is used for both the transition from fuzzy dominance graphs and the ranking of alternatives is proposed. This algorithm is based on the idea of constructing Kemeny medians or other concordant rankings at a given confidence level in the existence of corresponding arcs. Computational experiments have shown the performance of these approaches. It is reasonable to apply them in problems that require complex expert evaluations with a large number of alternatives and criteria. Full article

(This article belongs to the Special Issue Advanced Graph Theory and Combinatorics)

► Show Figures

Figure 1

11 pages, 1963 KiB

Open AccessArticle

Underwater Image Enhancement Based on the Improved Algorithm of Dark Channel

by Dachang Zhu

Mathematics 2023, 11(6), 1382; https://doi.org/10.3390/math11061382 - 13 Mar 2023

Cited by 11 | Viewed by 3409

Abstract

Enhancing underwater images presents a challenging problem owing to the influence of ocean currents, the refraction, absorption and scattering of light by suspended particles, and the weak illumination intensity. Recently, different methods have relied on the underwater image formation model and deep learning [...] Read more.

Enhancing underwater images presents a challenging problem owing to the influence of ocean currents, the refraction, absorption and scattering of light by suspended particles, and the weak illumination intensity. Recently, different methods have relied on the underwater image formation model and deep learning techniques to restore underwater images. However, they tend to degrade the underwater images, interfere with background clutter and miss the boundary details of blue regions. An improved image fusion and enhancement algorithm based on a prior dark channel is proposed in this paper based on graph theory. Image edge feature sharpening, and dark detail enhancement by homomorphism filtering in CIELab colour space are realized. In the RGB colour space, the multi-scale retinal with colour restoration (MSRCR) algorithm is used to improve colour deviation and enhance colour saturation. The contrast-limited adaptive histogram equalization (CLAHE) algorithm defogs and enhances image contrast. Finally, according to the dark channel images of the three processing results, the final enhanced image is obtained by the linear fusion of multiple images and channels. Experimental results demonstrate the effectiveness and practicality of the proposed method on various data sets. Full article

(This article belongs to the Special Issue Advanced Graph Theory and Combinatorics)

► Show Figures

Figure 1

9 pages, 326 KiB

Open AccessArticle

Multi de Bruijn Sequences and the Cross-Join Method

by Abbas Alhakim and Janusz Szmidt

Mathematics 2023, 11(5), 1262; https://doi.org/10.3390/math11051262 - 6 Mar 2023

Viewed by 1541

Abstract

We show a method to construct binary multi de Bruijn sequences using the cross-join method. We extend the proof given by Alhakim for ordinary de Bruijn sequences to the case of multi de Bruijn sequences. In particular, we establish that all multi de [...] Read more.

We show a method to construct binary multi de Bruijn sequences using the cross-join method. We extend the proof given by Alhakim for ordinary de Bruijn sequences to the case of multi de Bruijn sequences. In particular, we establish that all multi de Bruijn sequences can be obtained by cross-joining an ordinary de Bruijn sequence concatenated with itself an appropriate number of times. We implemented the generation of all multi de Bruijn sequences of type

C (2, 2, 2)

and

C (3, 2, 2) .

We experimentally confirm that some multi de Bruijn sequences can be generated by Galois Nonlinear Feedback Shift Registers (NLFSRs). It is supposed that all multi de Bruijn sequences can be generated using Galois NLFSRs. Full article

(This article belongs to the Special Issue Advanced Graph Theory and Combinatorics)

► Show Figures

Figure 1

17 pages, 305 KiB

Open AccessArticle

Metric Dimensions of Bicyclic Graphs

by Asad Khan, Ghulam Haidar, Naeem Abbas, Murad Ul Islam Khan, Azmat Ullah Khan Niazi and Asad Ul Islam Khan

Mathematics 2023, 11(4), 869; https://doi.org/10.3390/math11040869 - 8 Feb 2023

Cited by 3 | Viewed by 2445

Abstract

The distance

d (v_{a}, v_{b})

between two vertices of a simple connected graph G is the length of the shortest path between

v_{a}

and

v_{b}

. Vertices

v_{a}, v_{b}

of G are considered [...] Read more.

The distance

d (v_{a}, v_{b})

between two vertices of a simple connected graph G is the length of the shortest path between

v_{a}

and

v_{b}

. Vertices

v_{a}, v_{b}

of G are considered to be resolved by a vertex v if

d (v_{a}, v) \neq d (v_{b}, v)

. An ordered set

W = {v_{1}, v_{2}, v_{3}, \dots, v_{s}} \subseteq V (G)

is said to be a resolving set for G, if for any

v_{a}, v_{b} \in V (G),

∃

v_{i} \in W ∋ d (v_{a}, v_{i}) \neq d (v_{b}, v_{i})

. The representation of vertex v with respect to W is denoted by

r (v | W)

and is an s-vector(s-tuple)

(d (v, v_{1}), d (v, v_{2}), d (v, v_{3}), \dots, d (v, v_{s}))

. Using representation

r (v | W)

, we can say that W is a resolving set if, for any two vertices

v_{a}, v_{b} \in V (G)

, we have

r (v_{a} | W) \neq r (v_{b} | W)

. A minimal resolving set is termed a metric basis for G. The cardinality of the metric basis set is called the metric dimension of G, represented by

d i m (G)

. In this article, we study the metric dimension of two types of bicyclic graphs. The obtained results prove that they have constant metric dimension. Full article

(This article belongs to the Special Issue Advanced Graph Theory and Combinatorics)

► Show Figures

Figure 1

13 pages, 3948 KiB

Open AccessArticle

Graph-Clustering Method for Construction of the Optimal Movement Trajectory under the Terrain Patrolling

by Boris V. Rumiantsev, Rasul A. Kochkarov and Azret A. Kochkarov

Mathematics 2023, 11(1), 223; https://doi.org/10.3390/math11010223 - 2 Jan 2023

Cited by 1 | Viewed by 1537

Abstract

The method of the optimal movement trajectory construction in the terrain patrolling tasks is proposed. The method is based on the search of the Hamiltonian circuit on the graph of the terrain map and allows automatic construction of the optimal closed path for [...] Read more.

The method of the optimal movement trajectory construction in the terrain patrolling tasks is proposed. The method is based on the search of the Hamiltonian circuit on the graph of the terrain map and allows automatic construction of the optimal closed path for arbitrary terrain map. The distinguishing feature of the method is the use of the modified algorithm for the Hamiltonian circuit search. The algorithm can be scaled for the maps corresponding to the graphs with a large (more than 100) number of the vertices, for which the standard brute-force algorithm of the Hamiltonian circuit search requires significantly higher execution time than the proposed algorithm. It is demonstrated that the utilized algorithm possesses 17 times less constant of the time complexity growth than the standard brute-force algorithm. It allows more than one order of magnitude (from 30 to 500 vertices, i.e., approximately to the 17 times) increase of the graph vertices that is used for the Hamiltonian circuit search in the real time (0.1–100 s) regime. Full article

(This article belongs to the Special Issue Advanced Graph Theory and Combinatorics)

► Show Figures

Figure 1

15 pages, 621 KiB

Open AccessArticle

On the Degree Distribution of Haros Graphs

by Jorge Calero-Sanz

Mathematics 2023, 11(1), 92; https://doi.org/10.3390/math11010092 - 26 Dec 2022

Cited by 1 | Viewed by 1196

Abstract

Haros graphs are a graph-theoretical representation of real numbers in the unit interval. The degree distribution of the Haros graphs provides information regarding the topological structure and the associated real number. This article provides a comprehensive demonstration of a conjecture concerning the analytical [...] Read more.

Haros graphs are a graph-theoretical representation of real numbers in the unit interval. The degree distribution of the Haros graphs provides information regarding the topological structure and the associated real number. This article provides a comprehensive demonstration of a conjecture concerning the analytical formulation of the degree distribution. Specifically, a theorem outlines the relationship between Haros graphs, the corresponding continued fraction of its associated real number, and the subsequent symbolic paths in the Farey binary tree. Moreover, an expression that is continuous and piecewise linear in subintervals defined by Farey fractions can be derived from an additional conclusion for the degree distribution of Haros graphs. Full article

(This article belongs to the Special Issue Advanced Graph Theory and Combinatorics)

► Show Figures

Figure 1

15 pages, 422 KiB

Open AccessArticle

The Connective Eccentricity Index of Hypergraphs

by Guihai Yu, Renjie Wu and Xingfu Li

Mathematics 2022, 10(23), 4574; https://doi.org/10.3390/math10234574 - 2 Dec 2022

Cited by 3 | Viewed by 1689

Abstract

The connective eccentricity index (CEI) of a hypergraph

G

is defined as

ξ^{c e} (G) = \sum_{v \in V (G)} \frac{d_{G} (v)}{ε_{G} (v)}

, where

ε_{G} (v)

[...] Read more.

The connective eccentricity index (CEI) of a hypergraph

G

is defined as

ξ^{c e} (G) = \sum_{v \in V (G)} \frac{d_{G} (v)}{ε_{G} (v)}

, where

ε_{G} (v)

and

d_{G} (v)

denote the eccentricity and the degree of the vertex v, respectively. In this paper, we determine the maximal and minimal values of the connective eccentricity index among all k-uniform hypertrees on n vertices and characterize the corresponding extremal hypertrees. Finally, we establish some relationships between the connective eccentricity index and the eccentric connectivity index of hypergraphs. Full article

(This article belongs to the Special Issue Advanced Graph Theory and Combinatorics)

► Show Figures

Figure 1

14 pages, 2613 KiB

Open AccessArticle

Application of Graph Structures in Computer Vision Tasks

by Nikita Andriyanov

Mathematics 2022, 10(21), 4021; https://doi.org/10.3390/math10214021 - 29 Oct 2022

Cited by 4 | Viewed by 2966

Abstract

On the one hand, the solution of computer vision tasks is associated with the development of various kinds of images or random fields mathematical models, i.e., algorithms, that are called traditional image processing. On the other hand, nowadays, deep learning methods play an [...] Read more.

On the one hand, the solution of computer vision tasks is associated with the development of various kinds of images or random fields mathematical models, i.e., algorithms, that are called traditional image processing. On the other hand, nowadays, deep learning methods play an important role in image recognition tasks. Such methods are based on convolutional neural networks that perform many matrix multiplication operations with model parameters and local convolutions and pooling operations. However, the modern artificial neural network architectures, such as transformers, came to the field of machine vision from natural language processing. Image transformers operate with embeddings, in the form of mosaic blocks of picture and the links between them. However, the use of graph methods in the design of neural networks can also increase efficiency. In this case, the search for hyperparameters will also include an architectural solution, such as the number of hidden layers and the number of neurons for each layer. The article proposes to use graph structures to develop simple recognition networks on different datasets, including small unbalanced X-ray image datasets, widely known the CIFAR-10 dataset and the Kaggle competition Dogs vs Cats dataset. Graph methods are compared with various known architectures and with networks trained from scratch. In addition, an algorithm for representing an image in the form of graph lattice segments is implemented, for which an appropriate description is created, based on graph data structures. This description provides quite good accuracy and performance of recognition. The effectiveness of this approach based, on the descriptors of the resulting segments, is shown, as well as the graph methods for the architecture search. Full article

(This article belongs to the Special Issue Advanced Graph Theory and Combinatorics)

► Show Figures

Figure 1

17 pages, 4709 KiB

Open AccessArticle

Construction of Dual Optimal Bidirectional Double-Loop Networks for Optimal Routing

by Hui Liu, Xiaowan Li and Shenling Wang

Mathematics 2022, 10(21), 4016; https://doi.org/10.3390/math10214016 - 29 Oct 2022

Cited by 2 | Viewed by 1400

Abstract

Bidirectional double-loop networks (BDLNs) are widely used in computer networks for their simplicity, symmetry and scalability. One common way to improve their performance is to decrease the diameter and average distance. Attempts have been made to find BDLNs with minimal diameters; however, such [...] Read more.

Bidirectional double-loop networks (BDLNs) are widely used in computer networks for their simplicity, symmetry and scalability. One common way to improve their performance is to decrease the diameter and average distance. Attempts have been made to find BDLNs with minimal diameters; however, such BDLNs will not necessarily have the minimum average distance. In this paper, we construct dual optimal BDLNs with minimum diameters and average distances using an efficient method based on coordinate embedding and transforming. First, we get the lower bounds of both the diameter and average distance by embedding a BDLN into Cartesian coordinates. Then, we construct tight optimal BDLNs that provide the aforementioned lower bounds based on an embedding graph. On the basis of node distribution regularity in tight optimal BDLNs, we construct dual optimal BDLNs with minimum diameters and average distances for any number of nodes. Finally, we present on-demand optimal message routing algorithms for the dual optimal BDLNs that we have constructed. The presented algorithms do not require routing tables and are efficient, requiring little computation. Full article

(This article belongs to the Special Issue Advanced Graph Theory and Combinatorics)

► Show Figures

Figure 1

16 pages, 434 KiB

Open AccessArticle

Algorithm for Optimization of Inverse Problem Modeling in Fuzzy Cognitive Maps

by Alina Vladimirovna Petukhova, Anna Vladimirovna Kovalenko and Anna Vyacheslavovna Ovsyannikova

Mathematics 2022, 10(19), 3452; https://doi.org/10.3390/math10193452 - 22 Sep 2022

Cited by 3 | Viewed by 1937

Abstract

Managerial decision-making is a complex process that has several problems. The more heterogeneous the system, the more immeasurable, non-numerical information it contains. To understand the cognitive processes involved, it is important to describe in detail their components, define the dependencies between components, and [...] Read more.

Managerial decision-making is a complex process that has several problems. The more heterogeneous the system, the more immeasurable, non-numerical information it contains. To understand the cognitive processes involved, it is important to describe in detail their components, define the dependencies between components, and apply relevant algorithms for scenario modelling. Fuzzy cognitive maps (FCMs) is the popular approach for modeling a system’s behavior over time and defining its main properties. This work develops a new algorithm for scenario analysis in complex systems represented by FCMs to provide support for decision-making. The algorithm allows researchers to analyze system-development scenarios to obtain the required change to the system’s components that leads to the target state. The problem of determining a system’s initial state is most conspicuous when constructing a compound or unbalanced fuzzy maps. Currently, a brute force algorithm is used to calculate the steps needed to approach a target, but that takes exponential time. The paper describes a new algorithm to obtain the initial values of the controlled concepts in fuzzy cognitive maps using the theory of neutrosophic fuzzy equations. This approach reduces the time needed to find the optimal solution to a problem, and it allows inverse problems to be solved in the fuzzy cognitive maps as a part of the scenario-modeling framework. Full article

(This article belongs to the Special Issue Advanced Graph Theory and Combinatorics)

► Show Figures

Figure 1

15 pages, 312 KiB

Open AccessArticle

On Two Outer Independent Roman Domination Related Parameters in Torus Graphs

by Hong Gao, Xing Liu, Yuanyuan Guo and Yuansheng Yang

Mathematics 2022, 10(18), 3361; https://doi.org/10.3390/math10183361 - 16 Sep 2022

Cited by 1 | Viewed by 1557

Abstract

In a graph

G = (V, E)

, where every vertex is assigned 0, 1 or 2, f is an assignment such that every vertex assigned 0 has at least one neighbor assigned 2 and all vertices labeled by 0 [...] Read more.

In a graph

G = (V, E)

, where every vertex is assigned 0, 1 or 2, f is an assignment such that every vertex assigned 0 has at least one neighbor assigned 2 and all vertices labeled by 0 are independent, then f is called an outer independent Roman dominating function (OIRDF). The domination is strengthened if every vertex is assigned 0, 1, 2 or 3, f is such an assignment that each vertex assigned 0 has at least two neighbors assigned 2 or one neighbor assigned 3, each vertex assigned 1 has at least one neighbor assigned 2 or 3, and all vertices labeled by 0 are independent, then f is called an outer independent double Roman dominating function (OIDRDF). The weight of an (OIDRDF) OIRDF f is the sum of

f (v)

for all

v \in V

. The outer independent (double) Roman domination number (

γ_{o i d R} (G)

)

γ_{o i R} (G)

is the minimum weight taken over all (OIDRDFs) OIRDFs of G. In this article, we investigate these two parameters

γ_{o i R} (G)

and

γ_{o i d R} (G)

of regular graphs and present lower bounds on them. We improve the lower bound on

γ_{o i R} (G)

for a regular graph presented by Ahangar et al. (2017). Furthermore, we present upper bounds on

γ_{o i R} (G)

and

γ_{o i d R} (G)

for torus graphs. Furthermore, we determine the exact values of

γ_{o i R} (C_{3} □ C_{n})

and

γ_{o i R} (C_{m} □ C_{n})

for

m \equiv 0 (\mod 4)

and

n \equiv 0 (\mod 4)

, and the exact value of

γ_{o i d R} (C_{3} □ C_{n})

. By our result,

γ_{o i d R} (C_{m} □ C_{n}) \leq 5 m n / 4

which verifies the open question is correct for

C_{m} □ C_{n}

that was presented by Ahangar et al. (2020). Full article

(This article belongs to the Special Issue Advanced Graph Theory and Combinatorics)

► Show Figures

Figure 1

Journal Menu

Journal Browser

Advanced Graph Theory and Combinatorics

Share This Special Issue

Special Issue Editor

Special Issue Information

Keywords

Benefits of Publishing in a Special Issue

Published Papers (17 papers)

Research

Further Information

Guidelines

MDPI Initiatives

Follow MDPI