The diameter of total domination vertex critical graphs

Wayne Goddard; Teresa W. Haynes; Michael A. Henning; Lucas C. Van der Merwe

doi:10.1016/j.disc.2004.05.010

The diameter of total domination vertex critical graphs

Wayne Goddard, Teresa W. Haynes, Michael A. Henning, Lucas C. Van der Merwe

Research output: Contribution to journal › Article › peer-review

43 Citations (Scopus)

Abstract

A graph G with no isolated vertex is total domination vertex critical if for any vertex v of G that is not adjacent to a vertex of degree one, the total domination number of G - v is less than the total domination number of G. These graphs we call γ_t-critical. If such a graph G has total domination number k, we call it k-γ_t-critical. We characterize the connected graphs with minimum degree one that are γ _t-critical and we obtain sharp bounds on their maximum diameter. We calculate the maximum diameter of a k-γ_t-critical graph for k≤8 and provide an example which shows that the maximum diameter is in general at least 5k/3 - O(1).

Original language	English
Pages (from-to)	255-261
Number of pages	7
Journal	Discrete Mathematics
Volume	286
Issue number	3
DOIs	https://doi.org/10.1016/j.disc.2004.05.010
Publication status	Published - 28 Sept 2004
Externally published	Yes

Keywords

Bounds; Diameter
Total domination
Vertex critical

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.disc.2004.05.010

Cite this

@article{5b0f6d0effb74555a811658ea77e7335,

title = "The diameter of total domination vertex critical graphs",

abstract = "A graph G with no isolated vertex is total domination vertex critical if for any vertex v of G that is not adjacent to a vertex of degree one, the total domination number of G - v is less than the total domination number of G. These graphs we call γt-critical. If such a graph G has total domination number k, we call it k-γt-critical. We characterize the connected graphs with minimum degree one that are γ t-critical and we obtain sharp bounds on their maximum diameter. We calculate the maximum diameter of a k-γt-critical graph for k≤8 and provide an example which shows that the maximum diameter is in general at least 5k/3 - O(1).",

keywords = "Bounds; Diameter, Total domination, Vertex critical",

author = "Wayne Goddard and Haynes, {Teresa W.} and Henning, {Michael A.} and {Van der Merwe}, {Lucas C.}",

year = "2004",

month = sep,

day = "28",

doi = "10.1016/j.disc.2004.05.010",

language = "English",

volume = "286",

pages = "255--261",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "3",

}

TY - JOUR

T1 - The diameter of total domination vertex critical graphs

AU - Goddard, Wayne

AU - Haynes, Teresa W.

AU - Henning, Michael A.

AU - Van der Merwe, Lucas C.

PY - 2004/9/28

Y1 - 2004/9/28

N2 - A graph G with no isolated vertex is total domination vertex critical if for any vertex v of G that is not adjacent to a vertex of degree one, the total domination number of G - v is less than the total domination number of G. These graphs we call γt-critical. If such a graph G has total domination number k, we call it k-γt-critical. We characterize the connected graphs with minimum degree one that are γ t-critical and we obtain sharp bounds on their maximum diameter. We calculate the maximum diameter of a k-γt-critical graph for k≤8 and provide an example which shows that the maximum diameter is in general at least 5k/3 - O(1).

AB - A graph G with no isolated vertex is total domination vertex critical if for any vertex v of G that is not adjacent to a vertex of degree one, the total domination number of G - v is less than the total domination number of G. These graphs we call γt-critical. If such a graph G has total domination number k, we call it k-γt-critical. We characterize the connected graphs with minimum degree one that are γ t-critical and we obtain sharp bounds on their maximum diameter. We calculate the maximum diameter of a k-γt-critical graph for k≤8 and provide an example which shows that the maximum diameter is in general at least 5k/3 - O(1).

KW - Bounds; Diameter

KW - Total domination

KW - Vertex critical

UR - http://www.scopus.com/inward/record.url?scp=4444266176&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2004.05.010

DO - 10.1016/j.disc.2004.05.010

M3 - Article

AN - SCOPUS:4444266176

SN - 0012-365X

VL - 286

SP - 255

EP - 261

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 3

ER -

The diameter of total domination vertex critical graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this