Total Domination Versus Domination in Cubic Graphs

Joanna Cyman; Magda Dettlaff; Michael A. Henning; Magdalena Lemańska; Joanna Raczek

doi:10.1007/s00373-017-1865-5

Total Domination Versus Domination in Cubic Graphs

Joanna Cyman, Magda Dettlaff, Michael A. Henning, Magdalena Lemańska, Joanna Raczek

Mathematics and Applied Mathematics

Gdańsk University of Technology

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

9 Citations (Scopus)

Abstract

A dominating set in a graph G is a set S of vertices of G such that every vertex not in S has a neighbor in S. Further, if every vertex of G has a neighbor in S, then S is a total dominating set of G. The domination number, γ(G) , and total domination number, γ_t(G) , are the minimum cardinalities of a dominating set and total dominating set, respectively, in G. The upper domination number, Γ (G) , and the upper total domination number, Γ _t(G) , are the maximum cardinalities of a minimal dominating set and total dominating set, respectively, in G. It is known that γ_t(G) / γ(G) ≤ 2 and Γ _t(G) / Γ (G) ≤ 2 for all graphs G with no isolated vertex. In this paper we characterize the connected cubic graphs G satisfying γ_t(G) / γ(G) = 2 , and we characterize the connected cubic graphs G satisfying Γ _t(G) / Γ (G) = 2.

Original language	English
Pages (from-to)	261-276
Number of pages	16
Journal	Graphs and Combinatorics
Volume	34
Issue number	1
DOIs	https://doi.org/10.1007/s00373-017-1865-5
Publication status	Published - 1 Jan 2018

Keywords

Cubic graph
Domination number
Total domination number
Upper domination number
Upper total domination number

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1007/s00373-017-1865-5

Cite this

@article{bc102c972c104fb58a4de472b0613af8,

title = "Total Domination Versus Domination in Cubic Graphs",

abstract = "A dominating set in a graph G is a set S of vertices of G such that every vertex not in S has a neighbor in S. Further, if every vertex of G has a neighbor in S, then S is a total dominating set of G. The domination number, γ(G) , and total domination number, γt(G) , are the minimum cardinalities of a dominating set and total dominating set, respectively, in G. The upper domination number, Γ (G) , and the upper total domination number, Γ t(G) , are the maximum cardinalities of a minimal dominating set and total dominating set, respectively, in G. It is known that γt(G) / γ(G) ≤ 2 and Γ t(G) / Γ (G) ≤ 2 for all graphs G with no isolated vertex. In this paper we characterize the connected cubic graphs G satisfying γt(G) / γ(G) = 2 , and we characterize the connected cubic graphs G satisfying Γ t(G) / Γ (G) = 2.",

keywords = "Cubic graph, Domination number, Total domination number, Upper domination number, Upper total domination number",

author = "Joanna Cyman and Magda Dettlaff and Henning, {Michael A.} and Magdalena Lema{\'n}ska and Joanna Raczek",

note = "Publisher Copyright: {\textcopyright} 2017, The Author(s).",

year = "2018",

month = jan,

day = "1",

doi = "10.1007/s00373-017-1865-5",

language = "English",

volume = "34",

pages = "261--276",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "1",

}

TY - JOUR

T1 - Total Domination Versus Domination in Cubic Graphs

AU - Cyman, Joanna

AU - Dettlaff, Magda

AU - Henning, Michael A.

AU - Lemańska, Magdalena

AU - Raczek, Joanna

PY - 2018/1/1

Y1 - 2018/1/1

N2 - A dominating set in a graph G is a set S of vertices of G such that every vertex not in S has a neighbor in S. Further, if every vertex of G has a neighbor in S, then S is a total dominating set of G. The domination number, γ(G) , and total domination number, γt(G) , are the minimum cardinalities of a dominating set and total dominating set, respectively, in G. The upper domination number, Γ (G) , and the upper total domination number, Γ t(G) , are the maximum cardinalities of a minimal dominating set and total dominating set, respectively, in G. It is known that γt(G) / γ(G) ≤ 2 and Γ t(G) / Γ (G) ≤ 2 for all graphs G with no isolated vertex. In this paper we characterize the connected cubic graphs G satisfying γt(G) / γ(G) = 2 , and we characterize the connected cubic graphs G satisfying Γ t(G) / Γ (G) = 2.

AB - A dominating set in a graph G is a set S of vertices of G such that every vertex not in S has a neighbor in S. Further, if every vertex of G has a neighbor in S, then S is a total dominating set of G. The domination number, γ(G) , and total domination number, γt(G) , are the minimum cardinalities of a dominating set and total dominating set, respectively, in G. The upper domination number, Γ (G) , and the upper total domination number, Γ t(G) , are the maximum cardinalities of a minimal dominating set and total dominating set, respectively, in G. It is known that γt(G) / γ(G) ≤ 2 and Γ t(G) / Γ (G) ≤ 2 for all graphs G with no isolated vertex. In this paper we characterize the connected cubic graphs G satisfying γt(G) / γ(G) = 2 , and we characterize the connected cubic graphs G satisfying Γ t(G) / Γ (G) = 2.

KW - Cubic graph

KW - Domination number

KW - Total domination number

KW - Upper domination number

KW - Upper total domination number

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

U2 - 10.1007/s00373-017-1865-5

DO - 10.1007/s00373-017-1865-5

M3 - Article

AN - SCOPUS:85038357507

SN - 0911-0119

VL - 34

SP - 261

EP - 276

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 1

ER -

Total Domination Versus Domination in Cubic Graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this