Total domination subdivision numbers of trees

Teresa W. Haynes; Michael A. Henning; Lora Hopkins

doi:10.1016/j.disc.2004.06.004

Total domination subdivision numbers of trees

Teresa W. Haynes, Michael A. Henning, Lora Hopkins

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

23 Citations (Scopus)

Abstract

A set S of vertices in a graph G is a total dominating set of G if every vertex is adjacent to a vertex in S. The total domination number yγ _t (G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number sd_γt (G) of a graph G is the minimum number of edges that must be subdivided (where each edge in G can be subdivided at most once) in order to increase the total domination number. Haynes et al. (J. Combin. Math. Combin. Comput. 44 (2003) 115) showed that for any tree T of order at least 3, 1 ≤sd_γt (T)≤3. In this paper, we give a constructive characterization of trees whose total domination subdivision number is 3.

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

Keywords

Total domination number
Total domination subdivision number
Trees

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.disc.2004.06.004

Cite this

@article{f8c378781da84e5aa93886575c406774,

title = "Total domination subdivision numbers of trees",

abstract = "A set S of vertices in a graph G is a total dominating set of G if every vertex is adjacent to a vertex in S. The total domination number yγ t (G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number sdγt (G) of a graph G is the minimum number of edges that must be subdivided (where each edge in G can be subdivided at most once) in order to increase the total domination number. Haynes et al. (J. Combin. Math. Combin. Comput. 44 (2003) 115) showed that for any tree T of order at least 3, 1 ≤sdγt (T)≤3. In this paper, we give a constructive characterization of trees whose total domination subdivision number is 3.",

keywords = "Total domination number, Total domination subdivision number, Trees",

author = "Haynes, {Teresa W.} and Henning, {Michael A.} and Lora Hopkins",

year = "2004",

month = sep,

day = "28",

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

language = "English",

volume = "286",

pages = "195--202",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

T1 - Total domination subdivision numbers of trees

AU - Haynes, Teresa W.

AU - Henning, Michael A.

AU - Hopkins, Lora

PY - 2004/9/28

Y1 - 2004/9/28

N2 - A set S of vertices in a graph G is a total dominating set of G if every vertex is adjacent to a vertex in S. The total domination number yγ t (G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number sdγt (G) of a graph G is the minimum number of edges that must be subdivided (where each edge in G can be subdivided at most once) in order to increase the total domination number. Haynes et al. (J. Combin. Math. Combin. Comput. 44 (2003) 115) showed that for any tree T of order at least 3, 1 ≤sdγt (T)≤3. In this paper, we give a constructive characterization of trees whose total domination subdivision number is 3.

AB - A set S of vertices in a graph G is a total dominating set of G if every vertex is adjacent to a vertex in S. The total domination number yγ t (G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number sdγt (G) of a graph G is the minimum number of edges that must be subdivided (where each edge in G can be subdivided at most once) in order to increase the total domination number. Haynes et al. (J. Combin. Math. Combin. Comput. 44 (2003) 115) showed that for any tree T of order at least 3, 1 ≤sdγt (T)≤3. In this paper, we give a constructive characterization of trees whose total domination subdivision number is 3.

KW - Total domination number

KW - Total domination subdivision number

KW - Trees

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

U2 - 10.1016/j.disc.2004.06.004

DO - 10.1016/j.disc.2004.06.004

M3 - Article

AN - SCOPUS:4444337447

SN - 0012-365X

VL - 286

SP - 195

EP - 202

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 3

ER -

Total domination subdivision numbers of trees

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this