EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

THE 1-NEARLY VERTEX INDEPENDENCE NUMBER OF A GRAPH

Zekhaya B. Shozi

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →