Advanced
THE ZAGREB INDICES OF BIPARTITE GRAPHS WITH MORE EDGES†
THE ZAGREB INDICES OF BIPARTITE GRAPHS WITH MORE EDGES†
Journal of Applied Mathematics & Informatics. 2015. May, 33(3_4): 365-377
Copyright © 2015, Korean Society of Computational and Applied Mathematics
  • Received : October 15, 2014
  • Accepted : December 18, 2014
  • Published : May 30, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
KEXIANG XU
KECHAO TANG
HONGSHUANG LIU
JINLAN WANG

Abstract
Abstract. For a (molecular) graph, the first and second Zagreb indices ( M 1 and M 2 ) are two well-known topological indices, first introduced in 1972 by Gutman and Trinajstić. The first Zagreb index M 1 is equal to the sum of the squares of the degrees of the vertices, and the second Zagreb index M 2 is equal to the sum of the products of the degrees of pairs of adjacent vertices. Let with n 1 n 2 , n 1 + n 2 = n and p < n 1 be the set of bipartite graphs obtained by deleting p edges from complete bipartite graph K n1,n2 . In this paper, we determine sharp upper and lower bounds on Zagreb indices of graphs from and characterize the corresponding extremal graphs at which the upper and lower bounds on Zagreb indices are attained. As a corollary, we determine the extremal graph from with respect to Zagreb coindices. Moreover a problem has been proposed on the first and second Zagreb indices. AMS Mathematics Subject Classification : 05C07, 05C35, 05C90.
Keywords
1. Introduction
We only consider finite, undirected and simple graphs throughout this paper. Let G be a graph with vertex set V ( G ) and edge set E ( G ). For any vertex v V ( G ), we denote by NG ( v ) the set of its neighbors in G . The degree of v V ( G ), denoted by dG ( v ), is the cardinality of NG ( v ), i.e., the number of vertices in G adjacent to v . For a subset W of V ( G ), let G - W be the subgraph of G obtained by deleting the vertices of W and the edges incident with them. Similarly, for a subset E′ of E ( G ), we denote by G - E′ the subgraph of G obtained by deleting the edges of E′ . If W = { v } and E′ = { xy }, the subgraphs G - W and G - E′ will be written as G - v and G - xy for short, respectively. K n1,n2 is a complete bipartite graph of order n = n 1 + n 2 and two bipartite sets V 1 and V 2 with | Vi | = ni for i = 1, 2. Other undefined notations and terminology on the graph theory can be found in [4] .
A graphical invariant is a number related to a graph which is a structural invariant, in other words, it is a fixed number under graph automorphisms. In chemical graph theory, these invariants are also known as the topological indices. Two of the oldest graph invariants are the well-known Zagreb indices first introduced in [17] where Gutman and Trinajsti´c examined the dependence of total π -electron energy on molecular structure and elaborated in [18] . For a (molecular) graph G , the first Zagreb index M 1 ( G ) and the second Zagreb index M 2 ( G ) are, respectively, defined as follows:
PPT Slide
Lager Image
Another well-known version of first Zagreb index is in the following:
PPT Slide
Lager Image
These two classical topological indices reflect the extent of branching of the molecular carbon-atom skeleton [3 , 22 , 25] . The main properties of M 1 and M 2 were summarized in [5 , 7 9 , 14 16 , 20 , 24 , 26 , 28] . In particular, Deng [9] gave a unified approach to determine extremal values of Zagreb indices for trees, unicyclic, and bicyclic graphs, respectively. For some newest applications of Zagreb indices of graphs, please see [6 , 13 , 14 , 19 , 23] . In recent years, some novel variants of ordinary Zagreb indices have been introduced and studied, such as Zagreb coindices [1 , 2 , 10] , multiplicative Zagreb indices [12 , 24 , 30] , multiplicative sum Zagreb index [11 , 27] and multiplicative Zagreb coindices [29] . Especially the first and second Zagreb coindices of graph G are defined [1 , 10] in what follows:
PPT Slide
Lager Image
Hereafter we always assume that n 1 , n 2 , p are three positive integers such that n 1 n 2 , n 1 + n 2 = n and p < n 1 . We denote by
PPT Slide
Lager Image
the set of bipartite graphs obtained by deleting p edges from the complete bipartite graph K n1,n2 . In this paper we present sharp upper and lower bounds on the Zagreb indices of graphs from
PPT Slide
Lager Image
and characterize the extremal graphs at which the upper or lower bounds are attained. As a corollary, we also determine the extremal graph from
PPT Slide
Lager Image
with respect to Zagreb coindices. Finally an open problem is proposed on the Zagreb indices.
2. Preliminaries
In this section we list or prove some lemmas as preliminaries, which will be further used .
Lemma 2.1 ( [1 , 2] ). Let G be a connected graph of order n and with m edges.
Then we have
  • (1)= 2m(n- 1) -M1(G);
  • (2)= 2m2-M2(G) -.
