Search

An Italian dominating function of a graph G = (V , E) with vertex set V is defined as a function f : V → { 0 , 1 , 2 } , which satisfies the condition that for every v ∈ V with f (v) = 0 , ∑ u ∈ N (v) f (u) ≥ 2. The weight of an Italian dominating function on G is the sum f (V) = ∑ u ∈ V f (v) and the Italian dominating number, and γ I (G) indicates the minimum weight of an Italian dominating function f. In this paper, the structure of the generalized Sierpiński networks is investigated using the bounds of Italian domination number of graphs and the methods of mathematical induction and reduction to absurdity. Then, the Italian domination on the generalized Sierpiński networks S (G , t) is obtained, where G denotes any special class of Path P n , Cycle C n , Wheel W n , Star K 1 , n , and complete bipartite graph K m , n . [ABSTRACT FROM AUTHOR]

The distance energy of a connected graph G is the sum of absolute values of the eigenvalues of the distance matrix of G. In this paper, we study how the distance energy of the complete split graph G S (m , n) = K m + K ¯ n changes when an edge is deleted from it. The complete split graph G S (m , n) consists of a clique on m vertices and an independent set on n vertices in which each vertex of the clique is adjacent to each vertex of the independent set. We prove that the distance energy of the complete split graph G S (m , n) always increases when an edge is deleted from it. [ABSTRACT FROM AUTHOR]

Graph protection using mobile guards has received a lot of attention in the literature. It has been considered in different forms, including Eternal Dominating set, Eternal Independent set and Eternal Vertex Cover set. In this paper, we introduce and study two new models of graph protection, namely Eternal Feedback Vertex Sets (EFVS) and m-Eternal Feedback Vertex Sets (m-EFVS). Both models are based on an initial selection of a feedback vertex set (FVS), where a vertex in FVS can be replaced with a neighboring vertex such that the resulting set is a FVS too. We prove bounds for both the eternal and m-eternal feedback vertex numbers on, mainly, distance graphs, circulant graphs and grids. Also, we deduce other inequalities for both parameters on cycles, complete graphs and complete bipartite graphs. [ABSTRACT FROM AUTHOR]

In this paper, we generalize the concepts of (perfect) Roman and Italian dominations to (perfect) strong Roman and Roman k -domination for arbitrary positive integer k. These generalizations cover some of previous ones. After some comparison of their domination numbers, as a first study of these concepts, we study the (perfect, strong, perfect strong) Roman k -domination numbers of complete bipartite graphs. [ABSTRACT FROM AUTHOR]

The crossing number of a graph G , denoted by cr (G) , is defined to be the minimum number of crossings that arise among all its drawings in the plane. This concept has been of interest to many researchers who have studied it for many families of graphs. In this paper, we introduce the crossing number of Cartesian product of sunlet graph S m with path P n . Further, we prove that the crossing number of S m □ P 2 is equal to m , along with giving a conjecture for the general case. In addition, we utilize the vertex's rotation concept in order to prove some necessary conditions for the complete bipartite graph K m , n to be optimal when it is drawn in the plane, by presenting an upper bound for the crossing number of any subgraph in it together with determining the exact number of crossings in case the vertices of subgraph have the same rotation. [ABSTRACT FROM AUTHOR]

Let G be a graph. A vertex-cut S of G is said to be k-restricted if every component of G − S has at least k vertices, and cyclic if G − S has at least two components which contain a cycle. The minimum cardinality over all k -restricted vertex-cuts of G is called the k-restricted connectivity of G and is denoted by κ k (G). Also the minimum cardinality over all cyclic vertex-cuts of G is called the cyclic connectivity of graph G and is denoted by κ c (G). In this paper, the k -restricted connectivity and cyclic connectivity of the direct product of two graphs G 1 and G 2 is obtained for some k ≥ 2 , where G 1 is a complete graph, and G 2 is a complete graph, a complete bipartite graph or a cycle. [ABSTRACT FROM AUTHOR]

