On the existence problem of the total domination vertex critical graphs

DOI10.1016/J.DAM.2010.09.004MaRDI QIDQ617898zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 5575482 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 2188442 (Why is no real title available?)
• scientific article; zbMATH DE number 2197907 (Why is no real title available?)
• A note on the total domination vertex critical graphs
• A remark on total domination critical graphs
• A total domination vertex critical graph of diameter two
• On 4-\gamma_t-critical graphs of order 4+\Delta(G)
• On an open problem concerning total domination critical graphs
• On the total domination critical graphs
• On total domination vertex critical graphs of high connectivity
• The diameter of paired-domination vertex critical graphs
• The diameter of total domination vertex critical graphs

Cited in

(10)

• Existence of graphs with a given domination parameter
• On 3-_t-vertex critical graphs of diameter three
• On the total domination critical graphs
• 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)