On the SDD and ISDD Indices

José Luis Palacios

Department of Electrical and Computer Engineering, The University of New Mexico, Albuquerque, USA.

DOI: 10.4236/ojapps.2024.142033                

Abstract

We find some upper bounds for the product of the SDD and ISDD indices, and discuss the graphs were the equalities are attained. Our bounds allow us to find new upper bounds for the ISDD index, using previously known lower bounds for the SDD index.

Keywords

Inverse Topological Descriptors, Schweitzer Inequality

1. Introduction

In what follows, a graph $G=\left(V\mathrm{,}E\right)$ will be a finite simple connected undirected graph with vertex set $V=\left\{\mathrm{1,2,}\cdots \mathrm{,}n\right\}$ , edge set E and degrees $\Delta =d_1\ge d_2\ge \cdots \ge d_n=\delta$ . A graph is d-regular if all its vertices have degree d; a graph is $\left(a\mathrm{,}b\right)$ -regular if its vertices have degree either a or b. Sometimes we will call these latter graphs semiregular, when the values of a and b are not needed explicitly. As we emphasized in [1] , as opposed to some other articles on the indices under study, we do not require that the semiregular graphs be bipartite. For all graph theoretical terms the reader is referred to reference [2] .

In Mathematical Chemistry, molecules are modeled using these graphs, where the vertices are the atoms and the atomic bonds are represented by the edges. Many topological indices, or descriptors, i.e., real-valued functions on the domain of all graphs, have been defined with the purpose of capturing physico-chemical properties of the molecules and classifying them according to the values of their indices. One such index is the symmetric division deg index, defined by

$SDD\left(G\right)={\displaystyle \underset{\left(i,j\right)\in E}{\sum }}\left(\frac{d_i}{d_j}+\frac{d_j}{d_i}\right)={\displaystyle \underset{\left(i,j\right)\in E}{\sum }}\frac{d_i^2+d_j^2}{d_i{d}_j},$ (1)

for any graph G, and introduced by Vukičević and Gašperov in [3] as one of the 148 so-called Adriatic indices. This index, which has a good predictive power for the total surface area of polychlorobiphenyls, has been studied in a number of articles, of which we mention [1] [4] [5] and [6] where additional references can be found.

In [7] we worked with a resistive relative of the SDD index, the mixed degree-Kirchhoff index defined as

$\hat{R}\left(G\right)={\displaystyle \underset{i<j}{\sum }}\left(\frac{d_i}{d_j}+\frac{d_j}{d_i}\right)R_{ij},$ (2)

where $R_{ij}$ is the effective resistance between vertices i and j when the graph is thought of as an electrical network, where all the edges have unit resistance. In that article we found the relation

${\displaystyle \underset{i<j}{\sum }}\left(\frac{d_i}{d_j}+\frac{d_j}{d_i}\right)=2\left|E\right|{\displaystyle \underset{i}{\sum }}\frac{1}{d_i}-n,$

that was used extensively in [1] and rediscovered in [8] .

Ghorbani et al. introduced in [8] the inverse symmetric division deg index, defined as

$ISDD\left(G\right)={\displaystyle \underset{\left(i,j\right)\in E}{\sum }}\frac{d_i{d}_j}{d_i^2+d_j^2},$

that uses the inverses of the quotients used in (1), and proved, among other things, a lower bound for the product of the SDD and ISDD indices, as well as lower bounds for the difference of the indices. Some optimal results for the ISDD index are found in [9] for unicyclic graphs, and in [10] for trees and chain graphs.

In this article we want to continue working with the interplay between the two indices proving an upper bound for their product, and studying the large family of graphs for which the equalities are attained. Additionally, we give two new upper bounds for the ISDD index using known lower bounds for the SDD index found in the literature.

2. The Results

For a general descriptor of the form

$D_p\left(G\right)={\displaystyle \underset{i=1}{\overset{N}{\sum }}}{c}_i^p,$

where the c_is are non-negative parameters of G, and for which $m\le c_i^p\le M$ , we found in [11] the following bounds:

Lemma 1. For any descriptor $D_p\left(G\right)$ we have

$N^2\le D_p\left(G\right)\cdot D_{-p}\left(G\right)\le N^2\frac{{\left(m+M\right)}^2}{4mM}\mathrm{.}$ (3)

