This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.
Introduction
Let G = (V,E) be a simple graph with n = |V| vertices and m = |E|edges. As usual, nis said to be an order and mthe size of G. The subdivision graph S(G) is the graph obtained from Gby replacing each edge by a path of length 2. The line graph L(G) of Gis the graph whose vertex set is E(G) in which two vertices are adjacent if and only if they are adjacent in G. The tadpole graph Tn,k is the graph obtained by joining a cycle of nvertices with a path of length k. The cartesian product G × Hof graphs Gand Hhas the vertex set V(G × H) = V(G) × V(H) and (a,x)(b,y) is an edge of G × Hif and only if [a = band xy ∈ E(H)] or [x = yand ab ∈ E(G)]. The ladder graph Ln is given by Ln = K2× Pn, where Pn is the path of length n. Let Eβ (G) be the set of paths of length βin G. We refer to [13] for unexplained terminology and notation.
Chemical graph theory is a branch of mathematical chemistry concerned with the study of chemical graphs. Chemical graphs are models of molecules in which atoms are represented by vertices and chemical bonds by edges of a graph. A graphical invariant is a number related to a graph. In other words, it is a fixed number under graph automorphisms. In chemical graph theory, these invariants are also called the topological indices. The first and second Zagreb indices are defined as
The higher connectivity indices are of great interest in molecular graph theory [15, 22] and some of their mathematical properties have been reported in [1, 18, 19]. Chemical applications of higher connectivity indices are the motivations for our study.
By Eq. (1), it is consistent to define (2, α)-connectivity index and (2,1)-connectivity index as
$$\begin{array}{}
\displaystyle
{{}_{}^2{\chi _\alpha }\left( G \right) = }&{\mathop {\rm{\Sigma }}\limits_{uvw \in {E_2}\left( G \right)} {{({d_G}\left( u \right){d_G}\left( v \right){d_G}\left( w \right))}^\alpha }\;{{ and}}}
\end{array}$$
$$\begin{array}{}
\displaystyle
{{}_{}^2{\chi _1}\left( G \right) = }&{\mathop {\rm{\Sigma }}\limits_{uvw \in {E_2}\left( G \right)} ({d_G}\left( u \right){d_G}\left( v \right){d_G}\left( w \right))}
\end{array}$$
respectively.
The present paper is organized as follows. In Section 2, we study the chemical applicability of the (2,1)-connectivity index. In Section 3, we compute the (2,α)-connectivity index of certain class of graphs and present the upper and lower bounds for (2, α)-connectivity index in terms of the number of vertices, the number of edges and the minimum vertex degree and determine the extremal graphs which achieve the bounds. In Section 4, we compute the (2, α)-connectivity index of line graphs of subdivision graphs of 2D-lattice, nanotube and nanotorus of TUC4C8[p,q], tadpole graphs, wheel graphs and ladder graphs.
On the chemical applicability of the (2,1)-connectivity index
Octane isomers have become an important set of organic molecules to test the applicability of various topological parameters in quantitative structure-property relationships (QSPR) and quantitative structure-activity relationships (QSAR). The productivity of (2,1)-connectivity index was tested using a dataset of octane isomers, found at https://www.moleculardescriptors.eu/dataset.htm. It is shown that the (2,1)-connectivity index has a good correlation with the acentric factor of an octane isomers.
The dataset of octane isomers (first two columns of Table 1) are taken from https://www.moleculardescriptors.eu/dataset.htm and the last column of Table 1 is computed from the definition of (2,1)-connectivity index.
Experimental values of the acentric factor and corresponding values of 2χ1 of octane isomers.
Alkane
AcentFac
2χ1
n-octane
0.397898
40
2-methyl-heptane
0.377916
47
3-methyl-heptane
0.371002
54
4-methyl-heptane
0.371504
56
3-ethyl-hexane
0.362472
64
2,2-dimethyl-hexane
0.339426
64
2,3-dimethyl-hexane
0.348247
70
2,4-dimethyl-hexane
0.344223
63
2,5-dimethyl-hexane
0.35683
54
3,3-dimethyl-hexane
0.322596
80
3,4-dimethyl-hexane
0.340345
78
2-methyl-3-ethyl-pentane
0.332433
81
3-methyl-3-ethyl-pentane
0.306899
96
2,2,3-trimethyl-pentane
0.300816
96
2,2,4-trimethyl-pentane
0.30537
75
2,3,3-trimethyl-pentane
0.293177
103
2,3,4-trimethyl-pentane
0.317422
87
2,2,3,3-tetramethylbutane
0.255294
120
The linear regression model for the acentric factor of Table 1 is obtained by using the least squares fitting procedure as implemented in R−software [24]. The fitted model is
The values of (2,1)-connectivity index against values of acentric factor of an octane isomers are plotted in Fig. 1. The absolute value of correlation coefficient between AcentFac and 2χ1 is 0.95802 and with standard error 0.01047.
Estimating the (2,α)-connectivity index of graphs
We start by stating the following observation, which is needed to prove our main results.
Remark 1. For a graph Gon medges, the number of paths of length 2 in Gis $- m + \frac{1}{2}{M_1}\left( G \right).$
Proof.For a path Pn on n >4 vertices each vertex is of degree either 1 or 2. Based on the degree of vertices on the path of length 2 in Pn we can partition E2(Pn). In Pn, path (1,2,2) appears 2 times and path (2,2,2) appears (n −4) times. Hence by Eq. (2) we get the required result.
Proof.For a wheel Wn+1 on n ≥3 vertices each vertex is of degree either 3 or n. Based on the degree of vertices on the path of length 2 in Wn+1 we can partition E2(Wn+1). In Wn+1, path (3,3,3) appears ntimes and path (3,3,n) appears n2+3n$\frac{{{n^2} + 3n}}{2}$ times. Therefore by Eq. (2), we get the required result.
Proof.For a complete bipartite graph Kr,s on r + svertices each vertex is of degree either ror s. Based on the degree of vertices on the path of length 2 in Kr,s we can partition E2(Kr,s). In Kr,s, path (r,s,r) appears $\frac{{rs\left( {s - 1} \right)}}{2}$ times and path (s,r,s) appears $\frac{{sr\left( {r - 1} \right)}}{2}$ times. Hence by Eq. (2), we get the required result.
Relations (6) and (7) were obtained by taking into account for each vertices v ∈ V(G), we have dG(v) n − 1 and Eq. (4), respectively.
Suppose that equality in (5) holds. Then inequalities (6) and (7) become equalities. From (6) we conclude that for every vertex v, dG (v) = n −1. Then from Eq. (7) and Lemma 8 it follows that G is a complete graph. Conversely, let G be a complete graph. Then it is easily verified that equality holds in (5).
Lemma 10
(c.f. [4]). Let G be a graph with n vertices and m edges. Then
Relations (9) and (10) were obtained by taking into accounting for each vertices v ∈ V(G), we have dG(v) ≥ δ and Eq. (8), respectively.
Suppose now that equality in (8) holds. Then inequalities (9) and (10) become equalities. From (9) we conclude that for every vertex v, dG(v) = δ. Then from Eq. (10) and Lemma 10 it follows that Gis a regular graph. Conversely, let Gbe a regular graph. Then it is easily verified that equality holds in (8).
Computing the (2,α)-connectivity index of line graphs of subdivision graphs of some families of graphs
In [16], Nadeem et al. obtained expressions for certain topological indices of the line graphs of subdivision graphs of 2D-lattice, nanotube, and nanotorus of TUC4C8[p,q], where pand qdenote the number of squares in a row and the number of rows of squares, respectively in 2D-lattice, nanotube and nanotorus as shown in Figure 2 (a), (b) and (c)respectively. The numbers of vertices and edges of 2D-lattice, nanotube and nanotorus of TUC4C8[p,q] are given in Table 2. Readers interested in other information on nanostructures can be referred to [2, 5–9, 11].
Number of vertices and edges.
Graph
Number of vertices
Number of edges
2D-lattice of TUC4C8 [p,q]
4pq
6pq − p − q
TUC4C8[p,q] nanotube
4pq
6 pq — p
TUC4C8[p,q] nanotorus
4pq
6pq
In [20, 21], Ranjini et al. presented explicit formula for computing the Shultz index and Zagreb indices of the subdivision graphs of the tadpole, wheel and ladder graphs. In 2015, Su and Xu [23] calculated the general sum-connectivity index and coindex of the L(S(Tn,k)), L(S(Wn)) and L(S(Ln)). In [11], Nadeem et al. derived some exact formulas for ABC4 and GA5 indices of the line graphs of the tadpole, wheel and ladder graphs by using the notion of subdivision.
Lemma 12
(c.f. [16]). Let X be the line graph of the subdivision graph of 2D-lattice of TUC4C8[p,q]. Then M1(X) = 108pq −38p −38q.
Theorem 13
Let X be the line graph of the subdivision graph of 2D-lattice of TUC4C8[p,q]. Then2χα(X) = 8α+1 + 4(12α + 2 ·18α)(p + q −2) + 27α(36pq −26p −26q + 16).
Proof.The subdivision graph of 2D-lattice of TUC4C8[p,q] and the graph Xare shown in Fig. 3 (a) and (b), respectively. In Xthere are total 2(6pq− p−q) vertices each vertex is of degree either 2 or 3 and 18pq−5p−5qedges. From Observation 1 and Lemma 12, we get 36pq −14p −14qof paths of length 2 in X. Based on the degree of vertices on the path of length 2 in Xwe can partition E2(X) as shown in Table 3. Apply Eq. (2) to Table 3 and get the required result.
Partition of paths of length 2 of the graph X.
(dx(u), dX (v), dX (w)) where uvw ∈ E2(X)
(2,2,2)
(2,2,3)
(3,3,2)
(3,3,3)
Number of paths of length 2 in X
8
4(p + q — 2)
8(p + q — 2)
(36 pq — 26 p — 26q + 16)
Lemma 14
(c.f. [16]). Let Y be the line graph of the subdivision graph of TUC4C8[p,q] nanotube. Then M1(Y) = 108pq −38p.
Theorem 15
Let Y be the line graph of the subdivision graph of TUC4C8[p,q] nanotube. Then2χα(Y) = 12α · 4p + 18α · 8p + 27α(36pq − 26p).
Proof.The subdivision graph of TUC4C8[p,q] nanotube and the graph Y are shown in Fig. 4 (a) and (b), respectively. In Y there are total 12pq − 2p vertices in which each vertex is of degree either 2 or 3 and 18pq − 5p edges. From Remark 1 and Lemma 14, we get 36pq − 14p number of paths of length 2 in Y. Based on the degree of vertices on the paths of length 2 in Y we can partition E2(Y) as shown in Table 4. Apply Eq. (2) to Table 4 and get the required result.
Partition of paths of length 2 of the graph Y.
(dY (u), dY(v), dY (w)) where uvw ∈ E2(Y)
(2,2,3)
(3,3,2)
(3,3,3)
Number of paths of length 2 in Y
4p
8p
(36pq — 26p)
Theorem 16
Let Z be the line graph of the subdivision graph of TUC4C8[p,q] nanotorus. Then2χα(Z) = 27α · 36pq.
Proof.The subdivision graph of TUC4C8[p,q] nanotorus and the graph Zare shown in Fig. 5 (a) and (b), respectively. Since Zis a 3-regular graph with 12pq vertices and 18pq edges. Therefore by Theorem 4, we get the required result.
Lemma 17
(c.f. [20, 23]). Let A be a line graph of the subdivision graph of the tadpole graph Tn,k. ThenM1(A) = 8n + 8k + 12.
Theorem 18
Let A be a line graph of the subdivision graph of the tadpole graph Tn,k. Then
Proof.First of all, we consider graph A for n ≥ 3 and k > 1. In this graph there are total 2(n + k) vertices and 2n + 2k + 1 edges. From Remark 1 and Lemma 17, we get 2k + 2n + 5 of paths of length 2 in A. Based on the degree of vertices on the paths of length 2 in A we can partition E2(A) as shown in Table 6. Apply Eq. (2) to Table 6 and get the required result. By similar arguments we can obtain the expression of 2χα(A) for k = 1 from Table 5.
Partition of paths of length 2 of the graph A = L(S(Tn,k)) for k = 1
(dA(u), dA(v), dA (w)) where uvw ∈ E2(A)
(1,3,3)
(2,3,3)
(2,2,3)
(3,3,3)
(2,2,2)
Number of paths of length 2 in A
2
4
2
3
2n − 4
Partition of paths of length 2 of the graph A = L(S(Tn,k)) for k > 1
(dA(u), dA(v), dA(w)) where uvw ∈ E2(A)
(1,2,2)
(2,3,3)
(2,2,3)
(3,3,3)
(2,2,2)
Number of paths of length 2 in A
1
6
3
3
2n + 2k – 8
Lemma 19
(c.f. [20]). Let B be a line graph of the subdivision graph of the wheel graph Wn+1. Then M1(B) = n3 + 27n.
Theorem 20
Let B be a line graph of the subdivision graph of the wheel graph Wn+1. Then$^{2}\chi_{\alpha}(B)=7n\cdot 27^{\alpha}+n^{\alpha + 1}\cdot 9^{\alpha} \cdot 2+3^{\alpha}\cdot n^{2\alpha + 1}(n-1)+n^{3\alpha +1}\cdot \frac{(n-1)(n-2)}{2}$
Proof.The graph L(S(Wn+1)) contains 4(n + 1) vertices and $\frac{{{n^2} + 9n}}{2}$ edges. From Remark 1 and Lemma 19, we get $\frac{{{n^3} - {n^2} + 18n}}{2}$ number of paths of length 2 in B. Based on the degree of vertices on the paths of length 2 in Bwe can partition E2(B) as shown in Table 7. Apply Eq. (2) to Table 7 and get the required result.
(c.f. [20, 23]). Let C be a line graph of subdivision graph of a ladder graph with order n. Then M1(Z) = 54n −76.
Theorem 22
Let C be a line graph of subdivision graph of a ladder graph with order n. Then2χα(C) = 8α ·4 + 12α ·4 + 18α ·8 + 27α(18n −44).
Proof.The graph L(S(Ln)) contains 6n −4 vertices and $\frac{{18n - 20}}{2}$ edges. From Remark 1 and Lemma 21, we get 18n −28 number of paths of length 2 in C. Based on the degree of vertices on the paths of length 2 in Cwe can partition E2(C) as shown in Table 8. Apply Eq. (2) to Table 8 and get the required result.