Let R be a commutative ring with unity, and let Γ (R) denote the comaximal graph of R. The comaximal graph Γ (R) has vertex set as R, and any two distinct vertices x, y of Γ (R) are adjacent if R x + R y = R. Let Γ 2 (R) denote the induced subgraph of Γ (R) on the set of all nonzero non-unit elements of R, and any two distinct vertices x, y of Γ 2 (R) are adjacent if R x + R y = R. In this paper, we study the graphical structure as well the adjacency spectrum of Γ 2 (ℤ n) , where n ≥ 4 is a non-prime positive integer, and ℤ n is the ring of integers modulo n. We show that for a given non-prime positive integer n with D number of positive proper divisors, the eigenvalues of Γ 2 (ℤ n) are 0 with multiplicity n − φ (n) − D − 1 , and remaining eigenvalues are contained in the spectrum of a symmetric D × D matrix. We further calculate the rank and nullity of Γ 2 (ℤ n). We also determine all the eigenvalues of Γ 2 (ℤ n) whenever Γ 2 (ℤ n) is a bipartite graph. Finally, apart from determining certain structural properties of Γ 2 (ℤ n) , we conclude the paper by determining the metric dimension of Γ 2 (ℤ n). [ABSTRACT FROM AUTHOR]

A broadcast on a graph G = (V , E) is a function f : V → { 0 , 1 , ... , diam (G) } such that for each v ∈ V , f (v) ≤ e (v) , where diam (G) denotes the diameter of G and e (v) denotes the eccentricity of v. The cost of a broadcast is the value f (V) = ∑ v ∈ V f (v). In this paper, we define and study a new invariant of broadcasts in graphs, which is global dominating broadcast. A dominating broadcast f of a graph G is a global dominating broadcast if f is also a dominating broadcast of G ¯ the complement of G. We begin by determining the global broadcast domination number of bipartite graphs, paths, cycles, grid graphs and trees. Then we establish lower and upper bounds on the global broadcast domination number of a graph. Finally, we establish relationships between the global broadcast domination number and other parameters. [ABSTRACT FROM AUTHOR]

The partially balanced incomplete block (PBIB)-designs and association schemes arising from different graph parameters is a well-studied concept. In this paper, we define and construct PBIB-designs with association schemes in strongly regular graphs through the nodes belonging to the diametral paths as blocks. A (v , b , r , k , λ , μ) -design, called a diametral-design (in short) over a strongly regular graph G = (V , E) of degree d , diameter diam (G) , is an ordered pair D = (V , B) , where V = V (G) and B is the set of all diametral paths of G , called blocks, containing the nodes belonging to the diametral paths, satisfying the following conditions: (i) If x , y ∈ V and { x , y } ∈ E , then there are exactly λ blocks containing { x , y } ; (ii) If x , y ∈ V , x ≠ y and { x , y } ∉ E , then there are exactly μ -blocks containing { x , y }. We construct PBIB-designs with two-association schemes through diametral paths corresponding to the strongly regular graphs such as the square lattice graphs L 2 (n) , the triangular graphs T (n) , the three Chang graphs, the Petersen graph, the Shrikhande graph, the Clebsch graph, the complement of Clebsch graph, the complement of Schläfli graph, complete bipartite graphs, the Hoffman–Singleton graph, etc. and in each case we give the composition of the diametral paths. These serve as extensions for the collection of near impossible class of strongly regular graphs with given parameters having two-association schemes. [ABSTRACT FROM AUTHOR]

In this paper, we analyze the intersection graphs of subtrees in a cactus, called cactus subtree graphs. A max-k-cliquesubgraph of a graph is an induced subgraph whose maximum clique has at most k vertices. We describe a polynomial time algorithm to find a maximum weight max- k -clique subgraph in a cactus subtree graph when k is fixed. In perfect graphs this problem is equivalent to the maximum weight k -colorable subgraph problem. In many applications like scheduling production lines and communication networks on imperfect graphs, a maximum max- k -clique subgraph solution is better than a maximum k -colorable subgraph solution. In addition, we describe cactus subtree graphs polynomial time algorithms for recognition, maximum independent sets, maximum cliques, maximum induced bipartite graphs, maximum induced forests and minimum feedback vertex sets. [ABSTRACT FROM AUTHOR]

In this paper, we introduced the new concept detour global domination number for splitting graph of standard graph. The detour global dominating sets in some standard and special graphs are determined. First we recollect the concept of splitting graph of a graph and we produce some results based on the detour global domination number of splitting graph of star graph, bistar graph and complete bipartite graph. A set S is called a detour global dominating set of G if S is both detour and global dominating set of G. The detour global domination number is the minimum cardinality of a detour global dominating set in G. [ABSTRACT FROM AUTHOR]

An edge labeling of a connected graph G = (V , E) is said to be local antimagic if it is a bijection f : E → { 1 , ... , | E | } such that for any pair of adjacent vertices x and y, f + (x) ≠ f + (y) , where the induced vertex label f + (x) = ∑ f (e) , with e ranging over all the edges incident to x. The local antimagic chromatic number of G, denoted by χ la (G) , is the minimum number of distinct induced vertex labels over all local antimagic labelings of G. In this paper, we show the existence of infinitely many bipartite and tripartite graphs with χ l a = 2 , 3. [ABSTRACT FROM AUTHOR]

