An improved lower bound on the number of 1-nearly independent vertex subsets

2024/07/12 by Shozi, Zekhaya B.
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2407.09067

Abstract

Let G=(V(G),E(G)) be a graph with set of vertices V(G) and set of edges E(G). For k≥ 0 an integer, a subset I_k of V(G) is called a k-nearly independent vertex subset of G if I_k induces a subgraph of size k in G. The number of such subsets in G is denoted by σ_k(G). In this paper we continue the study of σ₁. In particular, we prove the lower bound on σ₁ for a connected graph that contains a cycle and also characterise the two extremal graphs. This improves the result obtained in [E. O. D. Andriantiana and Z. B. Shozi. The number of 1-nearly independent vertex subsets. Quaestiones Mathematicae, accepted].

Related

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