University of Kashan Iranian Journal of Mathematical Chemistry 2228-6489 16 1 2025 03 01 The Number of 1-Nearly Independent Edge Subsets 65 84 114723 10.22052/ijmc.2024.254977.1871 EN Eric O‎. ‎D‎. ‎ Andriantiana Department of Mathematics (Pure and Applied)‎, ‎Rhodes University‎, ‎Makhanda‎, ‎6140 South Africa Zekhaya B‎. ‎Shozi School of Mathematics‎, ‎Statistics and Computer Science‎, ‎University of KwaZulu-Natal‎, ‎Durban‎, ‎4000 South Africa Journal Article 2024 05 29 ‎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‎.<br />‎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‎. ‎ https://ijmc.kashanu.ac.ir/article_114723_2e396ade9272032e67bd55589bf307d7.pdf