Both equalities are attained in case $m=c_i^p=M$ for all $1\le i\le N$ . Also, the right equality is attained if n is even and the first $\frac{n}{2}$ of the $c_i^p$ s are equal to m and the other $\frac{n}{2}$ of the $c_i^p$ s are equal to M.

Also, if n is odd we have

$N^2\le D_p\left(G\right)\cdot D_{-p}\left(G\right)\le \frac{N^2{\left(M+m\right)}^2-{\left(M-m\right)}^2}{4mM}\mathrm{.}$ (4)

Both equalities are attained in case $m=c_i^p=M$ for all $1\le i\le N$ . Also, the right equality is attained if the first $\frac{n-1}{2}$ of the $c_i^p$ s are equal to m, the last $\frac{n-1}{2}$ of the $c_i^p$ s are equal to M, and the middle $c_i^p$ is either m or M.

The left inequalities are a consequence of the arithmetic-harmonic-mean inequality. The right inequalities are shown using Schweitzer inequality, originally found in [12] , and Lupaş inequality, a refinement of Schweitzer inequality

proved in [13] . Let us denote by $Q_{ij}$ the quotients $\frac{d_i{d}_j}{d_i^2+d_j^2}$ , for $\left(i\mathrm{,}j\right)\in E$ , and let $M={\max }_{i,j}{Q}_{ij}$ , $m={\min }_{i,j}{Q}_{ij}$ . Applying the lemma we have the following:

Theorem 1. For all G we have

${\left|E\right|}^2\le SDD\left(G\right)\cdot ISDD\left(G\right)\le \frac{{\left|E\right|}^2{\left(m+M\right)}^2}{4mM}\mathrm{,}$ (5)

where both equalities are attained if all quotients are equal, and the right equality is also attained attained if $\left|E\right|$ is even, and $\frac{\left|E\right|}{2}$ of the quotients are equal to m and the other $\frac{\left|E\right|}{2}$ are equal to M.

Also, if $\left|E\right|$ is odd, we have

${\left|E\right|}^2\le SDD\left(G\right)\cdot ISDD\left(G\right)\le \frac{{\left|E\right|}^2{\left(M+m\right)}^2-{\left(M-m\right)}^2}{4Mm}\mathrm{,}$ (6)

where the equality is attained if all quotients $Q_{ij}$ are equal, or if $\lfloor \frac{\left|E\right|}{2}\rfloor$ of them are equal to m and the rest are equal to M, or if $\lceil \frac{\left|E\right|}{2}\rceil$ of them are equal to m and the rest are equal to M.

We want to give sufficient conditions for the cases where the equalities in (5) and (6) are attained. As Ghorbani et al. noticed ( [8] , thm. 4), the quotients are all equal if the graph is regular or edge-transitive.

Regularity and edge-transitivity are sufficient but not necessary conditions for the right equalities of (5) and (6) to be attained: the natural condition here, other than regularity, is $\left(k\mathrm{,}r\right)$ -regularity. Obviously edge-transitivity guarantees $\left(k\mathrm{,}r\right)$ -regularity for some k and r, but the opposite is not necessarily true. Consider for example the graph built from two 4-cycles, or squares, S₁ and S₂, such that one vertex v₁ of S₁ is linked to another vertex v₂ of S₂ with a 2-path graph P₂, and the diagonally opposite vertices of v₁ and v₂ are linked with another P₂. Then this is a 10-vertex $\left(\mathrm{2,3}\right)$ -regular graph which is not edge-transitive, because not all edges are part of a square. Still, not even $\left(k\mathrm{,}r\right)$ -regularity is necessary. A more general condition would be that for all pairs of edges $\left(a\mathrm{,}b\right)$ and $\left(g\mathrm{,}h\right)$ , there is a positive integer q such that $d_a=q{d}_g$ and $d_b=q{d}_h$ . For example, the 9-vertex graph with incidence matrix

$A=\left(\begin{array}{ccccccccc}0& 1& 0& 0& 0& 0& 0& 0& 0\\ 1& 0& 1& 0& 0& 0& 0& 0& 0\\ 0& 1& 0& 1& 1& 1& 0& 0& 0\\ 0& 0& 1& 0& 0& 0& 1& 0& 0\\ 0& 0& 1& 0& 0& 0& 1& 0& 0\\ 0& 0& 1& 0& 0& 0& 1& 0& 0\\ 0& 0& 0& 1& 1& 1& 0& 1& 0\\ 0& 0& 0& 0& 0& 0& 1& 0& 1\\ 0& 0& 0& 0& 0& 0& 0& 1& 0\end{array}\right)$

