Let $ G = (V(G), E(G)) $ be a graph with a vertex set $ V(G) $ and an edge set $ E(G) $. For every injective vertex labeling $ f:V\left (G \right)\to \mathbb{Z} $, there are two induced edge labelings denoted by $ f^{+} :E\left (G \right)\to \mathbb{Z} $ and $ f^{-} :E\left (G \right)\to \mathbb{Z} $. These two edge labelings $ f^{+} $ and $ f^{-} $ are defined by $ f^{+}(uv) = f(u)+f(v) $ and $ f^{-}(uv) = \left |f(u)-f(v)\right | $ for each $ uv\in E(G) $ with $ u, v\in V(G) $. The sum index and difference index of $ G $ are induced by the minimum ranges of $ f^{+} $ and $ f^{-} $, respectively. In this paper, we obtain the properties of sum and difference index labelings. We also improve the bounds on the sum indices and difference indices of regular graphs and induced subgraphs of graphs. Further, we determine the sum and difference indices of various families of graphs such as the necklace graphs and the complements of matchings, cycles and paths. Finally, we propose some conjectures and questions by comparison.
Citation: Yuan Zhang, Haiying Wang. Some new results on sum index and difference index[J]. AIMS Mathematics, 2023, 8(11): 26444-26458. doi: 10.3934/math.20231350
Let $ G = (V(G), E(G)) $ be a graph with a vertex set $ V(G) $ and an edge set $ E(G) $. For every injective vertex labeling $ f:V\left (G \right)\to \mathbb{Z} $, there are two induced edge labelings denoted by $ f^{+} :E\left (G \right)\to \mathbb{Z} $ and $ f^{-} :E\left (G \right)\to \mathbb{Z} $. These two edge labelings $ f^{+} $ and $ f^{-} $ are defined by $ f^{+}(uv) = f(u)+f(v) $ and $ f^{-}(uv) = \left |f(u)-f(v)\right | $ for each $ uv\in E(G) $ with $ u, v\in V(G) $. The sum index and difference index of $ G $ are induced by the minimum ranges of $ f^{+} $ and $ f^{-} $, respectively. In this paper, we obtain the properties of sum and difference index labelings. We also improve the bounds on the sum indices and difference indices of regular graphs and induced subgraphs of graphs. Further, we determine the sum and difference indices of various families of graphs such as the necklace graphs and the complements of matchings, cycles and paths. Finally, we propose some conjectures and questions by comparison.
| [1] |
J. Harrington, E. Henninger-Voss, K. Karhadkar, E. Robinson, T. W. H. Wong, Sum index and difference index of graphs, Discrete Appl. Math., 325 (2023), 262–283. https://doi.org/10.1016/j.dam.2022.10.020 doi: 10.1016/j.dam.2022.10.020
|
| [2] |
M. Randić, On characterization of molecular branching, J. Am. Chem. Soc., 97 (1975), 6609–6615. https://doi.org/10.1021/ja00856a001 doi: 10.1021/ja00856a001
|
| [3] |
Y. Shang, Sombor index and degree-related properties of simplicial networks, Appl. Math. Comput., 419 (2022), 126881. https://doi.org/10.1016/j.amc.2021.126881 doi: 10.1016/j.amc.2021.126881
|
| [4] |
E. Estrada, Atom-bond connectivity and the energetic of branched alkanes, Chem. Phys. Lett., 463 (2008), 422–425. https://doi.org/10.1016/j.cplett.2008.08.074 doi: 10.1016/j.cplett.2008.08.074
|
| [5] | E. Estrada, L. Torres, L. Rodríguez, I. Gutman, An atom-bond connectivity index: Modelling the enthalpy of formation of alkanes, Indian J. Chem., 37 (1998), 849–855. |
| [6] | I. Gutman, K. C. Das, The first Zagreb index 30 years after, MATCH Commun. Math. Comput. Chem., 50 (2004), 83–92. |
| [7] |
M. Rizwan, A. A. Bhatti, M. Javaid, Y. Shang, Conjugated tricyclic graphs with maximum variable sum exdeg index, Heliyon, 9 (2023), e15706. https://doi.org/10.1016/j.heliyon.2023.e15706 doi: 10.1016/j.heliyon.2023.e15706
|
| [8] |
I. Gutman, N. Trinajstić, Graph theory and molecular orbitals. Total $\phi$-electron energy of alternant hydrocarbons, Chem. Phys. Lett., 17 (1972), 535–538. https://doi.org/10.1016/0009-2614(72)85099-1 doi: 10.1016/0009-2614(72)85099-1
|
| [9] | F. Harary, Sum graphs and difference graphs, In: Proceedings of the twentieth southeastern conference on combinatorics, graph Theory, and computing, 72 (1990), 101–108. |
| [10] | H. Wang, J. Gao, The sum numbers and the integral sum numbers of $\overline{P_{n}}$ and $\overline{F_{n}}$, Ars Combin., 96 (2010), 9–31. |
| [11] | H. Wang, J. Gao, The sum numbers and the integral sum numbers of $\overline{C_{n}}$ and $\overline{W_{n}}$, Ars Combin., 96 (2010), 479–488. |
| [12] | J. A. MacDougall, M. Miller, S. Slamin, W. D. Wallis, Vertex-magic total labelings of graphs, Util. Math., 61 (2002), 3–21. |
| [13] | R. Ponraj, J. V. X. Parthipan, Pair sum labeling of graphs, J. Indian Acad. Math., 32 (2010), 587–595. |
| [14] |
J. Harrington, T. W. H. Wong, On super totient numbers and super totient labelings of graphs, Discrete Math., 343 (2020), 111670. https://doi.org/10.1016/j.disc.2019.111670 doi: 10.1016/j.disc.2019.111670
|
| [15] |
J. Haslegrave, Sum index, difference index and exclusive sum number of graphs, Graph Combinatoric., 39 (2023), 32. https://doi.org/10.1007/s00373-023-02624-0 doi: 10.1007/s00373-023-02624-0
|
Figures(7) / Tables(2)
Yuan Zhang, Haiying Wang. Some new results on sum index and difference index[J]. AIMS Mathematics, 2023, 8(11): 26444-26458. doi: 10.3934/math.20231350
DownLoad: