Next Article in Journal
How Asymmetries Evolved: Hearts, Brains, and Molecules
Previous Article in Journal
Comparison between Single-Phase Flow Simulation and Multiphase Flow Simulation of Patient-Specific Total Cavopulmonary Connection Structures Assisted by a Rotationally Symmetric Blood Pump
Previous Article in Special Issue
Bounds on the Arithmetic-Geometric Index
 
 
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Article

Cactus Graphs with Maximal Multiplicative Sum Zagreb Index

1
Department of Mathematics, Mongolian National University of Education, Baga toiruu-14, Ulaanbaatar 210648, Mongolia
2
College of Mathematics and Physics, Inner Mongolia University for Nationalities, Tongliao 028000, China
*
Authors to whom correspondence should be addressed.
Submission received: 10 March 2021 / Revised: 10 May 2021 / Accepted: 17 May 2021 / Published: 20 May 2021
(This article belongs to the Special Issue Analytical and Computational Properties of Topological Indices)

Abstract

:
A connected graph G is said to be a cactus if any two cycles have at most one vertex in common. The multiplicative sum Zagreb index of a graph G is the product of the sum of the degrees of adjacent vertices in G. In this paper, we introduce several graph transformations that are useful tools for the study of the extremal properties of the multiplicative sum Zagreb index. Using these transformations and symmetric structural representations of some cactus graphs, we determine the graphs having maximal multiplicative sum Zagreb index for cactus graphs with the prescribed number of pendant vertices (cut edges). Furthermore, the graphs with maximal multiplicative sum Zagreb index are characterized among all cactus graphs of the given order.
MSC:
05C35; 05C09; 92E10; 05C07

1. Introduction

In chemical graph theory and mathematical chemistry, a degree-based topological index, also known as a connectivity index, is a type of molecular descriptor calculated based on the molecular graph of a chemical compound. Symmetry has played an important role in chemical graph theory; in recent years, this role has increased in the study of topological indices. Let G = ( V , E ) be a graph with vertex set V ( G ) and edge set E ( G ) . The degree of the vertex v in G is denoted by d G ( v ) . The oldest and most well-known graph invariants are the first Zagreb index M 1 and the second Zagreb index M 2 of a graph G, and they are defined as
M 1 ( G ) = u V ( G ) ( d G ( u ) ) 2 and M 2 ( G ) = u v E ( G ) d G ( u ) d G ( v ) .
These indices were first introduced about fifty years ago by Gutman and Trinajstić [1]; for details of the mathematical studies and chemical applications on the Zagreb indices, see [2,3,4,5,6]. Moreover, the relation and comparison between them were studied in [7,8,9,10,11,12,13].
Todeschini and Consonni [14] proposed the multiplicative versions of the classical Zagreb indices M 1 and M 2 , which are defined as
Π 1 ( G ) = u V ( G ) d G ( u ) 2 and Π 2 ( G ) = u v E ( G ) d G ( u ) d G ( v ) .
Gutman [15] studied these two graphical invariants and called them first and second multiplicative Zagreb indices, respectively. Recent results related to the multiplicative Zagreb indices and their other versions can be found in [16,17].
Eliasi, Iranmanesh, and Gutman [18] introduced a new graphical invariant, which is the multiplicative version of the well-known first Zagreb index M 1 and called the multiplicative sum Zagreb index by Xu and Das [19]. The multiplicative sum Zagreb index is defined as follows:
Π 1 ( G ) = u v E ( G ) ( d G ( u ) + d G ( v ) ) .
Although Π 1 was introduced in 2012, it has been studied only to a limited extent for various classes of graphs. Elias, Iranmanesh, and Gutman [18] proved that among all connected graphs with a given order, the path has minimal Π 1 -value. They also determined the trees with the second minimal Π 1 -value. Xu and Das [19] characterized the extremal trees, unicyclic and bicyclic graphs with a given order with respect to the multiplicative sum Zagreb index. Azari and Iranmanesh [17] gave some lower bounds for the multiplicative sum Zagreb index of graph operations. Kazemi [20] studied the multiplicative Zagreb indices of molecular graphs with a tree structure. The extremal graphs with respect to the multiplicative sum Zagreb index for several classes of graphs were determined in [21].
A connected graph G is said to be a cactus if any two cycles have at most one vertex in common. For the class of cactus graphs, the graphs were characterized that have the extremal Zagreb indices [22], the difference between Zagreb indices [23], and multiplicative Zagreb indices [24]. Recently, Liu, Yao, and Das [25] characterized the extremal cactus graphs with respect to several well-known vertex degree-based graph invariants. A vertex of degree one is called pendent, and an edge incident with a pendent vertex is called pendent. For v V ( G ) , N G ( v ) denotes the set of neighbors of v. A cut edge in a graph G is an edge whose removal increases the number of connected components of G. For X E ( G ) , denote by G X the subgraph of G obtained from G by deleting all edges in X. For Y E ( G ¯ ) , denote by G + Y the supergraph of G obtained from G by adding all edges in Y, where G ¯ is a complement of G.
Denote by C n , k the class of cactus graphs of order n with k pendent vertices, and denote by C n k the class of cactus graphs of order n with k cut edges. This paper is organized as follows. In Section 2, we present several graph transformations that increase the Π 1 -value. In Section 3, by using these transformations, we determine the graphs that have maximal Π 1 -value in C n , k and C n k . Moreover, the graphs with maximal Π 1 -value are characterized among all cactus graphs of the given order.