is neither edge-transitive nor $\left(k\mathrm{,}r\right)$ -regular. Two edges have degrees 1 and 2 and eight edges have degrees 2 and 4, so that all quotients satisfy

$\frac{d_u{d}_v}{d_u^2+d_v^2}=\frac{2}{5}.$

Now let us look at a family of graphs that have exactly two different quotients, and attain the equalities in (5) and (6). For $k\ge 3$ , consider the squares $S_i$ , $1\le i\le k$ , and link S₁ with S₂ with a P₄ and for all other $2\le i\le k-1$ , link $S_i$ to $S_{i+1}$ with a P₈, using always diagonally opposite vertices for the linking. It is easy to see that the total number of $\left(\mathrm{2,3}\right)$ edges is equal to the total number of $\left(\mathrm{2,2}\right)$ edges, which is $6\left(k-1\right)$ . Replacing the P₄ with a P₃ produces a graph

where $\lceil \frac{n}{2}\rceil$ of the edges have quotient m and the other $\lfloor \frac{n}{2}\rfloor$ edges have quotient M; finally, replacing the P₄ with a P₅ produces a graph where $\lceil \frac{n}{2}\rceil$ of the edges have quotient M and the other $\lfloor \frac{n}{2}\rfloor$ edges have quotient m.

Thus, these are examples of graphs where the right equalities in (5) and (6) are attained, in all three possible cases, and all conditions of theorem 1 are nonempty. As a final application, we give a couple of upper bounds for the ISDD index using known lower bounds for the SDD index found in the literature.

Theorem 2. For any graph G with p pendent vertices and minimum non-pendent vertex degree ${\delta }_1$ we have

$ISDD\left(G\right)\le \frac{{\left|E\right|}^2{\left(m+M\right)}^2}{4mM\left[p\left(\frac{{\delta }_1^2+1}{{\delta }_1}\right)+2\left(\left|E\right|-p\right)\right]}$ (7)

where the equality holds for any regular graph and for the star graph.

Proof. Use theorem 3.3 in [6] and (5) in our Theorem 1.

In the case that G is regular, all quotients are equal to $\frac{1}{2}$ , and thus $ISSD\left(G\right)=\frac{\left|E\right|}{2}$ ; on the other hand, on account of the facts that $m=M=\frac{1}{2}$ and $p=0$ , the right side also becomes $\frac{\left|E\right|}{2}$ .

In the case that G is the star graph, all quotients are equal to $\frac{n-1}{1+{\left(n-1\right)}^2}$ , and thus

$ISSD\left(G\right)=\frac{{\left(n-1\right)}^2}{1+{\left(n-1\right)}^2}\mathrm{,}$

which is equal to the value of the bound, on account of the facts that $m=M$ and $p=\left|E\right|=n-1$ $•$

The first and second Zagreb indices M₁ and M₂ were defined in [14] and [15] , respectively, as

$M_1\left(G\right)={\displaystyle \underset{i\in V}{\sum }}{d}_i^2={\displaystyle \underset{\left(i,j\right)\in E}{\sum }}\left(d_i+d_j\right),$

and

$M_2\left(G\right)={\displaystyle \underset{\left(i\mathrm{,}j\right)\in E}{\sum }}{d}_i{d}_j\mathrm{.}$

With these indices we have the following:

Theorem 3. For any graph G we have

$ISDD\left(G\right)\le \frac{{\left|E\right|}^2{\left(m+M\right)}^2}{4mM\left(\frac{M_1^2\left(G\right)}{M_2\left(G\right)}-2\left|E\right|\right)}\mathrm{,}$ (8)

where the equality holds for any regular or semiregular graphs.

Proof. Use theorem 3.1 in [4] and (5) in our Theorem 1.

In the case that G is d-regular, $ISSD\left(G\right)=\frac{\left|E\right|}{2}=\frac{nd}{4}$ . It is easy to see that this is also the value of the bound on the right side, because $m=M=\frac{1}{2}$ , $M_1\left(G\right)=n{d}^2$ and $M_2\left(G\right)=\frac{n{d}^3}{2}$ .

