EUVIMEDEUVIMED entdecken
Crossref

Augmenting graphs to partition their vertices into a total dominating set and an independent dominating set

Teresa W. Haynes, Michael A. Henning

Opuscula Mathematica · 2025 · 179-198

DOI: 10.7494/opmath.2025.45.2.179 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Opuscula Mathematica, 2025. Verfasst von Teresa W. Haynes und 1 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 25 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

A graph \(G\) whose vertex set can be partitioned into a total dominating set and an independent dominating set is called a TI-graph. There exist infinite families of graphs that are not TI-graphs. We define the TI-augmentation number \(\operatorname{ti}(G)\) of a graph \(G\) to be the minimum number of edges that must be added to \(G\) to ensure that the resulting graph is a TI-graph. We show that every tree \(T\) of order \(n \geq 5\) satisfies \(\operatorname{ti}(T) \leq \frac{1}{5}n\). We prove that if \(G\) is a bipartite graph of order \(n\) with minimum degree \(\delta(G) \geq 3\), then \(\operatorname{ti}(G) \leq \frac{1}{4}n\), and if \(G\) is a cubic graph of order \(n\), then \(\operatorname{ti}(G) \leq \frac{1}{3}n\). We conjecture that \(\operatorname{ti}(G) \leq \frac{1}{6}n\) for all graphs \(G\) of order \(n\) with \(\delta(G) \geq 3\), and show that there exist connected graphs \(G\) of sufficiently large order \(n\) with \(\delta(G) \geq 3\) such that \(\operatorname{ti}(T) \geq (\frac{1}{6} - \varepsilon) n\) for any given \(\varepsilon \gt 0\).

Zitieren

APA

Haynes, T. W., & Henning, M. A. (2025). Augmenting graphs to partition their vertices into a total dominating set and an independent dominating set. Opuscula Mathematica, 179-198. https://doi.org/10.7494/opmath.2025.45.2.179

Vancouver

Haynes TW, Henning MA. Augmenting graphs to partition their vertices into a total dominating set and an independent dominating set. Opuscula Mathematica. 2025:179-198. doi:10.7494/opmath.2025.45.2.179

BibTeX
@article{Haynes2025,
  author = {Haynes, Teresa W. and Henning, Michael A.},
  title = {Augmenting graphs to partition their vertices into a total dominating set and an independent dominating set},
  journal = {Opuscula Mathematica},
  year = {2025},
  pages = {179--198},
  doi = {10.7494/opmath.2025.45.2.179}
}
Kostenlos starten →