The 1-nearly edge independence number of a graph

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

paper · doi:10.48550/arxiv.2407.08870

Abstract

Let G = (V(G), E(G)) be a graph. The maximum cardinality of a set M_k ⊆ E(G) such that M_k contains exactly k-pairs of adjacent edges of G is called the k-nearly edge independence number of G, and is denoted by α'_k(G). In this paper we study α₁'(G). In particular, we prove a tight lower (resp. upper) bound on α₁(G) if G is a graph with given number of vertices. Furthermore, we present a characterisation of the general (resp. connected) graphs with given number of vertices and smallest 1-nearly edge independence number. Lastly, we pose an open problem for further exploration of this study.

Related

• The 1-nearly vertex independence number of a graph
• The number of 1-nearly independent edge subsets
• An improved lower bound on the number of 1-nearly independent vertex subsets
• The number of 1-nearly independent vertex subsets
• A sharp upper bound for the independence number