The $1$-nearly edge independence number of a graph

Abstract

Let $G=(V(G),E(G))$ be a graph. The maximum cardinality of a set $M_k\subseteq 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 ${\alpha }_k^{\prime }(G)$. In this paper we study ${\alpha }_1^{\prime }(G)$. In particular, we prove a tight lower (resp. upper) bound on ${\alpha }_1(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.

arXiv comment9 pages