The 1-nearly vertex independence number of a graph

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

paper · doi:10.48550/arxiv.2406.16668

Abstract

Let G be a graph with vertex set V(G) and edge set E(G). A set I₀(G) ⊆ V(G) is a vertex independent set if no two vertices in I₀(G) are adjacent in G. We study α₁(G), which is the maximum cardinality of a set I₁(G) ⊆ V(G) that contains exactly one pair of adjacent vertices of G. We call I₁(G) a 1-nearly vertex independent set of G and α₁(G) a 1-nearly vertex independence number of G. We provide some cases of explicit formulas for α₁. Furthermore, we prove a tight lower (resp. upper) bound on α₁ for graphs of order n. The extremal graphs that achieve equality on each bound are fully characterised.

Related

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