Lemma 2.2. Let G be a connected graph with e = uv E ( G ) and G′ = G - uv .
Then we have M 1 ( G′ ) = M 1 ( G ) - 2 - 2( dG′ ( u ) + dG′ ( v )).
Proof . By the definition of first Zagreb index, we have
PPT Slide
Lager Image
which completes the proof. □
Lemma 2.3. Let G be a connected graph with uv E ( G ) and NG ( u ) ╲ { v } = { v 1 , v 2 ,⋯, vα } and NG ( v ) ╲ { u } = { u 1 , u 2 ,⋯, uβ }. Suppose that G′ = G - uv .
Then we have
PPT Slide
Lager Image
Proof . From the definition of second Zagreb index, we have
PPT Slide
Lager Image
Thus the proof this lemma was completed. □
3. Extremal graphs fromw. r. t. Zagreb indices
In this section we will consider the extremal graphs from
PPT Slide
Lager Image
with respect to Zagreb indices. Before presenting the main results, we first introduce some special graphs in
PPT Slide
Lager Image
. Let
PPT Slide
Lager Image
be a bipartite graph obtained by deleting p edges e 1 , e 2 ,⋯, ep from K n1,n2 where all e 1 , e 2 ,⋯, ep are pairwise independent. And we denote by
PPT Slide
Lager Image
the bipartite graph obtained by deleting p edges e 1 , e 2 ,⋯, ep from K n1,n2 where e 1 , e 2 ,⋯, ep have a common vertex in the partite set of size n 1 in it. Similarly,
PPT Slide
Lager Image
is a bipartite graph obtained by deleting p edges e 1 , e 2 ,⋯, ep from K n1,n2 where all e 1 , e 2 ,⋯, ep have a common vertex in the partite set of size n 2 in it. As three examples,
PPT Slide
Lager Image
are shown in Figure 1 .
PPT Slide
Lager Image
The graphs
When p = 1, there is only one graph in
PPT Slide
Lager Image
, and there is nothing to deal with for our main problem. So in what follows, we always assume that p ≥ 2. In the following theorem we will determine the extremal graphs from
PPT Slide
Lager Image
with respect to the first Zagreb index.
Theorem 3.1. For any graph
PPT Slide
Lager Image
, we have
PPT Slide
Lager Image
with left equality holding if and only if
PPT Slide
Lager Image
and right equality holding if and only if
PPT Slide
Lager Image
for i = 1, 2.
Proof . We prove this result by induction on p , i.e., the number of edges deleted from K n1,n2 . When p = 2, there exist exactly three graphs in the set
PPT Slide
Lager Image
, which are just
PPT Slide
Lager Image
. From the definition of first Zagreb index, we have
PPT Slide
Lager Image
Therefore the results in this theorem hold immediately.
Assume that the results hold for p = k - 1. Now we consider the case when p = k . For any graph
PPT Slide
Lager Image
, there exists a graph
PPT Slide
Lager Image
with uv E ( G ) and G - uv = G . By Lemma 2.2, we have
PPT Slide
Lager Image
Now we assume that, at vertices u V 1 and v V 2 in G , there are k 1 , k 2 edges, respectively, deleted from K n1,n2 . Then we claim that 0 ≤ k 1 + k 2 k -1 and dG ( u )+ dG ( v ) = n - k 1 - k 2 . Considering the facts that dG ( u ) = dG ( u )-1 and dG ( v ) = dG ( v ) - 1, we have
PPT Slide
Lager Image
Combining these two equalities (3) and (4), we arrive at the following:
PPT Slide
Lager Image
Next it suffices to deal with the equality (5). For the left part in (2), by the induction hypothesis and equality (5), we have
PPT Slide
Lager Image
The above equality holds if and only if
PPT Slide
Lager Image
and k 1 = 0, k 2 = 0. Equivalently,
PPT Slide
Lager Image
and ek = uv is independent of any one edge from { e 1 , e 2 ,⋯, e k−1 }. Therefore we have
PPT Slide
Lager Image
. Then the proof of the left part in (2) is completed.
Now we turn to the right part of (2). By the induction hypothesis and equality (5), we have
PPT Slide
Lager Image
The above equality holds if and only if
PPT Slide
Lager Image
for i = 1, 2 and k 1 + k 2 = k -1, i.e.,
PPT Slide
Lager Image
and k 1 = k -1, k 2 = 0 or
PPT Slide
Lager Image
and k 1 = 0, k 2 = k - 1.
Thus we find that, either in
PPT Slide
Lager Image
, there are k - 1 edges deleted from the vertex u V 1 of K n1,n2 ; or in
PPT Slide
Lager Image
, there are k - 1 edges from v V 2 of K n1,n2 . Therefore, we conclude that
PPT Slide
Lager Image
. This completes the proof of this theorem. □
In the theorem below we characterize the extremal graphs from
PPT Slide
Lager Image
with respect to the second Zagreb index.
Theorem 3.2. For any graph
PPT Slide
Lager Image
with n 1 < n 2 , we have
PPT Slide
Lager Image
with left equality holding if and only if
PPT Slide
Lager Image
and right equality holding if and only if
PPT Slide
Lager Image
.
Proof . We prove this result by induction on p . When p = 2, there exist exactly three graphs in the set
PPT Slide
Lager Image
, which are just
PPT Slide
Lager Image
. From the definition of second Zagreb index, we have
PPT Slide
Lager Image
Obviously,
PPT Slide
Lager Image
. Thus our results hold as desired.
Now we assume that the results in (6) hold for p = k -1. Then we consider the case when p = k . For any graph
PPT Slide
Lager Image
, there exists a graph
PPT Slide
Lager Image
with u V 1 , v V 2 , uv E ( G ) and G - uv = G . The structure of G is shown in Fig. 2 where the polygonal lines denote the deleted edges from K n1,n2 . Suppose that NG ( u ) ╲ { v } = { v 1 , v 2 ,⋯, vα } ≜ X 1 and NG ( v ) ╲ { u } = { u 1 , u 2 ,⋯, uβ } ≜ X 4 . Let V 1 ╲ ( X 4 ∪ { u }) = X 3 and V 2 ╲ ( X 1 ∪ { v }) = X 2 . By Lemma 2.3, we have
PPT Slide
Lager Image
PPT Slide
Lager Image
The structure of graph G
As introduced in [8] , for any vertex v in a graph G , we denote by mG ( v ) the average of the degrees of all vertices adjacent to vertex v in G . Again we assume that, at vertices u V 1 and v V 2 in G , there are k 1 ; k 2 edges, respectively, deleted from K n1,n2 . Let the number of edges deleted between the two subsets X 1 , X 3 in G and between the two subsets X 1 , X 4 be x 1 and y 1 , respectively, the edges deleted between the two subsets X 2 , X 3 and between the two subsets X 2 ; X 4 be x 2 and y 2 , respectively. Moreover we have x 1 + x 2 + y 1 + y 2 = k - 1 - k 1 - k 2 . Then we claim that
PPT Slide
Lager Image
From the definition of mG ( u ), we arrive at:
PPT Slide
Lager Image
Similarly, we have
PPT Slide
Lager Image
Combining the above two equalities with equality (7), we get
PPT Slide
Lager Image
It can be easily checked that the term 2 k 1 n 1 + 2 k 2 n 2 - k 1 k 2 reaches its minimum value 0 when k 1 = k 2 = 0. For the left part in (6), from equality (∗) and the induction hypothesis, we have
PPT Slide
Lager Image
The above equality holds if and only if
PPT Slide
Lager Image
and k 1 = 0, k 2 = 0. Moreover, from the statement k 1 = 0, k 2 = 0 we can deduce that ek = uv is independent of any edge of { e 1 , e 2 ,⋯, e k−1 }. Therefore we find that
PPT Slide
Lager Image
, which ends the proof of left part in (6).
Now we will turn to the proof for the right part in (6). From the definition of mG ( v ) for any vertex v in a graph G and the structure of G , we have
PPT Slide
Lager Image
Similarly, we have
PPT Slide
Lager Image
Combining the above two inequalities with equality equality (7), we can obtain
PPT Slide
Lager Image
Clearly the term 2( n 2 -1) k 2 +2( n 1 -1) k 1 - k 1 k 2 reaches its maximum value 2( n 2 -1)( k - 1) when k 1 = 0 and k 2 = k -1. From the induction hypothesis, it follows that
PPT Slide
Lager Image
The above two equalities holds if and only if
PPT Slide
Lager Image
and k 1 = 0, k 2 = k - 1. That is to say, G is obtained by deleting from
PPT Slide
Lager Image
one more edge which has one common vertex with that one of { e 1 , e 2 ,⋯, e k−1 } in it. Therefore we claim that
PPT Slide
Lager Image
, finishing the proof of right part in (6). Thus we complete the proof of this theorem. □
Note that
PPT Slide
Lager Image
if n 1 = n 2 . We denote by
PPT Slide
Lager Image
this graph when n 1 = n 2 . By a similar reasoning as that in the proof of Theorem 3.2, the following corollary can be easily obtained.
Corollary 3.1. For any graph
PPT Slide
Lager Image
, we have
PPT Slide
Lager Image
with left equality holding if and only if
PPT Slide
Lager Image
and right equality holding if and only if
PPT Slide
Lager Image
.
Now we turn to the determination of extremal graphs from
PPT Slide
Lager Image
with respect to Zagreb coindices. Based on Lemma 2.1 (1), we have
PPT Slide
Lager Image
Moreover the following result can be easily obtained.
Corollary 3.2. For any graph
PPT Slide
Lager Image
, we have
PPT Slide
Lager Image
with left equality holding if and only if
PPT Slide
Lager Image
for i = 1, 2 and right equality holding if and only if
PPT Slide
Lager Image
.
In view of Lemma 2.1 (2), we have
PPT Slide
Lager Image
Corollary 3.3. For any graph
PPT Slide
Lager Image
, we have
PPT Slide
Lager Image
with left equality holding if and only if
PPT Slide
Lager Image
and right equality holding if and only if
PPT Slide
Lager Image
.
Proof . From Lemma 2.1 (2), it suffices to find the extremal graphs from
PPT Slide
Lager Image
at which the maximal (or minimal, resp.) first and second Zagreb indices are simultaneously attained. Note that, from Theorems 3.1 and 3.2, the first Zagreb index and second Zagreb index of graphs from
PPT Slide
Lager Image
with n 1 < n 2 reach the maximum only when
PPT Slide
Lager Image
. Thus our results follow immediately from Theorems 3.1 and 3.2. □
4. A related problem
In this section we propose a problem related to the extremal graphs with respect to Zagreb indices. Based on the alternative formula (1) of the first Zagreb index and the definition of the second Zagreb index, these two indices have very similar versions. Therefore, from the intuition, we think that, in a given set G of connected graphs, the graphs with maximal first Zagreb index are the same as the graphs with maximal second Zagreb index, and vice versa; and the graphs with minimal first Zagreb index are the same as the graphs with minimal second Zagreb index, and vice versa. We say that this set G satisfies extremal identical graph property with respect to Zagreb indices (EIG property w. r. t. Zagreb indices for short). Actually, our statement is true for many known results, such as trees, unicyclic graphs, and bicyclic graphs (see [9] ), and so on. Furthermore, our main result in this paper is also a positive example to our statement given above.
Now we would like to propose an interesting problem related to the EIG property as follows:
Problem 1. Characterizing the sets Γ of graphs which satisfy EIG property w. r. t. Zagreb indices?
Moreover, it is reasonable to restrict the consideration to the cases when the set Γ contains connected graphs of the same order.
Obviously, from Lemma 2.1, if a set Γ satisfies EIG property w. r. t. Zagreb indices, then it also satisfies EIG w. r. t. Zagreb coindices. Moreover we can also study the EIG property of any set of graphs with respect to other vertexdegree-based topological indices, which may be of interest to us.
BIO
Kexiang Xu received M.Sc. from Southeast University and Ph.D at Nanjing Normal University in China. He is an associate professor of Mathematics in Nanjing University of Aeronautics & Astronautics of China. His research interests include graph theory with its applications.
Department of Mathematics, College of Science, Nanjing University of Aeronautics & Astronautics, Nanjing, Jiangsu 210016, PR China.
e-mail: kexxu1221@126.com
Kechao Tang received M.Sc. from Nanjing University of Aeronautics & Astronautics of China.
Department of Mathematics, College of Science, Nanjing University of Aeronautics & Astronautics, Nanjing, Jiangsu 210016, PR China.
e-mail: tangkechao3@163.com
Hongshuang Liu is a M.Sc. student in Nanjing University of Aeronautics & Astronautics of China.
Department of Mathematics, College of Science, Nanjing University of Aeronautics & Astronautics, Nanjing, Jiangsu 210016, PR China.
e-mail: 992868875@qq.com
Jinlan Wang is a M.Sc. student in Nanjing University of Aeronautics & Astronautics of China.
Department of Mathematics, College of Science, Nanjing University of Aeronautics & Astronautics, Nanjing, Jiangsu 210016, PR China.
e-mail: 774189209@qq.com
References
Ashrafi A.R. , Došlić T. , Hamzeh A. (2010) The Zagreb coindices of graph operations Discrete Appl. Math. 158 1571 - 1578    DOI : 10.1016/j.dam.2010.05.017
Ashrafi A.R. , Došlić T. , Hamzeh A. (2011) Extremal graphs with respect to the Zagreb coindices MATCH Commun. Math. Comput. Chem. 65 85 - 92
Balaba A.T. , Motoc I. , Bonchev D. , Mekenyan O. (1983) Topological indices for structure- activity corrections Topics Curr. Chem. 114 21 - 55
Bondy J.A. , Murty U.S.R. 1976 Graph Theory with Applications Macmillan Press New York
Das K.C. (2004) Maximizing the sum of the squares of degrees of a graph Discrete Math. 257 57 - 66    DOI : 10.1016/j.disc.2004.04.007
Das K.C. , Akgünes N. , Togan M. , Yurttas A. , Cangül I.N. , Cevik A.S. On the first Za-greb index and multiplicative Zagreb coindices of graphs Analele Stiintifice ale Universitatii Ovidius Constanta in press
Das K.C. , Gutman I. , Zhou B. (2009) New upper bounds on Zagreb indices J. Math. Chem. 46 514 - 521    DOI : 10.1007/s10910-008-9475-3
Das K.C. , Gutman I. (2004) Some properties of the second Zagreb index MATCH Commun. Math. Comput. Chem. 52 103 - 112
Deng H. (2007) A unified approach to the extremal Zagreb indices for trees, unicyclic graphs and bicyclic graphs MATCH Commun. Math. Comput. Chem. 57 597 - 616
Došlić T. (2008) Vertex-weighted Wiener polynomials for composite graphs Ars Math. Contemp. 1 66 - 80
Eliasi M. , Iranmanesh A. , Gutman I. (2012) Multiplicative versions of first Zagreb index MATCH Commun. Math. Comput. Chem. 68 217 - 230
Gutman I. (2011) Multiplicative Zagreb indices of trees Bulletin of Society of Mathematicians Banja Luka 18 17 - 23
Gutman I. (2013) Degree-based topological indices Croat. Chem. Acta 86 351 - 361    DOI : 10.5562/cca2294
Gutman I. (2014) An exceptional property of first Zagreb index MATCH Commun. Math. Comput. Chem. 72 733 - 740
Gutman I. , Das K.C. (2004) The first Zagreb index 30 years after MATCH Commun. Math. Comput. Chem. 50 83 - 92
Gutman I. , Polansky O.E. 1986 Mathematical Concepts in Organic Chemistry Springer Berlin
Gutman I. , Trinajstić N. (1972) Graph theory and molecular orbitals. III. Total π-electron energy of alternant hydrocarbons Chem. Phys. Lett. 17 535 - 538    DOI : 10.1016/0009-2614(72)85099-1
Gutman I. , Ruščić B. , Trinajstić N. , Wilcox C.F. (1975) Graph theory and molecular orbitals. XII. Acyclic polyenes J. Chem. Phys. 62 3399 - 3405    DOI : 10.1063/1.430994
Lučić B. , Nikolić S. , Trinajstić N. 2012 Zagreb indices, in: Chemical information and computational challenges in the 21st century, edited by M.V. Putz Nova Sci. Publ. New York 261 - 275
Nikolić S. , Kovačević G. , Miličević A. , Trinajstić N. (2003) The Zagreb indices 30 years after Croat. Chem. Acta 76 113 - 124
Todeschini R. , Ballabio D. , Consonni V. 2010 Novel molecular descriptors based on func-tions of new vertex degrees, In: Novel molecular structure descriptors - Theory and applications I. (I. Gutman, B. Furtula, eds.) Univ. Kragujevac Kragujevac 73 - 100
Todeschini R. , Consonni V. 2000 Handbook of Molecular Descriptors Wiley-VCH Weinheim
Todeschini R. , Consonni V. (2009) Zagreb indices (Mn), in: Molecular descriptors for chemoinformatics Wiley-VCH Weinheim 955 - 966
Todeschini R. , Consonni V. (2010) New local vertex invariants and molecular descriptors based on functions of the vertex degrees MATCH Commun. Math. Comput. Chem. 64 359 - 372
Trinajstić T 1992 Chemical Graph Theory CRC Press Raton, FL
Xu K. (2011) The Zagreb indices of graphs with a given clique number Appl. Math. Lett. 24 1026 - 1030    DOI : 10.1016/j.aml.2011.01.034
Xu K. , Das K.C. (2012) Trees, unicyclic, and bicyclic graphs extremal with respect to multi-plicative sum Zagreb index Math. Comput. Chem. 68 257 - 272
Xu K. , Das K.C. , Balachandran S. (2014) Maximizing the Zagreb indices of (n,m)- graphs MATCH Commun. Math. Comput. Chem. 72 641 - 654
Xu K. , Das K.C. , Tang K. (2013) On the multiplicative Zagreb coindex of graphs Opuscula Math. 33 197 - 210
Xu K. , Hua H. (2012) A unified approach to extremal multiplicative Zagreb indices for trees, unicyclic and bicyclic graphs MATCH Commun. Math. Comput. Chem. 68 241 - 256