THE 1-NEARLY VERTEX INDEPENDENCE NUMBER OF A GRAPH
Advances and Applications in Discrete Mathematics · 26.05.2026 · 43 (5) · 627-639
DOI: 10.17654/0974165826040 ↗Kurz gefasst
Fachartikel in der Zeitschrift Advances and Applications in Discrete Mathematics, online erschienen am 26.05.2026. Verfasst von Zekhaya B. Shozi. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
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.
Zitieren
APA
Shozi, Z. B. (2026). THE 1-NEARLY VERTEX INDEPENDENCE NUMBER OF A GRAPH. Advances and Applications in Discrete Mathematics, 43(5), 627-639. https://doi.org/10.17654/0974165826040
Vancouver
Shozi ZB. THE 1-NEARLY VERTEX INDEPENDENCE NUMBER OF A GRAPH. Advances and Applications in Discrete Mathematics. 2026;43(5):627-639. doi:10.17654/0974165826040
BibTeX
@article{Shozi2026,
author = {Shozi, Zekhaya B.},
title = {THE 1-NEARLY VERTEX INDEPENDENCE NUMBER OF A GRAPH},
journal = {Advances and Applications in Discrete Mathematics},
year = {2026},
volume = {43},
number = {5},
pages = {627--639},
doi = {10.17654/0974165826040}
}
EUVIMED