Abstract
The general sum-connectivity index of a graph G is a molecular descriptor defined as \(\chi _{\alpha }(G)=\sum _{uv\in E(G)}(d_G(u)+d_G(v))^\alpha \), where \(d_G(u)\) denotes the degree of vertex u in G and \(\alpha \) is a real number. In this paper, we obtain the first third graphs with maximum general sum-connectivity index among the connected tricyclic graphs of order n for \(\alpha \ge 1\) by four transformations which increase the general sum-connectivity index.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
Let \(G=(V(G),E(G))\) be a connected simple graph with \(|V(G)|=n\) and \(|E(G|=m\). If \(m=n+c-1\), then G is called a c-cyclic graph. Specially, if \(c=0,1,2\) and 3, then G is called a tree, a unicyclic graph, a bicyclic graph and a tricyclic graph, respectively. Let \(P_n\) and \(S_n\) be respectively the path and the star with n vertices. Let \(N_G(v)\) denote the neighbor set of vertex v in G, then \(d_{G}(v)=|N_G(v)|\) is the degree of v in G. A pendent path in G is a path having one end vertex of degree at least 3, the other is of degree 1 and the intermediate vertices are of degree 2. An internal path of G is defined as a walk \(v_0v_1,\ldots ,v_s(s\ge 1)\) such that the vertices \(v_0,v_1,\ldots ,v_s\) are distinct, \(d_G(v_0)>2, d_G(v_s)>2\) and \(d_G(v_i)=2\), whenever \(0<i<s\). Other undefined notation may refer to [1].
The well-known Randić index R(G) of G, is defined as:
which is proposed by Randić in 1975 [2], has received intensive attention since its successful applications in QSPR and QSAR [3]. Later, Bollobás and Erdös [4] generalized this index to
for every graph G and an arbitrary value of \(\alpha \). The mathematical properties of R(G) as well as those of its generalization \(R_{\alpha }(G)\) have been studied extensively as summarized in the books [5, 6].
Recently, a closely related variant of Randić index called the sum-connectivity index [7], denoted by \(\chi (G)\), is defined as:
It has been found that \(\chi (G)\) and R(G) correlate well among themselves and with \(\pi \)-electronic energy of benzenoid hydrocarbons [7]. Similarly, the general sum-connectivity index [8] is defined as:
Several extremal properties of the general sum-connectivity index have already been established for general graphs [8], multigraphs [6], trees [6, 7, 9], unicyclic graphs [10, 11] and bicyclic graphs [12].
In this paper we want to extend the extremal study of the general sum-connectivity index to tricyclic graphs (connected graphs with n vertices and \(n+2\) edges). More precisely, we will find the graphs with the first fourth largest value of \(\chi _{\alpha }(G)\) among the tricyclic graphs of order n for \(\alpha \ge 1\) by four transformations which increase the general sum-connectivity index.
2 Preliminaries
In this section, we introduce some graphic transformations and lemmas, which will be used to prove our main results.
Transformation I
[10] Let u and v be two adjacent vertices of a graph G such that \(N_G(u)=\{v,z_1,\ldots ,z_p\}, N_G(v)=\{u,w_1,\ldots ,w_s\}\), where \(\{z_1,\ldots ,z_p\}\cap \{w_1,\ldots ,w_s\}=\emptyset \), \(p\ge 0, s\ge 1\). Let \(T_1(G)=G-vw_1-vw_2-\cdots -vw_s+uw_1+uw_2+\cdots +uw_s\). We say that \(T_1(G)\) is a \(T_1\)-transform of G (Fig. 1).
Lemma 2.1
[10] Let G and \(T_1(G)\) be the graphs in Transformation I, if \(\alpha < 0\), then \(\chi _{\alpha }(G)>\chi _{\alpha }(T_1(G))\) and if \(\alpha > 0\), then \(\chi _{\alpha }(G)<\chi _{\alpha }(T_1(G))\).
Lemma 2.2
[12] The real function defined by \(f_{\alpha ,a}(x)=(x+a)^{\alpha }-x^{\alpha }\) is strictly increasing for all \(\alpha >1\), \(a>0\).
Transformation II
Let G be a graph as shown in Fig. 2, and
where \(u_1,u_2,\ldots ,u_k\) are all the pendent vertices which are adjacent to u, integers \(k\ge 1,s\ge 0\), then \(d_G(u)-k=s+2\ge 2\). Let \(v_1,v_2,\ldots ,v_t\) are all the pendent vertices which are adjacent to v and \(d_G(v)=t+2\). Define \(T_2(G)\) as the graph obtained from G by deleting \(vv_1,vv_2,\ldots ,vv_t\) and adding \(uv_1,uv_2,\ldots ,uv_t\).
Lemma 2.3
Let G and \(T_2(G)\) be the graphs in Transformation II, if \(uv\in E(G),\) integers \(k\ge 1,s\ge 0,\) \(d_G(v)=t+2, t\ge 1\) and \(d_G(u')\ge d_G(v')\), then \(\chi _{\alpha }(G)<\chi _{\alpha }(T_2(G))\) for \(\alpha > 1\).
Proof
By direct calculation, we have
Furthermore, let
Note that \(d_G(u')\ge d_G(v')\), by Lemma 2.2, we have \(f_{\alpha ,t}(d_G(u')+k+s+2)\ge f_{\alpha ,t}(d_G(v')+2)\). Hence we have the desired results. \(\square \)
Remark 1
Lemma 2.3 is a generalization of Lemma 3 from [12].
For a graph G, the base of G, denoted by \(\widehat{G}\), is defined by the unique subgraph of G containing no pendent vertex. Obviously, for a graph G, by repeated Transformations I and II, finally, we can obtain a graph, denoted by \(G_0\), which cannot carry on further the Transformations I and II. Then by Lemmas 2.1 and 2.3, we have the following results.
Theorem 2.4
For a graph G, let \(G_0\) be the graph defined as above, then
-
(i)
All the cut-edges of \(G_0\) are pendent edges;
-
(ii)
Let \(U=\{u|d_{\widehat{G_0}}(u)\ge 3\}\), all bunches of pendent edges to \(V(\widehat{G_0})-U\) are situated at distances of at least two one from another;
-
(iii)
\(\chi _{\alpha }(G)<\chi _{\alpha }(G_0)\).
Transformation III
For a graph G, let \(G_0\) be the graph defined as above. Let \(U=\{u|d_{\widehat{G_0}}(u)\ge 3\}\), \(v\in V(\widehat{G_0})-U\) and \(v_1,v_2,\ldots ,v_t(t\ge 1)\) are all the pendent vertices which are adjacent to v in \(G_0\). For a vertex \(u\in U,\) if \(uv\in E(G_0)\) or P(u, v) is an internal path from u to v in \(G_0\), let \(T_3(G_0)=G_0-\{vv_1,vv_2,\ldots ,vv_t\}+\{uv_1,uv_2,\ldots ,uv_t\}.\)
Lemma 2.5
Let \(G_0, T_3(G_0)\) be the graphs in Transformation III, then \(\chi _{\alpha }(G_0)<\chi _{\alpha }(T_3(G_0))\).
Proof
Case 1 If \(uv\in E(G_0)\), by the definition of \(G_0\), we know that \(d_{\widehat{G_0}}(v)=2\). Let \(N_{\widehat{G_0}}(v)=\{u,w\}\) and \(u_1,\ldots ,u_k(k\ge 0)\) be the all pendent vertices which are adjacent to u in \(G_0\).
Subcase 1.1 If \(w\in U\) and \(uw\in E(G_0)\), let \(N_{G_0}(u)=\{v,w, u_1,\ldots ,u_k, w_1,\ldots , w_s\}(s\ge 1)\). By direct calculation, we have
Subcase 1.2 If \(w\in U\) and \(uw\notin E(G_0)\), without loss of generality, let \(d_{G_0}(w)\le d_{G_0}(u)\)(otherwise, we add the edges to w). Let \(N_{G_0}(u)=\{v, u_1,\ldots ,u_k, w_1,\ldots , w_s\}(s\ge 2)\), then \(d_{G_0}(u)=k+s+1\). Note that \(d_{G_0}(w_i)\ge 2\) and \(t\ge 1\). By direct calculation, we have
Subcase 1.3 If \(w\notin U\), then \(d_{G_0}(w)=2\). let \(N_{G_0}(u)=\{v,u_1,\ldots ,u_k, w_1,\ldots , w_s\}(s\ge 1)\). If \(k=0\), by Transformation I, we can obtain a graph \(T_1(G)\) with \(\chi _\alpha (G)<\chi _\alpha (T_1(G))\). So we can assume that \(k\ge 1\). Then
Now let
Obviously, \(f_{\alpha ,t}(d_{G_0}(w_1)+k+s+1)\ge f_{\alpha ,t}(4)\) since \(d_{G_0}(w_1)+k+s+1\ge 4\). Further by Lemma 2.2, we have \(\chi _{\alpha }(G_0)<\chi _{\alpha }(T_3(G_0))\).
Case 2 If P(u, v) is an internal path from u to v in \(G_0\), by Case 1, we can assume that all the neighbors of u and v situated on the base of \(G_0\) have degree 2 in \(G_0\). Let \(N_{G_0}(u)=\{u_1,\ldots ,u_k, w_1,\ldots , w_s\}(k\ge 0,s\ge 3)\), where \(u_1,\ldots ,u_k(k\ge 0)\) are the all pendent vertices which are adjacent to u in \(G_0\). Then
And let
then \(f_{\alpha ,t}(k+s+2)\ge f_{\alpha ,t}(4)\) since \(k+s+2\ge 5\). Hence \(\chi _{\alpha }(G_0)<\chi _{\alpha }(T_3(G_0))\). \(\square \)
Remark 2
By repeated Transformation III, all the pendent edges which are adjacent to a vertex in \(V(\widehat{G_0})-U\) can move to a vertex in U, denote the resulted graph by \(TT_3(G_0)\), then \(\chi _{\alpha }(G_0)<\chi _{\alpha }(TT_3(G_0))\). Furthermore, for any \(u,u'\in U\), we have \(uu'\in E(TT_3(G_0))\) or \(P(u,u')=ux_1x_2\cdots x_tu'(t\ge 1)\) is an internal path from u to \(u'\) in \(TT_3(G_0).\)
Transformation IV
If \(P(u,u')=ux_1x_2\cdots x_tu'\) is an internal path from u to \(u'\) in \(TT_3(G_0),\) let \(T_4(TT_3(G_0))=TT_3(G_0)-x_1x_2+ux_2\).
Similar to the proof of Lemma 2.5, we have
Lemma 2.6
Let \(TT_3(G_0), T_4(TT_3(G_0))\) be the graphs in Transformation IV, then \(\chi _{\alpha }(TT_3(G_0))<\chi _{\alpha }(T_4(TT_3(G_0)))\).
3 Main results
The base of a tricyclic graph G, denoted by \(\widehat{G}\), is the minimal tricyclic subgraph of G. Obviously, \(\widehat{G}\) is the unique tricyclic subgraph of G containing no pendent vertex, and G can be obtained from \(\widehat{G}\) by planting trees to some vertices of \(\widehat{G}\). By [13], we know that tricyclic graphs have the following four types of bases (as shown in Figs. 3, 4, 5): \(G_j^3 (j=1,\ldots , 7),G_j^4 (j=1,\ldots , 4), G_j^6 (j=1,\ldots , 3)\) and \(G_1^7\). Let
Then \({\fancyscript{G}}_{n,n+2}={\fancyscript{G}}_{n,n+2}^3\cup {\fancyscript{G}}_{n,n+2}^4\cup {\fancyscript{G}}_{n,n+2}^6\cup {\fancyscript{G}}_{n,n+2}^7.\)
Lemma 3.1
Let \(T_a^3, T_b^3\) be the graphs as shown in Fig. 6, \(s\ge t\ge 1\), then \(\chi _{\alpha }(T_a^3)<\chi _{\alpha }(T_b^3)\).
Proof
By direct calculation, we have
By Lemma 2.2, \(\chi _{\alpha }(T_a^3)<\chi _{\alpha }(T_b^3)\). \(\square \)
Lemma 3.2
Let \(T_1^3, T_2^3\) be the graphs as shown in Fig. 7, then \(\chi _{\alpha }(T_1^3)<\chi _{\alpha }(T_2^3)\).
Proof
By direct calculation, we have
Then
Let
then by Lemma 2.2, we have \(f_{\alpha ,2}(6)>f_{\alpha ,2}(4).\) Hence \(\chi _{\alpha }(T_1^3)<\chi _{\alpha }(T_2^3)\). \(\square \)
By repeated translations I–IV and Lemmas 2.1, 2.3, 2.5, 2.6, 3.1 and 3.2, we have
Theorem 3.3
Let \(G\in {\fancyscript{G}}_{n,n+2}^3\) and \(G\ne T_1^3,T_2^3\), \(\chi _{\alpha }(G)<\chi _{\alpha }(T_1^3)<\chi _{\alpha }(T_2^3)\).
Lemma 3.4
Let \(T_1^4, T_2^4\) be the graphs as shown in Fig. 8, then \(\chi _{\alpha }(T_1^4)<\chi _{\alpha }(T_2^4)\).
Proof
By direct calculation, we have
Then
Hence we obtain our desired result. \(\square \)
Remark 3
Let G is a graph with base \(\widehat{T_1^4}\) (or \(\widehat{T_2^4}\)), if there are two vertices u, v in its base with degrees no less 3 and at least one pendent edge attaching at each one, its general sum-connectivity index is less than \(T_1^4\) (or \(T_2^4\)).
By repeated translations I–IV and Lemmas 2.1, 2.3, 2.5, 2.6, 3.4 and Remark 3, we have
Theorem 3.5
Let \(G\in {\fancyscript{G}}_{n,n+2}^4\) and \(G\ne T_1^4,T_2^4\), then \(\chi _{\alpha }(G)<\chi _{\alpha }(T_1^4)<\chi _{\alpha }(T_2^4)\).
Lemma 3.6
Let \(T_1^6, T_2^6, T_3^6\) be the graphs as shown in Fig. 9, then \(\chi _{\alpha }(T_1^6)>\chi _{\alpha }(T_2^6)>\chi _{\alpha }(T_3^6)\).
Proof
By direct calculation, we have
Then
Let
then by Lemma 2.2, we have \(f_{\alpha ,1}(n+2)>f_{\alpha ,2}(n+1).\) So \(\chi _{\alpha }(T_1^6)>\chi _{\alpha }(T_2^6)\). Further,
Hence we have our desirable result. \(\square \)
Remark 4
Let G is a graph with base \(\widehat{T_1^6}\) (\(\widehat{T_2^6}\) or \(\widehat{T_3^6}\)), if there are two vertices u, v in its base with degrees no less 3 and at least one pendent edge attaching at each one, its general sum-connectivity index is less than \(T_1^6\) (\(T_2^6\) or \(T_3^6\)).
By repeated translations I–IV and Lemmas 2.1, 2.3, 2.5, 2.6, 3.6 and Remark 4, we have
Theorem 3.7
Let \(G\in {\fancyscript{G}}_{n,n+2}^6\) and \(G\ne T_1^6, T_2^6, T_3^6\), \(\chi _{\alpha }(G)<\chi _{\alpha }(T_3^6)<\chi _{\alpha }(T_2^6) <\chi _{\alpha }(T_1^6)\).
Lemma 3.8
Let \(T_a^7, T_b^7\) be the graphs as shown in Fig. 10, where \(s\ge t\ge 1\) and \(T_b^7=T_a^7-vy_t+ux_{s+1}.\) Then \(\chi _\alpha (T_a^7)<\chi _\alpha (T_b^7)\).
Proof
By direct calculation, we have
Let
By Lemma 2.2, we have \(f_{\alpha ,1}(s+6)>f_{\alpha ,1}(t+5)\) since \(s\ge t.\) Hence \(\chi _\alpha (T_a^7)<\chi _\alpha (T_b^7)\). \(\square \)
By Lemma 3.8, we have the following lemma.
Lemma 3.9
Let \(T_i^7, i=1,2\) be the graphs as shown in Fig. 11, \(\chi _\alpha (T_2^7)<\chi _\alpha (T_1^7)\).
By repeated translations I–IV and Lemmas 2.1, 2.3, 2.5, 2.6 and 3.9, we have
Theorem 3.10
Let \(G\in {\fancyscript{G}}_{n,n+2}^7\) and \(G\ne T_i^7(i=1,2)\), \(\chi _{\alpha }(G)<\chi _{\alpha }(T_2^7)<\chi _{\alpha }(T_1^7)\).
Lemma 3.11
For \(n\ge 6\), \(\chi _\alpha (T_2^7)<\chi _\alpha (T_2^6)<\min \{\chi _\alpha (T_1^6),\chi _{\alpha }(T_1^7)\}\) and \(\chi _\alpha (T_2^3)<\chi _\alpha (T_2^4)<\chi _\alpha (T_2^6)<\min \{\chi _\alpha (T_1^6),\chi _{\alpha }(T_1^7)\}\).
Proof
Let \(f_{\alpha ,1}(n+2)=(n+3)^\alpha -(n+2)^\alpha , f_{\alpha ,1}(n+1)=(n+2)^\alpha -(n+1)^\alpha , f_{\alpha ,1}(n)=(n+1)^\alpha -n^\alpha \). Then by Lemma 2.2, we have
Further by Lemmas 3.6 and 3.9, we have our desired results. \(\square \)
Note that
It is not easy to confirm the sign of the difference \(\chi _\alpha (T_1^7)-\chi _\alpha (T_1^6)\), but there exists a natural number \(n_0(\alpha )\) such that \(\chi _{\alpha }(T_1^{7})>\chi _{\alpha }(T_1^{6})\) for every \(n\ge n_0(\alpha )\). Using mathematical software it can be seen that \(n_0(\alpha )=\alpha -2\) for every \(\alpha \in N, 8\le \alpha \le 20\).
Theorems 3.3, 3.5, 3.7, 3.10 imply
Theorem 3.12
Let \(G\in {\fancyscript{G}}_{n,n+2}(n\ge 6)\) and \(G\ne T_2^6, T_1^6, T_1^7\), then \(\chi _{\alpha }(G)<\chi _\alpha (T_2^6)<\min \{\chi _\alpha (T_1^6),\chi _{\alpha }(T_1^7)\}< \max (\chi _{\alpha }(T_1^{6}),\chi _{\alpha }(T_1^{7}))\) for \(\alpha \ge 1\).
References
Bollobás, B.: Modern Graph Theory. Springer, New York (1998)
Randić, M.: On characterization of molecular branching. J. Am. Chem. Soc. 97, 6609–6615 (1975)
GarcÍa-Domenech, R., Gálvez, J., de Julian-Ortiz, J.V., Pogliani, L.: Some new trends in chemical graph theory. Chem. Rev. 108, 1127–1169 (2008)
Bollobás, B., Erdös, P.: Graphs of extremal weights. Ars Combin. 50, 225–233 (1998)
Li, X., Gutman, I.: Mathematical Aspects of Randić-Type Molecular Structure Descriptors. University of Kragujevac, Kragujevac (2006)
Tomescu, I., Kanwal, S.: Ordering trees having small general sum-connectivity index. MATCH Commun. Math. Comput. Chem. 69, 535–548 (2013)
Zhou, B., Trinajstić, N.: On a novel connectivity index. J. Math. Chem. 46, 1252–1270 (2009)
Zhou, B., Trinajstić, N.: On general sum-connectivity index. J. Math. Chem. 47, 210–218 (2010)
Du, Z., Zhou, B., Trinajstić, N.: On the general sum-connectivity index of tree. J. Math. Chem. 24, 402–405 (2011)
Du, Z., Zhou, B., Trinajstić, N.: Minimum general sum-connectivity index of unicyclic graphs. J. Math. Chem. 48, 697–703 (2010)
Tomescu, I., Kanwal, S.: Unicyclic graphs of given girth \(k\ge 4\) having smallest general sum-connectivity index. Discr. Appl. Math. 164, 344–348 (2014)
Tache, Rozica-Maria: General sum-connectivity index with for \(\alpha \ge 1\) bicyclic graphs. MATCH Commun. Math. Comput. Chem. 72, 761–774 (2014)
Li, S., Li, X., Zhu, Z.: On tricyclic graphs with minimal energy. MATCH Commun. Math. Comput. Chem. 59, 397–419 (2008)
Acknowledgments
The authors would like to express their sincere gratitude to the referees for a very careful reading of the paper and for all their insightful comments and valuable suggestions, which led to a number of improvements in this paper. This project is supported by Nature Science Foundation of Hubei Province (2014CFC1118), the foundation of State Ethnic Affairs Commission (14ZNZ023), the Special Fund for Basic Scientific Research of Central Colleges, South-Central University for Nationalities (CZW15084, CZW15063) and the Scientific Research Foundation of Graduate School of South Central University for Nationalities.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Zhu, Z., Lu, H. On the general sum-connectivity index of tricyclic graphs. J. Appl. Math. Comput. 51, 177–188 (2016). https://doi.org/10.1007/s12190-015-0898-2
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12190-015-0898-2