(β ,α)−Connectivity Index of Graphs

For a path P_n on n > 4 vertices,

2χα(Pn)=2⋅4α+8α⋅(n−4)$$\begin{array}{} \displaystyle ^2{\chi _\alpha }\left( {{P_n}} \right) = 2 \cdot {4^\alpha } + {8^\alpha } \cdot \left( {n - 4} \right) \end{array}$$

Proof.For a path P_n 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 P_n we can partition E₂(P_n). In P_n, 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.

For a wheel graph W_n+1,

χα(Wn+1)=27α2⋅n+(9n)α⋅n2+3n2.$$\begin{array}{} {}_{}^2{\chi _\alpha }\left( {{W_{n + 1}}} \right) = {27^\alpha } \cdot n + {\left( {9n} \right)^\alpha } \cdot \frac{{{n^2} + 3n}}{2}. \end{array}$$

Proof.For a wheel W_n+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 W_n+1 we can partition E₂(W_n+1). In W_n+1, path (3,3,3) appears ntimes and path (3,3,n) appears ⁿ²+3nn2+3n2$\frac{{{n^2} + 3n}}{2}$ times. Therefore by Eq. (2), we get the required result.

For a complete bipartite graph K_r,s,

χα2(Kr,s)=r2α+1⋅sα+1⋅(s−1)2+rα+1⋅s2α+1⋅(r−1)2$$\begin{array}{} \displaystyle {}_{}^2{\chi _\alpha }\left( {{K_{r,s}}} \right) = \frac{{{r^{2\alpha + 1}} \cdot {s^{\alpha + 1}} \cdot \left( {s - 1} \right)}}{2} + \frac{{{r^{\alpha + 1}} \cdot {s^{2\alpha + 1}} \cdot \left( {r - 1} \right)}}{2} \end{array}$$

Proof.For a complete bipartite graph K_r,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 K_r,s we can partition E₂(K_r,s). In K_r,s, path (r,s,r) appears rs(s−1)2$\frac{{rs\left( {s - 1} \right)}}{2}$ times and path (s,r,s) appears sr(r−1)2$\frac{{sr\left( {r - 1} \right)}}{2}$ times. Hence by Eq. (2), we get the required result.

Let G be a r-regular graph on n vertices,

χα2(G)=r3α+1⋅n(r−1)2.$$\begin{array}{} \displaystyle {}_{}^2{\chi _\alpha }\left( G \right) = {r^{3\alpha + 1}} \cdot \frac{{n\left( {r - 1} \right)}}{2}. \end{array}$$

Proof.Since Gis a r-regular graph, the path (r,r,r) appears nr(r−1)2$\frac{{nr\left( {r - 1} \right)}}{2}$

times in G. Therefore by Eq. (2), we get the required result.

For a cycle C_n, ²χ_a(C_n) = 8^a · n.

For a complete graph K_n, χα2(Kn)=n(n−2)⋅(n−1)3α+12.${}_{}^2{\chi _\alpha }\left( {{K_n}} \right) = \frac{{n\left( {n - 2} \right) \cdot {{(n - 1)}^{3\alpha + 1}}}}{2}.$

(c.f. [3]). Let G be a graph with n vertices and m edges. Then

M1(G)≤m(2mn−1+n−2).$$\begin{array}{} \displaystyle {M_1}\left( G \right) \le m\left( {\frac{{2m}}{{n - 1}} + n - 2} \right). \end{array}$$(4)

(c.f. [4]). Let G be a graph with n vertices and m edges, m > 0. Then the equality

M1(G)=m(2mn−1+n−2)$$\begin{array}{} \displaystyle {M_1}\left( G \right) = m\left( {\frac{{2m}}{{n - 1}} + n - 2} \right) \end{array}$$

holds if and only if G is isomorphic to star graph S_n or K_n or K_n−1 ∪ K₁.

Let G be a graph with n vertices and m edges. Then

χ12(G)≤(n−1)3α⋅m(mn−1+n−42)$$\begin{array}{} \displaystyle {}_{}^2{\chi _1}\left( G \right) \le {(n - 1)^{3\alpha }} \cdot m\left( {\frac{m}{{n - 1}} + \frac{{n - 4}}{2}} \right) \end{array}$$(5)

