THE 1-NEARLY VERTEX INDEPENDENCE NUMBER OF A GRAPH
Abstract
Let $G$ be a graph with vertex set $V(G)$ and edge set $E(G)$. A set $I_0(G) \subseteq V(G)$ is a vertex independent set if no two vertices in $I_0(G)$ are adjacent in $G$. We study $\alpha_1(G)$, which is the maximum cardinality of a set $I_1(G) \subseteq V(G)$ that contains exactly one pair of adjacent vertices of $G$. We call $I_1(G)$ a 1-nearly vertex independent set of $G$ and $\alpha_1(G)$ a 1-nearly vertex independence number of $G$. We provide some cases of explicit formulas for $\alpha_1$. Furthermore, we prove a tight lower (resp. upper) bound on $\alpha_1$ for graphs of order $n$. The extremal graphs that achieve equality on each bound are fully characterized.
Fields of Study & Subjects
Graph Labeling and Dimension Problems
Graph theory and applications
Advanced Graph Theory Research
Publication details
- Journal / source
- Advances and Applications in Discrete Mathematics
- Volume
- 43
- Issue
- 5
- Pages
- 627–639
- Publication date
- 26 May 2026
- Language
- EN