In the case that G is $\left(a\mathrm{,}b\right)$ -regular, $ISSD\left(G\right)=\left|E\right|\frac{ab}{a^2+b^2}$ . Since $m=M$ , the bound on the right becomes

$\frac{{\left|E\right|}^2}{\frac{M_1^2\left(G\right)}{M_2\left(G\right)}-2\left|E\right|}\mathrm{,}$ (9)

but

$\frac{M_1^2\left(G\right)}{M_2\left(G\right)}-2\left|E\right|=\frac{{\left(a+b\right)}^2{\left|E\right|}^2}{ab\left|E\right|}-2\left|E\right|=\frac{\left(a^2+b^2\right)\left|E\right|}{ab},$

and inserting this result into (9) gives us the same value for the upper bound obtained for $ISSD\left(G\right)$ $•$

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Palacios, J.L. (2019) New Upper Bounds for the Symmetric Division Deg Index of Graphs. Discrete Mathematics Letters, 2, 52-56.
[2]	Wilson, R.J. (1972) Introduction to Graph Theory. Oliver & Boyd, Edinburgh.
[3]	Vukičević, D. and Gašperov, M. (2010) Bond Additive Modeling 1. Adriatic Indices. Croatica Chemica Acta, 83, 243-260.
[4]	Das, K.C., Matejić, M., Milovanović, E. and MIlovanović, I. (2019) Bounds for Symmetric Division Deg Index of Graphs. Filomat, 33, 683-698. https://doi.org/10.2298/FIL1903683D
[5]	Furtula, B., Das, K.C. and Gutman, I. (2018) Comparative Analysis of Symmetric Division Deg Index as Potentially Useful Molecular Descriptor. International Journal of Quantum Chemistry, 118, e25659. https://doi.org/10.1002/qua.25659
[6]	Gupta, C.K., Lokesha, V., Shwetha, B.S. and Ranjini, P.S. (2016) On the Symmetric Division Deg Index of Graph. Southeast Asian Bulletin of Mathematics, 40, 59-80.
[7]	Bianchi, M., Cornaro, A., Palacios, J.L. and Torriero, A. (2016) Upper and Lower Bounds for the Mixed Degree-Kirchhoff Index. Filomat, 30, 2351-2358. https://doi.org/10.2298/FIL1609351B
[8]	Ghorbani, M., Zangi, S. and Amraei, N. (2021) New Results on Symmetric Division Deg Index. Journal of Computational and Applied Mathematics, 65, 161-176. https://doi.org/10.1007/s12190-020-01386-9
[9]	Albalahi, A.M. and Ali, A. (2022) On the Inverse Symmetric Division Deg Index of Unicyclic Graphs. Computation, 10, 181. https://doi.org/10.3390/computation10100181
[10]	Raza, Z., Saha, L. and Das, K.C. (2023) On Inverse Symmetric Division Deg Index of Graphs. RAIRO, 57, 3223-3236. https://doi.org/10.1051/ro/2023181
[11]	Palacios, J.L. (2024) More on Topological Indices and Their Reciprocals. MATCH Communications in Mathematical and in Computer Chemistry. 92, 55-63. https://doi.org/10.46793/match.92-1.055P
[12]	Schweitzer, P. (1914) An Inequality about the Arithmetic Mean. Matematikai és Physikai Lapok, 23, 257-261.
[13]	Lupaş, A. (1972) A Remark on the Schweitzer and Kantorovich Inequalities. Publikacije Elektrotehničkog Fakulteta Univerziteta u Beogradu, Serija: Matematica i fizika, 383, 13-14.
[14]	Gutman, I. and Trinajstić, N. (1972) Graph Theory and Molecular Orbitals. Total π-Electron Energy of Alternant Hydrocarbons. Chemical Physics Letters, 17, 535-538. https://doi.org/10.1016/0009-2614(72)85099-1
[15]	Gutman, I., Ruscić, B., Trinajstić, N. and Wilcox, C.F. (1975) Graph Theory and Molecular Orbitals. XII. Acyclic Ployenes. The Journal of Chemical Physics, 62, 3399-3405. https://doi.org/10.1063/1.430994