27 results
Search Results
2. On the study of rainbow antimagic connection number of comb product of tree and complete bipartite graph.
- Author
-
Septory, B. J., Susilowati, L., Dafik, D., and Venkatachalam, M.
- Subjects
BIJECTIONS ,BIPARTITE graphs ,GRAPH coloring ,COMPLETE graphs ,RAINBOWS ,GRAPH labelings - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
3. The Italian domination numbers of some generalized Sierpiński networks.
- Author
-
Liang, Zhipeng, Wu, Liyun, and Yang, Jinxia
- Subjects
DOMINATING set ,BIPARTITE graphs ,MATHEMATICAL induction ,COMPLETE graphs - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
4. Distance energy change of complete split graph due to edge deletion.
- Author
-
Banerjee, Subarsha
- Subjects
GRAPH connectivity ,INDEPENDENT sets ,ABSOLUTE value ,EIGENVALUES ,COMPLETE graphs ,BIPARTITE graphs - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
5. Eternal feedback vertex sets: A new graph protection model using guards.
- Author
-
Dyab, Nour, Lalou, Mohammed, and Kheddouci, Hamamache
- Subjects
DOMINATING set ,INDEPENDENT sets ,BIPARTITE graphs ,COMPLETE graphs - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
6. Fractional local edge dimensions of a graph.
- Author
-
Goshi, Nosheen, Zafar, Sohail, and Rashid, Tabasam
- Subjects
PETERSEN graphs ,INTEGER programming ,COMPLETE graphs - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
7. On a generalization of Roman domination with more legions.
- Author
-
Khosh-Ahang Ghasr, Fahimeh
- Subjects
DOMINATING set ,BIPARTITE graphs ,COMPLETE graphs ,GENERALIZATION ,ROMANS - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
8. The crossing number of Cartesian product of sunlet graph with path and complete bipartite graph.
- Author
-
Alhajjar, Mhaid, Panda, Amaresh Chandra, and Behera, Siva Prasad
- Subjects
BIPARTITE graphs ,COMPLETE graphs - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
9. On k-restricted connectivity of direct product of graphs.
- Author
-
Cheng, Huiwen, Varmazyar, Rezvan, and Ghasemi, Mohsen
- Subjects
BIPARTITE graphs ,GRAPH connectivity ,COMPLETE graphs - Abstract
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]
- Published
- 2023
- Full Text
- View/download PDF
10. Tadpole domination number of graphs.
- Author
-
Prebhath, Vinny Susan and Sangeetha, V.
- Subjects
DOMINATING set ,COMPLETE graphs ,TADPOLES - Abstract
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]
- Published
- 2023
- Full Text
- View/download PDF
11. The neighborhood version of the hyper Zagreb index of trees.
- Author
-
Dehgardi, Nasrin
- Subjects
- *
MOLECULAR connectivity index , *GRAPH connectivity , *COMPLETE graphs , *MOLECULAR structure , *NEIGHBORHOODS - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
12. Multi-decomposition of complete graphs into stars and bowties of size 6.
- Author
-
Hemalatha, P. and Ramya, K.
- Subjects
- *
COMPLETE graphs , *SUBGRAPHS , *INTEGERS - Abstract
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]- Published
- 2024
- Full Text
- View/download PDF
13. A generalization of the cozero-divisor graph of a commutative ring.
- Author
-
Farshadifar, F.
- Subjects
- *
COMPLETE graphs , *GRAPH connectivity , *GENERALIZATION , *DIVISOR theory - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
14. Partially balanced incomplete block (PBIB)-designs arising from diametral paths in some strongly regular graphs.
- Author
-
Huilgol, Medha Itagi and Vidya, M. D.
- Subjects
REGULAR graphs ,PETERSEN graphs ,BIPARTITE graphs ,COMPLETE graphs - Abstract
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]
- Published
- 2023
- Full Text
- View/download PDF
15. The connected p-median problem on complete multi-layered graphs.
- Author
-
Nguyen, Kien Trung, Nhan, Tran Hoai Ngoc, Teh, Wen Chean, and Hung, Nguyen Thanh
- Subjects
COMPLETE graphs ,CHARTS, diagrams, etc. ,PROBLEM solving - Abstract
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]
- Published
- 2022
- Full Text
- View/download PDF
16. Equitable partition for some Ramanujan graphs.
- Author
-
Alinejad, M., Erfanian, A., and Fulad, S.
- Subjects
REGULAR graphs ,COMPLETE graphs ,EIGENVALUES ,LOGICAL prediction - Abstract
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]
- Published
- 2023
- Full Text
- View/download PDF
17. Detour global domination for splitting graph.
- Author
-
Jayasekaran, C. and Ashwin Prakash, S. V.
- Subjects
DOMINATING set ,BIPARTITE graphs ,COMPLETE graphs - Abstract
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]
- Published
- 2023
- Full Text
- View/download PDF
18. Indicated coloring of the Mycielskian of some families of graphs.
- Author
-
Francis, P.
- Subjects
GRAPH coloring ,BIPARTITE graphs ,COMPLETE graphs ,FIXED effects model ,COLORS - Abstract
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]
- Published
- 2023
- Full Text
- View/download PDF
19. On the local irregularity vertex coloring of volcano, broom, parachute, double broom and complete multipartite graphs.
- Author
-
Kristiana, Arika Indah, Nikmah, Nafidatun, Dafik, Alfarisi, Ridho, Hasan, M. Ali, and Slamin
- Subjects
BROOMS & brushes ,COMPLETE graphs ,GRAPH connectivity ,GRAPH coloring ,PARACHUTING ,PARACHUTES ,BIJECTIONS - Abstract
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]
- Published
- 2022
- Full Text
- View/download PDF
20. Algorithm to check the existence of H for a given G such that A(G)A(H) is graphical.
- Author
-
Bhat, K. Arathi, Sudhakara, G., and Vinay, M.
- Subjects
MATRIX multiplications ,ALGORITHMS ,CHARTS, diagrams, etc. ,COMPLETE graphs - Abstract
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]
- Published
- 2022
- Full Text
- View/download PDF
21. Weak Roman subdivision number of graphs.
- Author
-
Roushini Leely Pushpam, P. and Srilakshmi, N.
- Subjects
CHARTS, diagrams, etc. ,DOMINATING set ,BIPARTITE graphs ,COMPLETE graphs ,ROMANS - Abstract
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]
- Published
- 2022
- Full Text
- View/download PDF
22. Wiener index via wirelength of an embedding.
- Author
-
Nandini, G. Kirithiga, Rajan, R. Sundara, Rajalaxmi, T. M., Shantrinal, A. Arul, Husain, Sharifah Kartini Said, and Hasni, Roslan
- Subjects
MOLECULAR connectivity index ,PHYSICAL & theoretical chemistry ,COMPLETE graphs ,MOLECULAR structure ,CHEMICAL properties ,PARALLEL algorithms - Abstract
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]
- Published
- 2022
- Full Text
- View/download PDF
23. On the Roman {2}-domatic number of graphs.
- Author
-
Giahtazeh, A., Maimani, H. R., and Iranmanesh, A.
- Subjects
DOMINATING set ,BIPARTITE graphs ,COMPLETE graphs ,ROMANS - Abstract
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]
- Published
- 2021
- Full Text
- View/download PDF
24. Two-tree graphs with minimum sum-connectivity index.
- Author
-
Jahanbani, A.
- Subjects
COMPLETE graphs ,MAXIMA & minima - Abstract
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]
- Published
- 2021
- Full Text
- View/download PDF
25. r-Dynamic chromatic number of subdivision-edge neighborhood corona of certain graph families.
- Author
-
Kalaiselvi, K., Mohanapriya, N., and Aparna, V.
- Subjects
SUBDIVISION surfaces (Geometry) ,BINARY stars ,GRAPH coloring ,RAMSEY numbers ,COMPLETE graphs ,GRAPH connectivity ,FAMILIES - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
26. On-line interval graphs coloring — Modification of the First-Fit algorithm and its performance ratio.
- Author
-
Bieganowski, Bartosz
- Subjects
GRAPH coloring ,COMPLETE graphs ,ALGORITHMS - Abstract
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]
- Published
- 2022
- Full Text
- View/download PDF
27. Triangulability of convex graphs and convex skewness.
- Author
-
Ali, Niran Abbas, Chia, Gek L., Trao, Hazim Michman, and Kilicman, Adem
- Subjects
COMPLETE graphs ,TRIANGULATION ,CHARTS, diagrams, etc. - Abstract
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]
- Published
- 2022
- Full Text
- View/download PDF
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.