On the upper total domination number of Cartesian products of graphs

Paul Dorbec; Michael A. Henning; Douglas F. Rall

doi:10.1007/s10878-007-9099-8

On the upper total domination number of Cartesian products of graphs

Paul Dorbec, Michael A. Henning, Douglas F. Rall

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

11 Citations (Scopus)

Abstract

In this paper we continue the investigation of total domination in Cartesian products of graphs first studied in (Henning, M.A., Rall, D.F. in Graphs Comb. 21:63-69, 2005). A set S of vertices in a graph G is a total dominating set of G if every vertex in G is adjacent to some vertex in S. The maximum cardinality of a minimal total dominating set of G is the upper total domination number of G, denoted by F₁(G). We prove that the product of the upper total domination numbers of any graphs G and H without isolated vertices is at most twice the upper total domination number of their Cartesian product; that is, F₁(G)F₁(H)≤2F_t(G□H).

Original language	English
Pages (from-to)	68-80
Number of pages	13
Journal	Journal of Combinatorial Optimization
Volume	16
Issue number	1
DOIs	https://doi.org/10.1007/s10878-007-9099-8
Publication status	Published - Jul 2008
Externally published	Yes

Keywords

Graph products
Upper domination number
Upper total domination number

ASJC Scopus subject areas

Computer Science Applications
Discrete Mathematics and Combinatorics
Control and Optimization
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.1007/s10878-007-9099-8

Cite this

@article{f4b0841aa3e0481faf38aa37f60a5b8b,

title = "On the upper total domination number of Cartesian products of graphs",

abstract = "In this paper we continue the investigation of total domination in Cartesian products of graphs first studied in (Henning, M.A., Rall, D.F. in Graphs Comb. 21:63-69, 2005). A set S of vertices in a graph G is a total dominating set of G if every vertex in G is adjacent to some vertex in S. The maximum cardinality of a minimal total dominating set of G is the upper total domination number of G, denoted by F1(G). We prove that the product of the upper total domination numbers of any graphs G and H without isolated vertices is at most twice the upper total domination number of their Cartesian product; that is, F1(G)F1(H)≤2Ft(G□H).",

keywords = "Graph products, Upper domination number, Upper total domination number",

author = "Paul Dorbec and Henning, {Michael A.} and Rall, {Douglas F.}",

year = "2008",

month = jul,

doi = "10.1007/s10878-007-9099-8",

language = "English",

volume = "16",

pages = "68--80",

journal = "Journal of Combinatorial Optimization",

issn = "1382-6905",

publisher = "Springer Netherlands",

number = "1",

}

TY - JOUR

T1 - On the upper total domination number of Cartesian products of graphs

AU - Dorbec, Paul

AU - Henning, Michael A.

AU - Rall, Douglas F.

PY - 2008/7

Y1 - 2008/7

N2 - In this paper we continue the investigation of total domination in Cartesian products of graphs first studied in (Henning, M.A., Rall, D.F. in Graphs Comb. 21:63-69, 2005). A set S of vertices in a graph G is a total dominating set of G if every vertex in G is adjacent to some vertex in S. The maximum cardinality of a minimal total dominating set of G is the upper total domination number of G, denoted by F1(G). We prove that the product of the upper total domination numbers of any graphs G and H without isolated vertices is at most twice the upper total domination number of their Cartesian product; that is, F1(G)F1(H)≤2Ft(G□H).

AB - In this paper we continue the investigation of total domination in Cartesian products of graphs first studied in (Henning, M.A., Rall, D.F. in Graphs Comb. 21:63-69, 2005). A set S of vertices in a graph G is a total dominating set of G if every vertex in G is adjacent to some vertex in S. The maximum cardinality of a minimal total dominating set of G is the upper total domination number of G, denoted by F1(G). We prove that the product of the upper total domination numbers of any graphs G and H without isolated vertices is at most twice the upper total domination number of their Cartesian product; that is, F1(G)F1(H)≤2Ft(G□H).

KW - Graph products

KW - Upper domination number

KW - Upper total domination number

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

U2 - 10.1007/s10878-007-9099-8

DO - 10.1007/s10878-007-9099-8

M3 - Article

AN - SCOPUS:44249119884

SN - 1382-6905

VL - 16

SP - 68

EP - 80

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

IS - 1

ER -

On the upper total domination number of Cartesian products of graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this