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 $α'_k(G)$. In this paper we study $α_1'(G)$. In particular, we prove a tight lower (resp. upper) bound on $α_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.
Fields of Study & Subjects
Graph Labeling and Dimension Problems
Graph theory and applications
Advanced Graph Theory Research
Publication details
- Journal / source
- Quaestiones Mathematicae
- Publisher
- National Inquiry Services Center (NISC)
- Volume
- 49
- Issue
- 10
- Pages
- 1437–1443
- Publication date
- 27 May 2026
- Language
- EN