the equality holds if and only if G is isomorphic to K_n.

Proof.

χα2(G)=Σuvw∈E2(G)[dG(u)dG(v)dG(w)]α≤Σuvw∈E2(G)(n−1)3α$$\begin{array}{} \displaystyle \begin{array}{*{20}{l}} {{}_{}^2{\chi _\alpha }(G)} & { = \mathop {\rm{\Sigma }}\limits_{uvw \in {E_2}(G)} {{[{d_G}(u){d_G}(v){d_G}(w)]}^\alpha }} \\ {} & { \le \mathop {\rm{\Sigma }}\limits_{uvw \in {E_2}(G)} {{(n - 1)}^{3\alpha }}} \\ \end{array} \end{array}$$(6)

=(n−1)3α(−m+12M1(G))≤(n−1)3α(−m+12m(2mn−1+n−2))=(n−1)3α⋅m(mn−1+n−42).$$\begin{array}{} \displaystyle \begin{array}{*{20}{c}} {} \hfill & { = {{(n - 1)}^{3\alpha }}( - m + \frac{1}{2}{M_1}(G))} \hfill \\ {} \hfill & { \le {{(n - 1)}^{3\alpha }}( - m + \frac{1}{2}m(\frac{{2m}}{{n - 1}} + n - 2))} \hfill \\ {} \hfill & { = {{(n - 1)}^{3\alpha }} \cdot m(\frac{m}{{n - 1}} + \frac{{n - 4}}{2}).} \hfill \\ \end{array} \end{array}$$(7)

