Search

In this paper, the b -coloring problem is solved for every subdivision-edge neighborhood corona of paths, cycles, stars and complete graphs. In addition, some exact values and sharp bounds are established for the b -chromatic number of subdivision-edge neighborhood coronas of these graphs with any other graph. [ABSTRACT FROM AUTHOR]

Rainbow antimagic coloring is the combination of antimagic labeling and rainbow coloring. The smallest number of colors induced from all edge weights of antimagic labeling is the rainbow antimagic connection number of G , denoted by rac (G). Given a graph G with vertex set V (G) and edge set E (G) , the function f from V (G) to { 1 , 2 , ... , | V (G) | } is a bijective function. The associated weight of an edge y z ∈ E (G) under f is w (y z) = f (y) + f (z). A path R in the vertex-labeled graph G is said to be a rainbow y − z path if for any two edges y z , y ′ z ′ ∈ E (R) it satisfies w (y z) ≠ w (y ′ z ′). The function f is called a rainbow antimagic labeling of G if there exists a rainbow y − z path for every two vertices y , z ∈ V (G). When we assign each edge y z with the color of the edge weight w (y z) , we say the graph G admits a rainbow antimagic coloring. In this paper, we show the new lower bound and exact value of the rainbow antimagic connection number of comb product of any tree and complete bipartite graph. [ABSTRACT FROM AUTHOR]

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]

Metric-based parameters aided the study of the structural properties of graph network space like complexity, central tendency, connectivity, robustness, accessibility, and vulnerability. At the same time, these parameters played a pivotal role in rectifying problems in navigation, integer programming, optimization, pattern recognition and avoidance, combinatoric detection, backtracking in geographical routing, etc. In this paper, we considered the fractional edge dimension, a metric-based parameter in local environment by initiating the study of the fractional local edge dimensions of a graph (FLED). We define the aforesaid concept and give its bounds. We discussed the characterization problem for FLED equal to 1 , the realization problem, and its relation with the fractional metric dimensions. We also calculated the FLED of the Petersen graph, Coxeter graph, the families of cycle, complete, wheel, grid and complete r -partite 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]

The graph obtained by joining cycle C m to a path P n with a bridge is called Tadpole graph denoted by T m , n . A subset D of V (G) is said to be a tadpole dominating set of G if D is a dominating set and the set of vertices of D spans a tadpole graph T m , n where m ≥ 3 , n ≥ 1. In this paper, we find the tadpole domination number of cartesian product of certain graphs, namely, paths, cycles and complete graphs. Also the tadpole domination number for the Mycielskian of cycles and paths is obtained. [ABSTRACT FROM AUTHOR]

Topological indices are numeric quantities that describes the topology of molecular structure in mathematical chemistry. One of these indices is the neighborhood version of the hyper Zagreb index, HMN. The neighborhood version of the hyper Zagreb index is expressed as the sum over all pairs of adjacent vertices a and b of the terms [δG(a) + δG(b)]2, where δG(a) is the neighborhood degree sum of the vertex a which is the sum of degrees of all of its neighboring vertices. In this paper, we show that over all simple connected graphs, the path graph Pn has the minimum value of HMN and the complete graph Kn has the maximum value of HMN. Also, we give the minimum value of this index within the set of trees with given vertices number and maximum vertex degree and specify the minimal trees. [ABSTRACT FROM AUTHOR]

Let Kn denote a complete graph on n vertices and Sk denote a complete bipartite graph K1,k. A Bowtie Bl is a graph formed by the union of two cycles Cn and Cm intersecting at a common vertex. A decomposition of a graph G is a collection of edge-disjoint subgraphs H, such that every edge of G belongs to exactly one H. Given non-isomorphic subgraphs H1 and H2 of G, a (H1,H2) — multi-decomposition of G is the decomposition of G into a copies of H1 and b copies of H2, such that aH1 ⊕ bH2 = G, for some integers a,b ≥ 0. In this paper, the multi-decomposition of Kn into Sk and Bl has been investigated and obtained a necessary and sufficient condition when k = l = 6. It is proved that for a given positive integer n, Kn can be decomposed into a copies of S6 and b copies of B6 for some pair of non-negative integers (a,b) if and only if 6(a + b) = n 2, for all n ≥ 9. [ABSTRACT FROM AUTHOR]

Let R be a commutative ring with identity and I be an ideal of R. The zero-divisor graph of R with respect to I, denoted by ΓI(R), is the graph whose vertices are the set {x ∈ R∖I|xy ∈ I for some y ∈ R∖I} with distinct vertices x and y are adjacent if and only if xy ∈ I. The cozero-divisor graph Γ′(R) of R is the graph whose vertices are precisely the non-zero, non-unit elements of R and two distinct vertices x and y are adjacent if and only if x∉yR and y∉xR. In this paper, we introduced and investigated a new generalization of the cozero-divisor graph Γ′(R) of R denoted by ΓI″(R). In fact, ΓI″(R) is a dual notion of ΓI(R). [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]

We address in this paper the connected p -median problem on complete multi-layered graphs. We first solve the corresponding 1-median problem on the underlying graph in linear time based on the structure of the induced path. For p ≥ 2 , we prove that the connected p -median contains at least one vertex in the layered set corresponding to the 1-median or its adjacent vertices in the induced path. Then, we develop an O (n log n) algorithm that solves the problem on a complete multi-layered graph with n vertices. [ABSTRACT FROM AUTHOR]

