The Number of 1-Nearly Independent Edge Subsets
نویسندگان
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
doi
10.22052/ijmc.2024.254977.1871چکیده
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.