2. Transformations

In this Section, we introduce several transformations that will be used in the proof of the main results of this paper. We begin by recalling the following two lemmas due to Xu and Das [19].
Lemma 1. 
([19]). Let G be a graph with u v E ( G ) . Then Π 1 ( G + u v ) > Π 1 ( G ) .
An edge contraction is an operation which removes an edge from a graph while simultaneously merging the two vertices that it previously joined.
Lemma 2. 
([19]). Let u v be a non-pendent cut edge of graph G. Denote by G = G · ( u v ) + u v the graph obtained by the contraction of u v onto the vertex u and adding a new pendent vertex v to u. Then Π 1 ( G ) < Π 1 ( G ) .
Transformation A. Let x 0 x 1 x 2 x l x 0 ( l 4 ) be a cycle of a connected graph G. If x 0 x 2 , x 0 x 3 E ( G ) then G = G x 2 x 3 + { x 0 x 2 , x 0 x 3 } (see Figure 1).
Lemma 3. 
Let G and G be the graphs depicted in Figure 1. Then Π 1 ( G ) < Π 1 ( G ) .
Proof. 
From the definition of G , we have d G ( v ) = d G ( v ) for all v V ( G ) { x 0 } . Then by the definition of Π 1 , we have
Π 1 ( G ) Π 1 ( G ) = ( d G ( x 0 ) + 2 + d G ( x 2 ) ) ( d G ( x 0 ) + 2 + d G ( x 3 ) ) d G ( x 2 ) + d G ( x 3 ) · v N G ( x 0 ) d G ( x 0 ) + 2 + d G ( v ) d G ( x 0 ) + d G ( v ) > 2 ( d G ( x 2 ) + d G ( x 3 ) ) d G ( x 2 ) + d G ( x 3 ) > 1
and it follows that Π 1 ( G ) < Π 1 ( G ) . □
Transformations B and C. Let x 0 x 1 x 2 x 3 x 0 and y 0 y 1 y 2 y 3 y 0 be cycles in connected graphs H 1 and H 2 , respectively ( x 0 x 2 E ( H 1 ) , y 0 y 2 E ( H 2 ) ). Let G be the graph obtained from H 1 and H 2 by identifying x 0 with y 0 and denote this vertex x 0 (see Figure 2). Without loss of generality, we can assume that d G ( x 1 ) d G ( x 3 ) , d G ( y 1 ) d G ( y 3 ) , and d G ( x 1 ) d G ( y 1 ) . Let G = G { x 2 x 3 , y 2 y 3 } + { x 0 x 2 , x 0 y 2 , x 3 y 3 } and G = G { x 2 x 3 , y 2 y 3 , x 0 y 1 } + { x 0 x 2 , x 1 y 1 , x 1 y 2 , x 3 y 3 } (see Figure 2).
Lemma 4. 
Let G, G , and G be the graphs depicted in Figure 2.
(i)
If d G ( x 2 ) d G ( x 3 ) then Π 1 ( G ) < Π 1 ( G ) .
(ii)
If d G ( x 2 ) < d G ( x 3 ) then Π 1 ( G ) < Π 1 ( G ) .
Proof. 
Set d G ( x 0 ) = a 4 , d G ( x i ) = a i , and d G ( y i ) = b i , i = 1 , 2 , 3 .
(i)
Then d G ( x 0 ) = a + 2 and d G ( v ) = d G ( v ) for all v V ( G ) { x 0 } . Therefore, we have
Π 1 ( G ) Π 1 ( G ) = ( a + 2 + a 2 ) ( a + 2 + b 2 ) ( a 3 + b 3 ) ( a 2 + a 3 ) ( b 2 + b 3 ) · v N G ( x 0 ) a + 2 + d G ( v ) a + d G ( v ) > ( a 2 + b 2 + a 2 b 2 ) ( a 3 + b 3 ) a 2 b 2 + a 2 b 3 + a 3 b 2 + a 3 b 3 > 1
since a 2 a 3 > 1 and b 2 > 1 .
(ii)
Then d G ( x 1 ) = a 1 + 2 and d G ( v ) = d G ( v ) for all v V ( G ) { x 1 } . From the assumption, we have a 1 b 1 b 3 and hence we get a 1 + 2 + b 2 > b 2 + b 3 . Therefore, we have
Π 1 ( G ) Π 1 ( G ) = ( a 1 + 2 + b 1 ) ( a 1 + 2 + b 2 ) ( a + a 2 ) ( a 3 + b 3 ) ( a + b 1 ) ( a 2 + a 3 ) ( b 2 + b 3 ) · v N G ( x 1 ) a 1 + 2 + d G ( v ) a 1 + d G ( v ) > ( a 1 + b 1 ) ( a + a 2 ) ( a 3 + b 3 ) a a 2 + a a 3 + a 2 b 1 + a 3 b 1 > a a 1 + a a 3 + a 2 b 1 + a 3 b 1 a a 2 + a a 3 + a 2 b 1 + a 3 b 1 > 1
since a 2 < a 3 a 1 and a 1 b 1 > 1 . □
Transformation D. Let u 1 u 2 u 3 u 4 u 1 and v 1 v 2 v 3 v 4 v 1 be two disjoint cycles of length 4 in a connected graph G. Suppose that u 1 u 3 , v 1 v 3 , u 1 v 2 , u 2 v 2 E ( G ) and
d G ( u 1 ) = max { d G ( u 1 ) , , d G ( u 4 ) , d G ( v 1 ) , , d G ( v 4 ) } .
Let G = G { u 2 u 3 , v 1 v 2 , v 2 v 3 } + { u 1 u 3 , v 1 v 3 , u 1 v 2 , u 2 v 2 } (see Figure 3).
Lemma 5. 
Let G and G be the graphs depicted in Figure 3. Then Π 1 ( G ) < Π 1 ( G ) .
Proof. 
Set d G ( u i ) = a i , d G ( v i ) = b i , i = 1 , 2 , 3 . Then d G ( u 1 ) = a 1 + 2 and d G ( w ) = d G ( w ) for all w V ( G ) { u 1 } . Therefore, we have
Π 1 ( G ) Π 1 ( G ) = ( a 1 + 2 + a 3 ) ( a 1 + 2 + b 2 ) ( b 1 + b 3 ) ( a 2 + b 2 ) ( a 2 + a 3 ) ( b 1 + b 2 ) ( b 2 + b 3 ) · x N G ( u 1 ) a 1 + 2 + d G ( x ) a 1 + d G ( x ) > ( a 1 + 2 + a 3 ) ( a 1 + 2 + b 2 ) ( b 1 + b 3 ) ( a 2 + b 2 ) ( a 2 + a 3 ) ( b 1 + b 2 ) ( b 2 + b 3 ) > ( b 1 + b 3 ) ( a 2 + b 2 ) b 2 + b 3 > 1
since a 1 a 2 , a 1 b 1 and a 2 , b 1 , b 2 , b 3 2 . □
Transformation E. Let u v be an edge in a connected graph G such that d G ( u ) 3 , d G ( v ) 3 and N G ( u ) N G ( v ) = . Assume that y 1 N G ( v ) is the maximum degree vertex in N G ( u ) N G ( v ) { u , v } . Let G = ( G v y 1 ) · ( u v ) + u v + v y 1 be the graph obtained by the contraction of u v onto the vertex u and adding a new vertex v of degree two to u and y 1 (see Figure 4).
Lemma 6. 
Let G and G be the graphs depicted in Figure 4. Then Π 1 ( G ) < Π 1 ( G ) .
Proof. 
Set A = N G ( u ) { v } , B = N G ( v ) { u , y 1 } and | A | = a , | B | = b . Then d G ( u ) = a + 1 , d G ( v ) = b + 2 , d G ( u ) = a + b + 1 , d G ( v ) = 2 , and d G ( w ) = d G ( w ) for all w V ( G ) { u , v } . Let x 1 and y 2 be maximum degree vertices in A and B, respectively. By the definition of Π 1 and Bernoulli’s inequality, we have
Π 1 ( G ) Π 1 ( G ) = x A a + b + 1 + d G ( x ) a + 1 + d G ( x ) · y B a + b + 1 + d G ( y ) b + 2 + d G ( y ) · 2 + d G ( y 1 ) b + 2 + d G ( y 1 ) 1 + b a + 1 + d G ( x 1 ) a · 1 + a 1 b + 2 + d G ( y 2 ) b · 2 + d G ( y 1 ) b + 2 + d G ( y 1 ) 1 + a b a + 1 + d G ( x 1 ) · 1 + a b b b + 2 + d G ( y 2 ) · 2 + d G ( y 1 ) b + 2 + d G ( y 1 )
since d G ( x 1 ) , d G ( y 2 ) are maximum in A and B, respectively. Denote d G ( x 1 ) + 1 = s , d G ( y 2 ) + 2 = r and d G ( y 1 ) + 2 = t . Then we have t > s and t r since d G ( y 1 ) is maximum in N G ( u ) N G ( v ) { u , v } . From (1), we have
Π 1 ( G ) Π 1 ( G ) ( a b + a + s ) ( a b + r ) t ( a + s ) ( b + r ) ( b + t ) = a 2 b 2 t + a 2 b t + a b s t + a b r t + a r t + s r t a b 2 + a b t + a b r + a r t + s b 2 + b s t + s r b + s r t > 1
since a 2 b 2 t 2 a b 2 t > a b 2 + b 2 t > a b 2 + b 2 s , a b s t 2 b s t b s t + b s r and a b r t > a b ( r + t ) . Hence, we get Π 1 ( G ) < Π 1 ( G ) . □
Transformation F. Let u v be an edge in a connected graph G such that d G ( u ) 3 , d G ( v ) 3 and N G ( u ) N G ( v ) = { w } . Let G = ( G v w ) · u v + { u v , v w } be the graph obtained by the contraction of u v in G v w onto the vertex u and adding a new vertex v of degree two to u and w (see Figure 5).
Lemma 7. 
Let G and G be the graphs in Figure 5. If d G ( u ) is the maximum degree in N G ( v ) { w } , then Π 1 ( G ) < Π 1 ( G ) .
Proof. 
Clearly, d G ( z ) = d G ( z ) for all z V ( G ) { u , v } . Set A = N G ( u ) { v , w } , B = N G ( v ) { u , w } and | A | = a , | B | = b , d G ( w ) = c 2 . Then d G ( u ) = a + 2 , d G ( v ) = b + 2 and d G ( u ) = a + b + 2 , d G ( v ) = 2 . Let d G ( x 1 ) and d G ( y 1 ) be the maximum degrees in A and B, respectively. By the definition of Π 1 and Bernoulli’s inequality, we have
Π 1 ( G ) Π 1 ( G ) = c ( a + b + c ) ( b + c ) ( a + c ) · x A a + b + 2 + d G ( x ) a + 2 + d G ( x ) · y B a + b + 2 + d G ( y ) b + 2 + d G ( y ) c ( a + b + c ) ( b + c ) ( a + c ) · 1 + b a + 2 + d G ( x 1 ) a · 1 + a b + 2 + d G ( y 1 ) b c ( a + b + c ) ( b + c ) ( a + c ) · 1 + a b a + 2 + d G ( x 1 ) · 1 + a b b + 2 + d G ( y 1 ) .
Denote d G ( x 1 ) + 2 = p and d G ( y 1 ) + 2 = q . Then from (2), we get
Π 1 ( G ) Π 1 ( G ) ( a b + a + p ) ( a b + b + q ) ( a c + b c + c 2 ) ( a + p ) ( b + q ) ( a b + a c + b c + c 2 ) = a b c ( a b + a + b + p + q ) ( a + b + c ) + ( a + p ) ( b + q ) ( a c + b c + c 2 ) ( a b + a q + b p + p q ) a b + ( a + p ) ( b + q ) ( a c + b c + c 2 ) > a b ( a b + a q + b p + ( a + c ) p ) + ( a + p ) ( b + q ) ( a c + b c + c 2 ) ( a b + a q + b p + p q ) a b + ( a + p ) ( b + q ) ( a c + b c + c 2 ) 1
since a + c a + 4 = d G ( u ) + 2 d G ( y 1 ) + 2 = q , and the proof is complete. □