For a d -regular graph G , an edge-signing σ : E (G) → { − 1 , 1 } is called a good signing if the absolute eigenvalues of its adjacency matrix are at most 2 d − 1 . Bilu and Linial conjectured that for each regular graph there exists a good signing. In this paper, by using the concept of "Equitable Partition", we prove the conjecture for some cases. We show how to find out a good signing for special complete graphs and lexicographic product of two graphs. In particular, if there exist two good signings for graph G , then we can find a good signing for a 2-lift of G. [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]

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]

Let G = (V , E) be a simple, finite, undirected, and connected graph with vertex set V (G) and edge set E (G). A bijection l : V (G) → { 1 , 2 , ... , k } is label function l if opt (l) = min { max (l i) : l i   v e r t e x   i r r e g u l a r   l a b e l i n g } and for any two adjacent vertices u and v , w (u) ≠ w (v) where w (u) = ∑ v ∈ N (u) l (v) and N (u) is set of vertices adjacent to v. w is called local irregularity vertex coloring. The minimum cardinality of local irregularity vertex coloring of G is called chromatic number local irregular denoted by χ l i s (G). In this paper, we verify the exact values of volcano, broom, parachute, double broom and complete multipartite graphs. [ABSTRACT FROM AUTHOR]

A matrix with entries 0 , 1 is graphical if it is symmetric and all its diagonal entries are zero. Let G 1 , G 2 and G 3 be graphs defined on the same set of vertices. The graph G 3 is said to be the matrix product of graphs G 1 and G 2 , if A (G 1) A (G 2) = A (G 3) , where A (G i) is the adjacency matrix of the graph G i , 1 ≤ i ≤ 3. In such a case, we say that G 1 and G 2 are companions of each other. The main purpose of this paper is to design an algorithm to check whether a given graph G has a companion. We derive conditions on n and m so that the generalized wheel graph, denoted by W m , n , has a companion and also show that the m th power of the path graph P n has no companion. Finally, we indicate a possible application of the algorithm in a problem of coloring of edges of the complete graph K n . [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]

Embeddings are often viewed as a high-level representation of systematic methods to simulate an algorithm designed for one kind of parallel machine on a different network structure and/or techniques to distribute data/program variables to achieve optimum use of all available processors. A topological index is a numeric quantity of a molecule that is mathematically derived in an unambiguous way from the structural graph of a molecule. In theoretical chemistry, distance-based molecular structure descriptors are used for modeling physical, pharmacologic, biological and other properties of chemical compounds. Arguably, the best known of these indices is the Wiener index, defined as the sum of all distances between distinct vertices. In this paper, we have obtained the exact wirelength of embedding Cartesian products of complete graphs into a Cartesian product of paths and cycles, and generalized book. In addition to that, we have found the Wiener index of generalized book and the relation between the Wiener index and wirelength of an embedding, which solves (partially) an open problem proposed in Kumar et al. [K. J. Kumar, S. Klavžar, R. S. Rajan, I. Rajasingh and T. M. Rajalaxmi, An asymptotic relation between the wirelength of an embedding and the Wiener index, submitted to the journal]. [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]

The sum-connectivity index of a graph G is defined as the sum of weights 1 / d u + d v over all edges u v of G , where d u and d v are the degrees of the vertices u and v in G , respectively. The graphs called two-trees are defined by recursion. The smallest two-tree is the complete graph on two vertices. A two-tree on n + 1 vertices (where n ≥ 2) is obtained by adding a new vertex adjacent to the two end vertices of one edge in a two-tree on n vertices. In this paper, the sharp lower bound on the sum-connectivity index of two-trees is presented, and the two-trees with the minimum and the second minimum sum-connectivity, respectively, are determined. [ABSTRACT FROM AUTHOR]

Let be a simple connected graph consisting of n vertices and m edges. In a proper l -coloring, an r -dynamic coloring of a graph is one in which each vertex's neighbors are provided at least min { r , d (k) } different colors. The r -dynamic chromatic number of graph , given as χ r () , is the minimal l such that the graph has r -dynamic l coloring of . In this study, we combine a few common graphs to provide the r -dynamic coloring of the subdivision-edge neighborhood corona of path graph P s and star graph K 1 , s . These graphs include path graph P q , cycle graph C q , complete graph K q , star graph K 1 , q , and double star graph K 1 , q , q . [ABSTRACT FROM AUTHOR]

We propose a modification of the First-Fit algorithm in which we forbid the use of the most frequently used color. We provide some lower bound of the performance ratio χ FF w P (G) ω (G) on the family of interval graphs G , where χ FF w P (G) denotes the number of used colors by the modified version of the First-Fit algorithm and ω (G) is the number of vertices in the largest complete subgraph in G. We also compare the modification with the usual First-Fit algorithm on some experimental data. [ABSTRACT FROM AUTHOR]

Suppose F is a subgraph of a convex complete graph K n and F contains no boundary edge of K n and | E (F) | ≤ n − 1. We determine necessary and sufficient conditions on F such that K n − F admits a triangulation. For | E (F) | ≥ n , we investigate the possibility of placing F in K n such that K n − F admits a triangulation for certain families of graphs F. These results are then applied to determine the convex skewness of the convex graphs of the form K n − F. [ABSTRACT FROM AUTHOR]