The number of 1-nearly independent edge subsets

2024/05/27 by Andriantiana, Eric O. D., Shozi, Zekhaya B. · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2405.17154

Abstract

Let G=(V(G),E(G)) be a graph with set of vertices V(G) and set of edges E(G). A subset S of E(G) is called a k-nearly independent edge subsets 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₁. Various properties of Z₁ are discussed. We characterise the two n-vertex trees with smallest Z₁, as well as the one with largest value. A conjecture on the n-vertex tree with second-largest Z₁ is proposed.

Cited by

• On the average size of 1-nearly independent vertex sets in graphs

Related

• The number of 1-nearly independent vertex subsets
• An improved lower bound on the number of 1-nearly independent vertex subsets
• The 1-nearly edge independence number of a graph
• The 1-nearly vertex independence number of a graph
• On the average size of 1-nearly independent vertex sets in graphs