3. Cactus Graphs with Maximal Π 1 -Value

In this Section, we determine the graphs with maximal Π 1 -value. A tree containing exactly two non-pendent vertices is called a double star.
Lemma 8. 
Let G be a cactus graph different from a double star. If Π 1 ( G ) is maximum in C n , k then there is no non-pendent cut edge. Moreover, the length of all k pendent paths in G is one.
Proof. 
Suppose there exists a non-pendent cut edge u v in G. Then d G ( u ) 2 and d G ( v ) 2 , and it follows that there exist vertices w 1 ( w 1 v ) and w 2 ( w 2 u ) such that u w 1 , v w 2 E ( G ) . If we cannot choose w 1 and w 2 such that d G ( w 1 ) 2 or d G ( w 2 ) 2 then G is isomorphic to a double star and it is a contradiction. Therefore we can assume that d G ( w 1 ) 2 . First suppose that d G ( u ) = 2 . Clearly, v w 1 E ( G ) , since u v is a cut edge of G. Then, since the path w 1 u v has no common edge with any cycle in G, we have G + w 1 v C n , k and it follows that
Π 1 ( G ) < Π 1 ( G + v w 1 )
by Lemma 1. This contradicts the fact that Π 1 ( G ) is maximum in C n , k .
Now suppose that d G ( u ) 3 and d G ( v ) = 2 . If d G ( w 2 ) 2 then G + w 2 u C n , k and again it follows that Π 1 ( G ) < Π 1 ( G + v w 1 ) by Lemma 1. Let now d G ( w 2 ) = 1 . Consider G 1 = G { u w 1 , v w 2 } + { u w 2 , w 1 w 2 } . Then, G 1 C n , k . By the definition of Π 1 , we have
Π 1 ( G 1 ) Π 1 ( G ) = ( d G ( u ) + 1 ) ( d G ( u ) + 2 ) ( d G ( w 1 ) + 2 ) 3 ( d G ( u ) + 2 ) ( d G ( u ) + d G ( w 1 ) ) = ( d G ( u ) 2 ) ( d G ( w 1 ) 1 ) + 3 ( d G ( u ) + d G ( w 1 ) ) 3 ( d G ( u ) + d G ( w 1 ) ) > 1
since d G ( u ) > 2 and d G ( w 1 ) > 1 . It follows that Π 1 ( G ) < Π 1 ( G 1 ) , and we get a contradiction. Hence we have d G ( u ) 3 and d G ( v ) 3 . Denote by y 1 the maximum degree vertex in N G ( u ) N G ( v ) { u , v } . Without loss of generality we can assume that y 1 N G ( v ) { u } . If G = ( G v y 1 ) · ( u v ) + u v + v y 1 is the graph obtained from G by Transformation E (see Figure 4), then we have G C n , k and Π 1 ( G ) < Π 1 ( G ) by Lemma 6. This is also a contradiction. Clearly, the length of any pendent path is one, since there is no non-pendent cut edge. Hence, the proof is complete. □
Lemma 9. 
Let G be a cactus graph with maximum multiplicative sum Zagreb index in C n , k . Then, the length of any cycle in G is at most four. Moreover, the number of cycles of length four in G is at most one.
Proof. 
Suppose there exists a cycle x 0 x 1 x 2 x l x 0 in G of length at least five ( l 4 ). Since G is a cactus graph, we have x 0 x 2 , x 0 x 3 E ( G ) . If G 1 = G x 2 x 3 + { x 0 x 2 , x 0 x 3 } is the graph obtained from G by Transformation A, then G 1 C n , k and Π 1 ( G ) < Π 1 ( G 1 ) by Lemma 3. This is a contradiction. Hence, we conclude that the length of any cycle in G is at most four.
Now suppose that there are two cycles of length four in G. If they have a common vertex x 0 , then we call them x 0 x 1 x 2 x 3 x 0 and x 0 y 1 y 2 y 3 x 0 . Without loss of generality, we can assume that d G ( x 1 ) d G ( x 3 ) , d G ( y 1 ) d G ( y 3 ) , and d G ( x 1 ) d G ( y 1 ) . Let G = G { x 2 x 3 , y 2 y 3 } + { x 0 x 2 , x 0 y 2 , x 3 y 3 } and G = G { x 2 x 3 , y 2 y 3 , x 0 y 1 } + { x 0 x 2 , x 1 y 1 , x 1 y 2 , x 3 y 3 } be the graphs obtained from G by Transformations B and C (see Figure 2). Then G , G C n , k , and Π 1 ( G ) < max { Π 1 ( G ) , Π 1 ( G ) } by Lemma 4. This contradicts the fact that Π 1 ( G ) is maximal in C n , k . If the two cycles of length four are disjoint then we call them u 1 u 2 u 3 u 4 u 1 and v 1 v 2 v 3 v 4 v 1 , where d G ( u 1 ) = max { d G ( u 1 ) , , d G ( u 4 ) , d G ( v 1 ) , , d G ( v 4 ) } . Let v 2 be the farthest vertex from u 1 . Since G is a cactus graph and v 2 is the farthest vertex from u 1 , one can easily see that u 1 u 3 , v 1 v 3 , u 1 v 2 , u 2 v 2 E ( G ) . Let G 2 = G { u 2 u 3 , v 1 v 2 , v 2 v 3 } + { u 1 u 3 , u 1 v 2 , u 2 v 2 , v 1 v 3 } be the graph obtained from G by Transformation D (see Figure 3). Obviously, the cycles u 1 u 3 u 4 u 1 and v 1 v 3 v 4 v 1 have no common edge with any cycle in G 2 . Since G is a cactus graph and v 2 is the farthest vertex, each path from u 1 and u 2 to v 2 contains the vertex v 4 . Hence, the cycle u 1 u 2 v 2 u 1 has no common edge with any cycle in G 2 . Therefore, G 2 C n , k and Π 1 ( G ) < Π 1 ( G 2 ) by Lemma 5. This contradicts the fact that Π 1 ( G ) is maximal. This completes the proof. □
Let n and k be integers such that n 1 and k 0 . If n k is odd then denote by C n , k 1 the graph obtained from the star K 1 , n 1 by adding ( n k 1 ) / 2 independent edges. If n k is even then denote by C n , k 2 the graph obtained from C n 1 , k 1 by inserting a new vertex of degree two on a non-pendent edge of it. Then, clearly the graphs C n , k 1 and C n , k 2 belong to C n , k (see Figure 6).
Theorem 1. 
Let G be a graph in C n , k .
(i)
If n k is odd then Π 1 ( G ) 2 n k 1 n k ( n + 1 ) n k 1 and equality holds if and only if G is isomorphic to C n , k 1
(ii)
If n k is even and k n 2 , then Π 1 ( G ) 2 n k ( n 1 ) k n n k 2 and equality holds if and only if G is isomorphic to C n , k 2 .
(iii)
If k = n 2 then Π 1 ( G ) 3 n ( n 1 ) n 3 and equality holds if and only if G is isomorphic to a double star of order n with maximum degree n 2 .
Proof. 
Suppose that Π 1 ( G ) is maximum in C n , k . By Lemma 9, we have the length of all cycles, except one cycle of length four (if it exists) in G is three. Now we distinguish the following three cases.
(i)
Let n k be odd. Then G is different from a double star. Hence, G has no non-pendent cut edge by Lemma 8. If G has a cycle of length four then | E ( G ) | = k + 3 ( t 1 ) + 4 = k + 3 t + 1 , where t is the number of cycles in G since there is no non-pendent cut edge and the length of each cycle except one cycle of length four is three. If we delete an edge from each cycle of G, then the resulting graph is a spanning tree of G. Hence we have n 1 = k + 3 t + 1 t = k + 2 t + 1 , and this contradicts our assumption that n k is odd. Therefore, the length of all cycles of G is three.
Now, let u V ( G ) be a vertex of maximum degree. If all neighbors of u are pendent, then k = n 1 and G K 1 , n 1 C n , n 1 1 since G is connected. If k < n 1 then at least one cycle contains u. Let u v w u be any cycle in G, where d G ( v ) d G ( w ) . If d G ( v ) 3 then d G ( u ) 3 and d G ( u ) is the maximum in N G ( v ) { w } since d G ( u ) is maximum. If G is the graph obtained from G by Transformation F (see Figure 5) then G C n , k and Π 1 ( G ) < Π 1 ( G ) by Lemma 7. Hence we get d G ( v ) = d G ( w ) = 2 for any cycle u v w u in G. Therefore, all cycles have length three and contain vertex u , and all pendent vertices are adjacent to u. This means that G C n , k 1 .
(ii)
Let n k be even and k n 2 . Then G is different from a double star since k n 2 . Hence G has no non-pendent cut edge by Lemma 8. If all cycles of G have length three, then | E ( G ) | = k + 3 t , where t is the number of cycles in G since all cut edges are pendent. Similarly, as in the above case, we have n 1 = k + 3 t t = k + 2 t and a contradiction. Therefore, G has a unique cycle of length four, as C = u x 1 v x 2 u .
Without loss of generality, we assume that u is a vertex of maximum degree among all vertices in V ( C ) . If d G ( u ) = 2 , then n = 4 , k = 0 , and we are done. Therefore, we have d G ( u ) 3 . Now, suppose that d G ( x i ) 3 ( i = 1 or 2). One can easily see that N G ( u ) N G ( x i ) = . Consider the graph G obtained from G by Transformation F (see Figure 5). Then G C n , k and Π 1 ( G ) < Π 1 ( G ) by Lemma 7. This is a contradiction with the fact that Π 1 ( G ) is maximum in C n , k . Hence, we get d G ( x 1 ) = d G ( x 2 ) = 2 .
Let H be the connected component of G { x 1 u , x 2 u } which contains v. Let v 1 be a maximum degree vertex in H. Suppose that v 1 is different from v. Then there is a cycle v 1 y z v 1 that contains v 1 such that d G ( y ) 3 since G has no non-pendent cut edge. Clearly, d G ( v 1 ) 3 . Let G 1 = ( G y z ) · ( v 1 y ) + { v 1 y , y z } be the graph obtained from G by Transformation F. Then since d G ( v 1 ) is maximum in N G ( y ) N G ( z ) , we have Π 1 ( G ) < Π 1 ( G 1 ) by Lemma 7 and a contradiction. Therefore, v is a maximum degree vertex in H. If any neighbor of v has degree at least three in H then we also get a contradiction by Lemma 7. It follows that all cycles in H contain v and all pendent vertices in H are adjacent to v. Similarly, we can show that all cycles in H 1 contain u and all pendent vertices in H 1 are adjacent to u, where H 1 is the connected component of G { x 1 v , x 2 v } which contains u. Hence, G is isomorphic to the graph G ( a , b , k 1 , k 2 ) in Figure 7, where a + b = ( n k 4 ) / 2 and k 1 + k 2 = k .
Without loss of generality, we can assume that min { k 1 + 2 a , k 2 + 2 b } = k 2 + 2 b . Then, it is easy to calculate that
Π 1 ( G ( a , b , k 1 , k 2 ) ) = ( k 1 + 2 a + 2 + 1 ) k 1 · ( k 2 + 2 b + 2 + 1 ) k 2 · 4 a · 4 b · ( k 1 + 2 a + 2 + 2 ) 2 a + 2 · ( k 2 + 2 b + 2 + 2 ) 2 b + 2 .
Now we show that
Π 1 ( G ( a , b , k 1 , k 2 ) ) Π 1 ( G ( a + b , 0 , k 1 + k 2 , 0 ) ) = Π 1 ( C n , k 2 )
and equality holds if and only if b = k 2 = 0 .
If k 2 + 2 b = 0 then k 2 = 0 and b = 0 . Hence, we are done since a + b = ( n k 4 ) / 2 and k 1 + k 2 = k . Let now k 2 + 2 b 1 . From (3) and Bernoulli’s inequality, we obtain
Π 1 ( G ( a + b , 0 , k 1 + k 2 , 0 ) ) Π 1 ( G ( a , b , k 1 , k 2 ) ) = 4 k 1 + 2 a + 4 1 + k 2 + 2 b k 1 + 2 a + 3 k 1 1 + k 2 + 2 b k 1 + 2 a + 4 2 a + 1 · 4 k 2 + 2 b + 4 1 + k 1 + 2 a k 2 + 2 b + 3 k 2 1 + k 1 + 2 a k 2 + 2 b + 4 2 b + 1 4 k 1 + 2 a + 4 1 + k 1 ( k 2 + 2 b ) k 1 + 2 a + 3 1 + ( 2 a + 1 ) ( k 2 + 2 b ) k 1 + 2 a + 4 · 4 k 2 + 2 b + 4 1 + k 2 ( k 1 + 2 a ) k 2 + 2 b + 3 1 + ( 2 b + 1 ) ( k 1 + 2 a ) k 2 + 2 b + 4 > 4 k 1 + 2 a + 4 1 + k 1 ( k 2 + 2 b ) k 1 + 2 a + 3 + ( 2 a + 1 ) ( k 2 + 2 b ) k 1 + 2 a + 4 · 4 k 2 + 2 b + 4 1 + k 2 ( k 1 + 2 a ) k 2 + 2 b + 3 + ( 2 b + 1 ) ( k 1 + 2 a ) k 2 + 2 b + 4 > 4 k 1 + 2 a + 4 1 + ( k 1 + 2 a + 1 ) ( k 2 + 2 b ) k 1 + 2 a + 4 · 4 k 2 + 2 b + 4 1 + ( k 2 + 2 b + 1 ) ( k 1 + 2 a ) k 2 + 2 b + 4 4 k 1 + 2 a + 4 1 + 2 5 ( k 2 + 2 b ) · 4 k 2 + 2 b + 4 1 + 2 5 ( k 1 + 2 a ) > 1
since k 1 + 2 a + 1 k 1 + 2 a + 4 2 5 and k 2 + 2 b + 1 k 2 + 2 b + 4 2 5 . Hence we get G C n , k 2 .
(iii)
Let k = n 2 . Then G is isomorphic to a double star. Let u and v be the non-pendent vertices in G and d G ( u ) = p + 1 , d G ( v ) = q + 1 , where p + q + 2 = n . By Bernoulli’s inequality, we have
3 · p + q + 1 p + 2 p 3 · 1 + p ( q 1 ) p + 2 3 · ( 1 + 1 / 3 ( q 1 ) ) = q + 2
since p p + 2 1 3 . Hence we obtain 3 · ( p + q + 1 ) p ( p + 2 ) p ( q + 2 ) . Therefore, we have
Π 1 ( G ) = n ( p + 2 ) p ( q + 2 ) q 3 n ( p + q + 1 ) p ( q + 2 ) q 1 3 n ( p + q + 1 ) p + q 1 = 3 n ( n 1 ) n 3
and equality holds if and only if G is isomorphic to a double star of order n with maximum degree n 2 . The proof is complete. □
Now we characterize the graphs with maximum Π 1 -value among all cactus graphs of the given order.
Theorem 2. 
Let G be a cactus graph of order n.
(i)
If n is odd then Π 1 ( G ) 2 n 1 ( n + 1 ) n 1 and equality holds if and only if G is isomorphic to C n , 0 1 .
(ii)
If n is even then Π 1 ( G ) 2 n 2 n ( n + 1 ) n 2 and equality holds if and only if G is isomorphic to C n , 1 1 .
Proof. 
Let k be the number of pendent vertices in G.
(i)
Let n be odd. Then by Theorem 1, we get
Π 1 ( G ) 2 n k 1 n k ( n + 1 ) n k 1 if k is even , 2 n k ( n 1 ) k n n k 2 if k is odd 2 n 1 ( n + 1 ) n 1 2 n 1 ( n 1 ) n n 3 2 n 1 ( n + 1 ) n 1
and equality holds if and only if G is isomorphic to C n , 0 1 .
(ii)
Let n be even. Then by Theorem 1, we get
Π 1 ( G ) 2 n k 1 n k ( n + 1 ) n k 1 if k is odd , 2 n k ( n 1 ) k n n k 2 if k is even 2 n 2 n ( n + 1 ) n 2 2 n n n 2 2 n 2 n ( n + 1 ) n 2
and equality holds if and only if G is isomorphic to C n , 1 1 . □
From Lemma 2, the following lemma holds immediately.
Lemma 10. 
Let G be a cactus graph with maximum multiplicative sum Zagreb index in C n k . Then all cut edges of G are pendent.
The same argument as in the proof of Theorem 1 yields the following result.
Theorem 3. 
Let G be a graph in C n k .
(i)
If n k is odd then Π 1 ( G ) 2 n k 1 n k ( n + 1 ) n k 1 and equality holds if and only if G is isomorphic to C n , k 1 .
(ii)
If n k is even then Π 1 ( G ) 2 n k ( n 1 ) k n n k 2 and equality holds if and only if G is isomorphic to C n , k 2 .