Indicated coloring is a graph coloring game in which two players collectively color the vertices of a graph in the following way. In each round, the first player (Ann) selects a vertex, and then the second player (Ben) colors it properly, using a fixed set of colors. The goal of Ann is to achieve a proper coloring of the whole graph, while Ben is trying to prevent the realization of this project. The smallest number of colors necessary for Ann to win the game on a graph G (regardless of Ben's strategy) is called the indicated chromatic number of G, denoted by χ i (G). In this paper, we examine whether the Mycielskian of G, μ (G) , is k-indicated colorable for all k ≥ χ i (μ (G)) , whenever G is l-indicated colorable for all l ≥ χ i (G). In this direction, we prove that the Mycielskian of the bipartite graphs, complete multipartite graphs, { P 5 , K 3 } -free graphs, { P 5 , K 4 , K i t e , B u l l } -free graphs, { 2 K 2 , C 4 } -free graphs and { P 6 , C 5 , P 5 ¯ , K 1 , 3 } -free graphs are k-indicated colorable for all k greater than or equal to the indicated chromatic number of the corresponding graphs. [ABSTRACT FROM AUTHOR]

A graph G is a 3-degree 4-chordal graph if every cycle of length at least five has a chord and the degree of each vertex is at most three. In this paper, we investigate the structure of 3-degree 4-chordal graphs, which is a subclass of 3-degree graphs. We present a structural characterization based on minimal vertex separators and bi-connected components. Many classical problems are known to be NP-complete for 3-degree graphs, and 3-degree 4-chordal graphs are a nontrivial subclass of 3-degree graphs. Using our structural results, we present polynomial-time algorithms for many classical problems which are grouped into (i) subset problems (vertex cover and its variants, feedback vertex set, Steiner tree), (ii) Hamiltonicity and its variants, (iii) graph embedding problems (treewidth, minimum fill-in), and (iv) Coloring problems(rainbow coloring). [ABSTRACT FROM AUTHOR]

A set D ⊆ V of a graph G = (V , E) is called an efficient dominating set of G if every vertex v has exactly one neighbor in D , in other words, the vertex set V is partitioned to some circles with radius one such that the vertices in D are the centers of partitions. A generalization of this concept, introduced by Chellali et al. [k-Efficient partitions of graphs, Commun. Comb. Optim. 4 (2019) 109–122], is called k -efficient dominating set that briefly partitions the vertices of graph with different radiuses. It leads to a partition set { U 1 , U 2 , ... , U t } such that each U i consists a center vertex u i and all the vertices in distance d i , where d i ∈ { 0 , 1 , ... , k }. In other words, there exist the dominators with various dominating powers. The problem of finding minimum set { u 1 , u 2 , ... , u t } is called the minimum k -efficient domination problem. Given a positive integer S and a graph G = (V , E) , the k -efficient Domination Decision problem is to decide whether G has a k -efficient dominating set of cardinality at most S. The k -efficient Domination Decision problem is known to be NP-complete even for bipartite graphs [M. Chellali, T. W. Haynes and S. Hedetniemi, k-Efficient partitions of graphs, Commun. Comb. Optim.  4 (2019) 109–122]. Clearly, every graph has a k -efficient dominating set but it is not correct for efficient dominating set. In this paper, we study the following: k -efficient domination problem set is NP-complete even in chordal graphs. A polynomial-time algorithm for k -efficient domination in trees. k -efficient domination on sparse graphs from the parametrized complexity perspective. In particular, we show that it is W [ 1 ] -hard on d-degenerate graphs while the original dominating set has Fixed Parameter Tractable (FPT) algorithm on d-degenerate graphs. k -efficient domination on nowhere-dense graphs is FPT. [ABSTRACT FROM AUTHOR]

For a graph G = (V , E) , a double Roman dominating function (DRDF) is a function f : V → { 0 , 1 , 2 , 3 } having the property that if f (v) = 0 for some vertex v , then v has at least two neighbors assigned 2 under f or one neighbor w with f (w) = 3 , and if f (v) = 1 then v has at least one neighbor w with f (w) ≥ 2. The weight of a DRDF f is the sum f (V) = ∑ u ∈ V f (u). The minimum weight of a DRDF on a graph G is the double Roman domination number of G and is denoted by γ d R (G). The double Roman bondage number of G , denoted by b d R (G) , is the minimum cardinality among all edge subsets B ⊆ E (G) such that γ d R (G − B) > γ d R (G). In this paper, we study the double Roman bondage number in graphs. We determine the double Roman bondage number in several families of graphs, and present several bounds for the double Roman bondage number. We also study the complexity issue of the double Roman bondage number and prove that the decision problem for the double Roman bondage number is NP-hard even when restricted to bipartite graphs. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a simple, undirected and connected graph. A vertex v of a simple, undirected graph v e -dominates all edges incident to at least one vertex in its closed neighborhood N [ v ]. A set D of vertices is a vertex-edge dominating set of G , if every edge of graph G is v e -dominated by some vertex of D. A vertex-edge dominating set D of G is called a total vertex-edge dominating set if the induced subgraph G [ D ] has no isolated vertices. The total vertex-edge domination number γ ve t (G) is the minimum cardinality of a total vertex-edge dominating set of G. In this paper, we prove that the decision problem corresponding to γ ve t (G) is NP-complete for chordal graphs, star convex bipartite graphs, comb convex bipartite graphs and planar graphs. The problem of determining γ ve t (G) of a graph G is called the minimum total vertex-edge domination problem (MTVEDP). We prove that MTVEDP is linear time solvable for chain graphs and threshold graphs. We also show that MTVEDP can be approximated within approximation ratio of ln (Δ − 0. 5) + 1. 5. It is shown that the domination and total vertex-edge domination problems are not equivalent in computational complexity aspects. Finally, an integer linear programming formulation for MTVEDP is presented. [ABSTRACT FROM AUTHOR]

Let G be a graph with the vertex set V. A function f : V → { 0 , 1 , 2 } is called a Roman dominating function of G , if every vertex v with f (v) = 0 is adjacent to at least one vertex u with f (u) = 2. The weight of a Roman dominating function f is equal to ∑ v ∈ V (G) f (v). The minimum weight of a Roman dominating function of G is called the Roman domination number of G , denoted by γ R (G). In this paper, we initiate the study of a variant of Roman dominating functions. A function f : V (G) → { 0 , 1 , 2 } is called an isolate Roman dominating function of G , if f is a Roman dominating function and there is a vertex v with f (v) = 0 which is not adjacent to any vertex u with f (u) = 0. The minimum weight of an isolate Roman dominating function of G is called the isolate Roman domination number of G , denoted by γ I R (G). We present some upper bound on the isolate Roman domination number of a graph G in terms of its Roman domination number and its domination number. Moreover, we present some classes of graphs G with γ I R (G) = γ R (G). Finally, we show that the decision problem associated with the isolate Roman dominating functions is NP-complete for bipartite graphs and chordal graphs. [ABSTRACT FROM AUTHOR]

A Roman dominating function (RDF) on a graph G is a function f : V (G) → { 0 , 1 , 2 } satisfying the condition that every vertex u for which f (u) = 0 is adjacent to at least one vertex v for which f (v) = 2. A vertex u with f (u) = 0 is undefended if it is not adjacent to a vertex with f (v) > 0. The function f : V (G) → { 0 , 1 , 2 } is a weak Roman dominating function (WRDF) if each vertex u with f (u) = 0 is adjacent to a vertex v with f (v) > 0 such that the function f ′ : V (G) → { 0 , 1 , 2 } defined by f ′ (u) = 1 , f ′ (v) = f (v) − 1 and f ′ (w) = f (w) if w ∈ V − { u , v } has no undefended vertex. The Roman domination subdivision number of a graph G is the minimum number of edges that must be subdivided in order to increase the Roman domination number of G. We introduce the concept of weak Roman subdivision number of a graph G , denoted by sd γ r (G) as the minimum number of edges that must be subdivided in order to increase the weak Roman domination number of G. In this paper, we determine the exact values of the weak Roman subdivision number for paths, cycles and complete bipartite graphs. We obtain bounds for the weak Roman subdivision number of a graph and characterize the extremal graphs. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a graph. A Roman { 2 } -dominating function f : V → { 0 , 1 , 2 } has the property that for every vertex v ∈ V with f (v) = 0 , either v is adjacent to a vertex assigned 2 under f , or v is adjacent to at least two vertices assigned 1 under f. A set { f 1 , f 2 , ... , f d } of distinct Roman { 2 } -dominating functions on G with the property that ∑ i = 1 d f i (v) ≤ 2 for each v ∈ V (G) is called a Roman { 2 } -domination family (or functions) on G. The maximum number of functions in a Roman { 2 } -dominating family on G is the Roman { 2 } -domatic number of G , denoted by d { R 2 } (G). In this paper, we answer two conjectures of Volkman [L. Volkmann, The Roman { 2 } -domatic number of graphs, Discrete Appl. Math. 258 (2019) 235–241] about Roman { 2 } -domatic number of graphs and we study this parameter for join of graphs and complete bipartite graphs. [ABSTRACT FROM AUTHOR]

For a simple, undirected graph G = (V , E) , a restrained Roman dominating function (rRDF) f : V → { 0 , 1 , 2 } has the property that, every vertex u with f (u) = 0 is adjacent to at least one vertex v for which f (v) = 2 and at least one vertex w for which f (w) = 0. The weight of an rRDF is the sum f (V) = ∑ v ∈ V f (v). The minimum weight of an rRDF is called the restrained Roman domination number (rRDN) and is denoted by γ r R (G). We show that restrained Roman domination and domination problems are not equivalent in computational complexity aspects. Next, we show that the problem of deciding if G has an rRDF of weight at most l for chordal and bipartite graphs is NP-complete. Finally, we show that rRDN is determined in linear time for bounded treewidth graphs and threshold graphs. [ABSTRACT FROM AUTHOR]

The metric dimension of graphs has been extended in some types and variations such as local metric dimension and complement metric dimension of graphs. Merging two concepts is one way of developing the concept of graph theory as a branch of mathematics. These two variations motivated us to construct a new concept of metric dimension so called local complement metric dimension. We apply this new concept to some particular classes of graphs and the corona product of two graphs. We also characterize the local complement metric dimension of graphs with certain properties, namely, bipartite graphs and odd cycle graphs. Furthermore, we discover the local complement metric dimension of the corona product of two particular graphs as well as the corona product of two general graphs. [ABSTRACT FROM AUTHOR]

A vertex v of a graph is said to v e r t e x - e d g e dominate every edge incident with v , as well as every edge incident to vertices adjacent to v. A subset D ⊆ V is a total outer connected vertex-edge dominating set of a graph G if every edge in G is v e r t e x - e d g e dominated by a vertex in D , the subgraph induced by D has no isolated vertices and the subgraph induced by V (G) ∖ D is connected. We initiate the study of total outer connected vertex-edge domination in graphs. We show that the decision problem for total outer-connected vertex-edge domination problem is N P -Complete even for bipartite graphs. We prove that for every tree of order n ≥ 3 with l leaves, γ tve oc (T) ≥ 2 (n − l + 1) / 3 and characterize the trees attaining the lower bound. We also study the effect of edge removal, edge addition and edge subdivision on total outer connected vertex-edge domination number of a graph. [ABSTRACT FROM AUTHOR]

An injective edge-coloring c of a graph G is an edge-coloring such that if e 1 , e 2 , and e 3 are three consecutive edges in G (they are consecutive if they form a path or a cycle of length three), then e 1 and e 3 receive different colors. The minimum integer k such that, G has an injective edge-coloring with k colors, is called the injective chromatic index of G ( χ inj ′ (G)). This parameter was introduced by Cardoso et al. [Injective coloring of graphs, Filomat 33(19) (2019) 6411–6423, arXiv:1510.02626] motivated by the Packet Radio Network problem. They proved that computing χ inj ′ (G) of a graph G is NP-hard. We give new upper bounds for this parameter and we present the relationships of the injective edge-coloring with other colorings of graphs. We study the injective edge-coloring of some classes of subcubic graphs. We prove that a subcubic bipartite graph has an injective chromatic index bounded by 6. We also prove that if G is a subcubic graph with maximum average degree less than 1 6 7 (respectively, 8 3 ), then G admits an injective edge-coloring with at most 4 (respectively, 6) colors. Moreover, we establish a tight upper bound for subcubic outerplanar graphs. [ABSTRACT FROM AUTHOR]

For a , b ∈ ℝ , we define the general eccentric distance sum of a connected graph G as EDS a , b (G) = ∑ v ∈ V (G) (e c c G (v)) a (D G (v)) b , where V (G) is the vertex set of G , e c c G (v) is the eccentricity of a vertex v in G , D G (v) = ∑ w ∈ V (G) d G (v , w) and d G (v , w) is the distance between vertices v and w in G. This index generalizes several other indices of graphs. We present some bounds on the general eccentric distance sum for general graphs, bipartite graphs and trees of given order, graphs of given order and vertex connectivity and graphs of given order and number of pendant vertices. The extremal graphs are presented as well. [ABSTRACT FROM AUTHOR]