Nordhaus-Gaddum bounds for upper total domination
A set \(S\) of vertices in an isolate-free graph \(G\) is a total dominating set if every vertex in \(G\) is adjacent to a vertex in \(S\). A total dominating set of \(G\) is minimal if it contains no total dominating set of \(G\) as a proper subset. The upper total domination number \(\Gamma_t(G)\)...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
AGH Univeristy of Science and Technology Press
2022-06-01
|
| Series: | Opuscula Mathematica |
| Subjects: | |
| Online Access: | https://www.opuscula.agh.edu.pl/vol42/4/art/opuscula_math_4226.pdf |
| _version_ | 1818242275796320256 |
|---|---|
| author | Teresa W. Haynes Michael A. Henning |
| author_facet | Teresa W. Haynes Michael A. Henning |
| author_sort | Teresa W. Haynes |
| collection | DOAJ |
| description | A set \(S\) of vertices in an isolate-free graph \(G\) is a total dominating set if every vertex in \(G\) is adjacent to a vertex in \(S\). A total dominating set of \(G\) is minimal if it contains no total dominating set of \(G\) as a proper subset. The upper total domination number \(\Gamma_t(G)\) of \(G\) is the maximum cardinality of a minimal total dominating set in \(G\). We establish Nordhaus-Gaddum bounds involving the upper total domination numbers of a graph \(G\) and its complement \(\overline{G}\). We prove that if \(G\) is a graph of order \(n\) such that both \(G\) and \(\overline{G}\) are isolate-free, then \(\Gamma_t(G) + \Gamma_t(\overline{G}) \leq n + 2\) and \(\Gamma_t(G)\Gamma_t(\overline{G}) \leq \frac{1}{4}(n+2)^2\), and these bounds are tight. |
| first_indexed | 2024-12-12T13:42:39Z |
| format | Article |
| id | doaj.art-ab46518842264960ab34dcff65eab170 |
| institution | Directory Open Access Journal |
| issn | 1232-9274 |
| language | English |
| last_indexed | 2024-12-12T13:42:39Z |
| publishDate | 2022-06-01 |
| publisher | AGH Univeristy of Science and Technology Press |
| record_format | Article |
| series | Opuscula Mathematica |
| spelling | doaj.art-ab46518842264960ab34dcff65eab1702022-12-22T00:22:45ZengAGH Univeristy of Science and Technology PressOpuscula Mathematica1232-92742022-06-01424573582https://doi.org/10.7494/OpMath.2022.42.4.5734226Nordhaus-Gaddum bounds for upper total dominationTeresa W. Haynes0Michael A. Henning1East Tennessee State University, Department of Mathematics and Statistics, Johnson City, TN 37614-0002 USAUniversity of Johannesburg, Department of Mathematics and Applied Mathematics, Auckland Park, 2006 South AfricaA set \(S\) of vertices in an isolate-free graph \(G\) is a total dominating set if every vertex in \(G\) is adjacent to a vertex in \(S\). A total dominating set of \(G\) is minimal if it contains no total dominating set of \(G\) as a proper subset. The upper total domination number \(\Gamma_t(G)\) of \(G\) is the maximum cardinality of a minimal total dominating set in \(G\). We establish Nordhaus-Gaddum bounds involving the upper total domination numbers of a graph \(G\) and its complement \(\overline{G}\). We prove that if \(G\) is a graph of order \(n\) such that both \(G\) and \(\overline{G}\) are isolate-free, then \(\Gamma_t(G) + \Gamma_t(\overline{G}) \leq n + 2\) and \(\Gamma_t(G)\Gamma_t(\overline{G}) \leq \frac{1}{4}(n+2)^2\), and these bounds are tight.https://www.opuscula.agh.edu.pl/vol42/4/art/opuscula_math_4226.pdfupper total dominationnordhaus-gaddum bounds |
| spellingShingle | Teresa W. Haynes Michael A. Henning Nordhaus-Gaddum bounds for upper total domination Opuscula Mathematica upper total domination nordhaus-gaddum bounds |
| title | Nordhaus-Gaddum bounds for upper total domination |
| title_full | Nordhaus-Gaddum bounds for upper total domination |
| title_fullStr | Nordhaus-Gaddum bounds for upper total domination |
| title_full_unstemmed | Nordhaus-Gaddum bounds for upper total domination |
| title_short | Nordhaus-Gaddum bounds for upper total domination |
| title_sort | nordhaus gaddum bounds for upper total domination |
| topic | upper total domination nordhaus-gaddum bounds |
| url | https://www.opuscula.agh.edu.pl/vol42/4/art/opuscula_math_4226.pdf |
| work_keys_str_mv | AT teresawhaynes nordhausgaddumboundsforuppertotaldomination AT michaelahenning nordhausgaddumboundsforuppertotaldomination |