Author Contributions

Investigation, C.X., B.H. and L.B.; writing—original draft preparation, C.X., B.H. and L.B.; writing—review and editing, C.X., B.H. and L.B.; funding acquisition, C.X. All authors have read and agreed to the published version of the manuscript.

Funding

This research was funded as a Scientific Research Project of Higher Education in the Inner Mongolia Autonomous Region (NJZY21439).

Institutional Review Board Statement

Not applicable.

Informed Consent Statement

Not applicable.

Data Availability Statement

Not applicable.

Acknowledgments

The authors are very grateful to the three anonymous referees for their valuable comments on our paper, which have considerably improved the presentation of this paper.

Conflicts of Interest

The authors declare no conflict of interest.

References

  1. Gutman, I.; Trinajstić, N. Graph theory and molecular orbitals. Total π-electron energy of alternant hydrocarbons. Chem. Phys. Lett. 1971, 17, 535–538. [Google Scholar] [CrossRef]
  2. Bollobás, B.; Erdös, P.; Sarkar, A. Extremal graphs for weights. Discret. Math. 1999, 200, 5–19. [Google Scholar] [CrossRef] [Green Version]
  3. Enteshari, M.; Taeri, B. Extremal Zagreb Indices of Graphs of Order n with p Pendent Vertices. MATCH Commun. Math. Comput. Chem. 2021, 86, 17–28. [Google Scholar]
  4. Filipovski, S. New Bounds for the First Zagreb index. MATCH Commun. Math. Comput. Chem. 2021, 85, 303–312. [Google Scholar]
  5. Selenge, T.; Horoldagva, B. Maximum Zagreb indices in the class of k-apex trees. Korean J. Math. 2015, 23, 401–408. [Google Scholar] [CrossRef] [Green Version]
  6. Wang, H.; Yuan, S. On the sum of squares of degrees and products of adjacent degrees. Discret. Math. 2016, 339, 1212–1220. [Google Scholar] [CrossRef]
  7. Buyantogtokh, L.; Horoldagva, B.; Das, K.C. On reduced second Zagreb index. J. Comb. Optim. 2020, 39, 776–791. [Google Scholar] [CrossRef]
  8. Das, K.C.; Gutman, I.; Horoldagva, B. Comparison between Zagreb indices and Zagreb coindices of trees. MATCH Commun. Math. Comput. Chem. 2012, 68, 189–198. [Google Scholar]
  9. Furtula, B.; Gutman, I.; Ediz, S. On difference of Zagreb indices. Discr. Appl. Math. 2014, 178, 83–88. [Google Scholar] [CrossRef]
  10. Horoldagva, B.; Das, K.C. On comparing Zagreb indices of graphs. Hacet. J. Math. Stat. 2012, 41, 223–230. [Google Scholar]
  11. Horoldagva, B.; Das, K.C. Sharp lower bounds for the Zagreb indices of unicyclic graphs. Turk. J. Math. 2015, 39, 595–603. [Google Scholar] [CrossRef]
  12. Horoldagva, B.; Das, K.C. On Zagreb indices of graphs. MATCH Commun. Math. Comput. Chem. 2021, 85, 295–301. [Google Scholar]
  13. Horoldagva, B.; Das, K.C.; Selenge, T. Complete characterization of graphs for direct comparing Zagreb indices. Discret. Appl. Math. 2016, 215, 146–154. [Google Scholar] [CrossRef]
  14. Todeschini, R.; Consonni, V. New local vertex invariants and molecular descriptors based on functions of the vertex degrees. MATCH Commun. Math. Comput. Chem. 2010, 64, 359–372. [Google Scholar]
  15. Gutman, I. Multiplicative Zagreb indices of trees. Bull. Soc. Math. Banja Luka 2011, 1, 13–19. [Google Scholar]
  16. Liu, J.; Zhang, Q. Sharp upper bounds for multiplicative Zagreb indices. MATCH Commun. Math. Comput. Chem. 2012, 68, 231–240. [Google Scholar]
  17. Azari, M.; Iranmanesh, A. Some inequalities for the multiplicative sum Zagreb index of graph operations. J. Math. Inequal 2015, 9, 727–738. [Google Scholar] [CrossRef]
  18. Eliasi, M.; Iranmanesh, A.; Gutman, I. Multiplicative version of the first Zagreb index. MATCH Commun. Math. Comput. Chem. 2012, 68, 217–230. [Google Scholar]
  19. Xu, K.; Das, K.C. Trees, unicyclic and bicyclic graphs extremal with respect to multipliactive sum Zagreb index. MATCH Commun. Math. Comput. Chem. 2012, 68, 257–272. [Google Scholar]
  20. Kazemi, R. Note on the multiplicative Zagreb indices. Discret. Appl. Math. 2016, 198, 147–154. [Google Scholar] [CrossRef]
  21. Horoldagva, B.; Xu, C.; Buyantogtokh, L.; Dorjsembe, S. Extremal graphs with respect to the multiplicative sum Zagreb index. MATCH Commun. Math. Comput. Chem. 2020, 84, 773–786. [Google Scholar]
  22. Li, S.; Yang, H.; Zhao, Q. Sharp bounds on Zagreb indices of cacti with k pendant vertices. Filomat 2012, 26, 1189–1200. [Google Scholar] [CrossRef] [Green Version]
  23. Li, S.; Zhang, L.; Zhang, M. On the extremal cacti of given parameters with respect to the difference of Zagreb indices. J. Comb. Optim. 2019, 38, 421–442. [Google Scholar] [CrossRef]
  24. Wang, S.; Wei, B. Multiplicative Zagreb indices of cacti. Discret. Math. Algorithms Appl. 2016, 8, 1650040. [Google Scholar] [CrossRef] [Green Version]
  25. Liu, M.; Yao, Y.; Das, K.C. Extremal results for cacti. Bull. Malays. Math. Sci. Soc. 2020, 43, 2783–2798. [Google Scholar] [CrossRef]
