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 ⊆ 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 . In this paper we study . In particular, we prove a tight lower bound on if G is a general (resp. connected) 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.