Relations (6) and (7) were obtained by taking into account for each vertices v ∈ V(G), we have d_G(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, d_G (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).

(c.f. [4]). Let G be a graph with n vertices and m edges. Then

M1(G)≥2m(2p+1)−pn(1+p),wherep=⌊2mn⌋,$$\begin{array}{} \displaystyle \begin{array}{*{20}{c}} {M_1}(G) \ge 2m(2p + 1) - pn(1 + p),\; where\; p = \lfloor\frac{{2m}}{n}\rfloor, \end{array} \end{array}$$

and the equality holds if and only if the difference of the degrees of any two vertices of graph G is at most one.

Let G be a graph with n vertices, m edges and the minimum vertex degree δ. Then

2χα(G)≥δ3α2(4mp−pn(p+1)),wherep=⌊2mn⌋,$$\begin{array}{} \displaystyle {}_{}^2{\chi _\alpha }\left( G \right) \ge \frac{{{\delta ^{3\alpha }}}}{2}(4mp - pn\left( {p + 1} \right)),\; where\; p = \left\lfloor {\frac{{2m}}{n}} \right\rfloor, \end{array}$$(8)

and the equality holds if and only if G is a regular graph.

Proof.

χα2(G)=Σuvw∈E2(G)[dG(u)dG(v)dG(w)]α≥Σuvw∈E2(G)δ3α$$\begin{array}{} \displaystyle \begin{array}{*{20}{l}} {{}_{}^2{\chi _\alpha }(G)} & { = \mathop {{\Sigma }}\limits_{uvw \in {E_2}(G)} {{[{d_G}(u){d_G}(v){d_G}(w)]}^\alpha }} \\ {} & { \ge \mathop {{\Sigma }}\limits_{uvw \in {E_2}(G)} {\delta ^{3\alpha }}} \\ \end{array} \end{array}$$(9)

=δ3α(−m+12M1(G))≥δ3α(−m+12(2m(2p+1)−pn(1+p)))=δ3α2(4mp−pn(p+1)).$$\begin{array}{} \displaystyle \begin{array}{*{20}{c}} {} \hfill & { = {\delta ^{3\alpha }}( - m + \frac{1}{2}{M_1}(G))} \hfill \\ {} \hfill & { \ge {\delta ^{3\alpha }}( - m + \frac{1}{2}(2m(2p + 1) - pn(1 + p)))} \hfill \\ {} \hfill & { = \frac{{{\delta ^{3\alpha }}}}{2}(4mp - pn(p + 1)).} \hfill \\ \end{array} \end{array}$$(10)

Relations (9) and (10) were obtained by taking into accounting for each vertices v ∈ V(G), we have d_G(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, d_G(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).

(c.f. [16]). Let X be the line graph of the subdivision graph of 2D-lattice of TUC₄C₈[p,q]. Then M₁(X) = 108pq −38p −38q.

Let X be the line graph of the subdivision graph of 2D-lattice of TUC₄C₈[p,q]. Then²χ_α(X) = 8^α+1 + 4(12^α + 2 ·18^α)(p + q −2) + 27^α(36pq −26p −26q + 16).

Proof.The subdivision graph of 2D-lattice of TUC₄C₈[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 E₂(X) as shown in Table 3. Apply Eq. (2) to Table 3 and get the required result.

Fig. 3

Table 3

Partition of paths of length 2 of the graph X.

(c.f. [16]). Let Y be the line graph of the subdivision graph of TUC₄C₈[p,q] nanotube. Then M₁(Y) = 108pq −38p.

Let Y be the line graph of the subdivision graph of TUC₄C₈[p,q] nanotube. Then²χ_α(Y) = 12^α · 4p + 18^α · 8p + 27^α(36pq − 26p).

Proof.The subdivision graph of TUC₄C₈[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 E₂(Y) as shown in Table 4. Apply Eq. (2) to Table 4 and get the required result.

Fig. 4

Table 4

Partition of paths of length 2 of the graph Y.

Let Z be the line graph of the subdivision graph of TUC₄C₈[p,q] nanotorus. Then²χ_α(Z) = 27^α · 36pq.

Proof.The subdivision graph of TUC₄C₈[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.

Fig. 5

(c.f. [20, 23]). Let A be a line graph of the subdivision graph of the tadpole graph T_n,k. ThenM₁(A) = 8n + 8k + 12.

Let A be a line graph of the subdivision graph of the tadpole graph T_n,k. Then

2χαA=4α+18α⋅6+12α⋅3+27α⋅3+8α⋅2n+2k−8fork>1.9α+18α⋅4+12α⋅2+27α⋅3+8α⋅2n−4fork=1.$$\begin{array}{l} \displaystyle {}_{}^2{\chi _\alpha }\left( A \right) = \left\{ \begin{array}{*{20}{c}} {{4^\alpha } + {{18}^\alpha } \cdot 6 + {{12}^\alpha } \cdot 3 + {{27}^\alpha } \cdot 3 + {8^\alpha } \cdot \left( {2n + 2k - 8} \right)}&{for \; k \gt 1.}\\ {{9^\alpha } + {{18}^\alpha } \cdot 4 + {{12}^\alpha } \cdot 2 + {{27}^\alpha } \cdot 3 + {8^\alpha } \cdot \left( {2n - 4} \right)}&{for \; k = 1.} \end{array}\right. \end{array}$$

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 E₂(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 ²χ_α(A) for k = 1 from Table 5.

Table 5

Partition of paths of length 2 of the graph A = L(S(T_n,k)) for k = 1

Table 6

Partition of paths of length 2 of the graph A = L(S(T_n,k)) for k > 1

(c.f. [20]). Let B be a line graph of the subdivision graph of the wheel graph W_n+1. Then M₁(B) = n³ + 27n.

Let B be a line graph of the subdivision graph of the wheel graph W_n+1. Thenχα2(B)=7n⋅27α+nα+1⋅9α⋅2+3α⋅n2α+1(n−1)+n3α+1⋅n(n−1)(n−2)2.$^{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(W_n+1)) contains 4(n + 1) vertices and n2+9n2$\frac{{{n^2} + 9n}}{2}$ edges. From Remark 1 and Lemma 19, we get n3−n2+18n2$\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 E₂(B) as shown in Table 7. Apply Eq. (2) to Table 7 and get the required result.

Table 7

Partition of paths of length 2 of the graph B.

(c.f. [20, 23]). Let C be a line graph of subdivision graph of a ladder graph with order n. Then M₁(Z) = 54n −76.

Let C be a line graph of subdivision graph of a ladder graph with order n. Then²χ_α(C) = 8^α ·4 + 12^α ·4 + 18^α ·8 + 27^α(18n −44).

Proof.The graph L(S(L_n)) contains 6n −4 vertices and 18n−202$\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 E₂(C) as shown in Table 8. Apply Eq. (2) to Table 8 and get the required result.

Table 8

Partition of paths of length 2 of the graph C.