Figure 1. Transformation A.
Figure 1. Transformation A.
Symmetry 13 00913 g001
Figure 2. Transformations B and C.
Figure 2. Transformations B and C.
Symmetry 13 00913 g002
Figure 3. Transformation D.
Figure 3. Transformation D.
Symmetry 13 00913 g003
Figure 4. Transformation E.
Figure 4. Transformation E.
Symmetry 13 00913 g004
Figure 5. Transformation F.
Figure 5. Transformation F.
Symmetry 13 00913 g005
Figure 6. The graphs C 7 , 2 1 and C 8 , 2 2 .
Figure 6. The graphs C 7 , 2 1 and C 8 , 2 2 .
Symmetry 13 00913 g006
Figure 7. The graph G ( a , b , k 1 , k 2 ) .
Figure 7. The graph G ( a , b , k 1 , k 2 ) .
Symmetry 13 00913 g007
Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Share and Cite

MDPI and ACS Style

Xu, C.; Horoldagva, B.; Buyantogtokh, L. Cactus Graphs with Maximal Multiplicative Sum Zagreb Index. Symmetry 2021, 13, 913. https://0-doi-org.brum.beds.ac.uk/10.3390/sym13050913

AMA Style

Xu C, Horoldagva B, Buyantogtokh L. Cactus Graphs with Maximal Multiplicative Sum Zagreb Index. Symmetry. 2021; 13(5):913. https://0-doi-org.brum.beds.ac.uk/10.3390/sym13050913

Chicago/Turabian Style

Xu, Chunlei, Batmend Horoldagva, and Lkhagva Buyantogtokh. 2021. "Cactus Graphs with Maximal Multiplicative Sum Zagreb Index" Symmetry 13, no. 5: 913. https://0-doi-org.brum.beds.ac.uk/10.3390/sym13050913

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Metrics

Back to TopTop