The Number of 1-Nearly Independent Edge Subsets

Document Type : Research Paper

Authors

1 Department of Mathematics (Pure and Applied)‎, ‎Rhodes University‎, ‎Makhanda‎, ‎6140 South Africa

2 School of Mathematics‎, ‎Statistics and Computer Science‎, ‎University of KwaZulu-Natal‎, ‎Durban‎, ‎4000 South Africa

Abstract

‎Let $G=(V(G),E(G))$ be a graph with the set of vertices $V(G)$ and the set of edges $E(G)$‎. ‎A subset $S$ of $E(G)$ is called a $k$-nearly independent edge subset if there are exactly $k$ pairs of elements of $S$ that share a common end‎. ‎$Z_k(G)$ is the number of such subsets‎.
‎This paper studies $Z_1$‎. ‎Various properties of $Z_1$ are discussed‎. ‎We characterize the two $n$-vertex trees with the smallest $Z_1$‎, ‎as well as the one with the largest value‎. ‎A conjecture on the $n$-vertex tree with the second-largest $Z_1$ is proposed‎. ‎

Keywords

Main Subjects

References

[1] M. A. Henning and A. Yeo, Total Domination in Graphs, Springer Monographs in Mathematics. Springer New York, 2013.
[2] E. O. D. Andriantiana and Z. B. Shozi, The number of 1-nearly independent vertex subsets, arXiv preprint arXiv:2309.05356v1, 2023.
[3] S. Wagner and I. Gutman, Maxima and minima of the hosoya index and the merrifieldsimmons index: a survey of results and techniques, Acta Appl. Math. 112 (2010) 323–346.
[4] H. Hosoya, Topological index. A newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons, Bull. Chem. Soc. Jpn. 44 (1971) 2332–2339, https://doi.org/10.1246/bcsj.44.2332.
[5] Y.-d. Gao and H. Hosoya, Topological index and thermodynamic properties. iv. size dependency of the structure-activity correlation of alkanes, Bull. Chem. Soc. Jpn. 61 (1988) 3093–3102, https://doi.org/10.1246/bcsj.61.3093.
[6] I. Gutman, B. Furtula, D. Vidovic and H. Hosoya, A concealed property of the topological index z, Bull. Chem. Soc. Jpn. 77 (2004) 491–496.
[7] I. Gutman, T. Yamaguchi, and H. Hosoya, Topological index as applied to $\pi$-electronic systems. iv. on the topological factors causing non-uniform $\pi$-electron charge distribution in non-alternant hydrocarbons, Bull. Chem. Soc. Jpn. 49 (1976) 1811–1816, https://doi.org/10.1246/bcsj.49.1811.
[8] H. Hosoya, Graphical enumeration of the coefficients of the secular polynomials of the hückel molecular orbitals, Theor. Chim. Acta (Berl.) 25 (1972) 215–222.
[9] H. Hosoya and K. Hosoi, Topological index as applied to $\pi$-electronic systems. iii. mathematical relations among various bond orders, J. Chem. Phys. 64 (1976) 1065–1073, https://doi.org/10.1063/1.432316.
[10] H. Hosoya, K. Hosoi and I. Gutman, A topological index for the total $\pi$-electron energy: proof of a generalised hückel rule for an arbitrary network, Theor. Chim. Acta (Berl). 38 (1975) 37–47.
[11] E. O. D. Andriantiana, Energy, hosoya index and merrifield–simmons index of trees with prescribed degree sequence, Discrete Appl. Math. 161 (2013) 724–741, https://doi.org/10.1016/j.dam.2012.10.010.
[12] E. O. D. Andriantiana, The Number of Independent Subsets and the Energy of Trees, PhD thesis, Stellenbosch: University of Stellenbosch, 2010.
[13] I. Gutman, Acyclic systems with extremal hückel $\pi$-electron energy, Theoret. Chim. Acta, 45 (1977) 79–87, https://doi.org/10.1007/BF00552542.
[14] I. Gutman and S. Wagner, The matching energy of a graph, Discret. Appl. Math. 160 (2012) 2177–2187, https://doi.org/10.1016/j.dam.2012.06.001.
[15] E. O. D. Andriantiana, More trees with large energy, MATCH Commun. Math. Comput. Chem. 68 (2012) 675–695.
Iranian Journal of Mathematical Chemistry
Volume 16, Issue 1
March 2025
Pages 65-84

Files

Share

How to cite

Statistics