On total domination vertex critical graphs of high connectivity

Michael A. Henning, Nader Jafari Rad

Research output: Contribution to journalArticlepeer-review

15 Citations (Scopus)


A graph is called γ-critical if the removal of any vertex from the graph decreases the domination number, while a graph with no isolated vertex is γt-critical if the removal of any vertex that is not adjacent to a vertex of degree 1 decreases the total domination number. A γt-critical graph that has total domination number k, is called k-γt-critical. In this paper, we introduce a class of k-γt-critical graphs of high connectivity for each integer k ≥ 3. In particular, we provide a partial answer to the question "Which graphs are γ-critical and γt-critical or one but not the other?" posed in a recent work [W. Goddard, T.W. Haynes, M.A. Henning, L.C. van der Merwe, The diameter of total domination vertex critical graphs, Discrete Math. 286 (2004) 255-261].

Original languageEnglish
Pages (from-to)1969-1973
Number of pages5
JournalDiscrete Applied Mathematics
Issue number8
Publication statusPublished - 28 Apr 2009
Externally publishedYes


  • Connectivity
  • Diameter
  • Total domination
  • Vertex critical

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'On total domination vertex critical graphs of high connectivity'. Together they form a unique fingerprint.

Cite this