On the existence problem of the total domination vertex critical graphs

DOI10.1016/J.DAM.2010.09.004zbMATH Open1208.05103arXiv1001.0797OpenAlexW2017903984MaRDI QIDQ617898FDOQ617898

Authors: Moo Young Sohn, Young Soo Kwon, Jaeun Lee, Dongseok Kim 

Publication date: 14 January 2011

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: The existence problem of the total domination vertex critical graphs has been studied in a series of articles. The aim of the present article is twofold. First, we settle the existence problem with respect to the parities of the total domination number m and the maximum degree Delta : for even m except m=4, there is no m-gamma_t-critical graph regardless of the parity of Delta; for m=4 or odd m ge 3 and for even Delta, an m-gamma_t-critical graph exists if and only if Delta ge 2 lfloor frac{m-1}{2} floor; for m=4 or odd m ge 3 and for odd Delta, if Delta ge 2lfloor frac{m-1}{2} floor +7, then m-gamma_t-critical graphs exist, if Delta < 2lfloor frac{m-1}{2} floor, then m-gamma_t-critical graphs do not exist. The only remaining open cases are Delta = 2lfloor frac{m-1}{2} floor +k, k=1, 3, 5. Second, we study these remaining open cases when m=4 or odd m ge 9. As the previously known result for m = 3, we also show that for Delta(G)= 3, 5, 7, there is no 4-gamma_t-critical graph of order Delta(G)+4. On the contrary, it is shown that for odd m ge 9 there exists an m-gamma_t-critical graph for all Delta ge m-1.

Full work available at URL: https://arxiv.org/abs/1001.0797

Recommendations

• A note on the total domination vertex critical graphs
• On the total domination critical graphs
• On questions on (total) domination vertex critical graphs.
• On an open problem concerning total domination critical graphs
• A constructive characterization of total domination vertex critical graphs
• On maximum total domination vertex critical graphs
• Critical graphs with respect to total domination and connected domination
• On the structure of graphs vertex critical with~respect to connected domination
• A remark on total domination critical graphs
• On the diameter of total domination vertex-critical graphs

zbMATH Keywords

maximal degreetotal domination numberstotal domination vertex critical graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Title not available (Why is that?)
• On total domination vertex critical graphs of high connectivity
• On an open problem concerning total domination critical graphs
• Title not available (Why is that?)
• The diameter of total domination vertex critical graphs
• A total domination vertex critical graph of diameter two
• The diameter of paired-domination vertex critical graphs
• Title not available (Why is that?)
• A note on the total domination vertex critical graphs
• A remark on total domination critical graphs
• Title not available (Why is that?)
• On the total domination critical graphs
• On 4-\gamma_t-critical graphs of order 4+\Delta(G)

Cited In (10)

• Existence of graphs with a given domination parameter
• On the total domination critical graphs
• On 3-\(\gamma_t\)-vertex critical graphs of diameter three
• On the \(3\)-\(\gamma_t\)-critical graphs of order \(\Delta(G)+3\)
• A note on the total domination vertex critical graphs
• On total domination vertex critical graphs of high connectivity
• On an open problem concerning total domination critical graphs
• On \(4\)-\(\gamma_t\)-critical graphs of diameter two
• Total \(k\)-distance domination critical graphs
• The existence problem of \(k\mathrm{-}\gamma_t\)-critical graphs

This page was built for publication: On the existence problem of the total domination vertex critical graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q617898)