(Total) domination in prisms

Jernej Azarija; Michael A. Henning; Sandi Klavžar

doi:10.37236/6288

(Total) domination in prisms

Jernej Azarija, Michael A. Henning, Sandi Klavžar

Mathematics and Applied Mathematics

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

14 Citations (Scopus)

Abstract

Using hypergraph transversals it is proved that γ_t(Q_n+1) = 2γ(Q_n), where γ_t(G) and γ(G) denote the total domination number and the domination number of G, respectively, and Q_n is the n-dimensional hypercube. More generally, it is shown that if G is a bipartite graph, then (formula presented). Further, we show that the bipartiteness condition is essential by constructing, for any k ≥ 1, a (non-bipartite) graph G such that formula presented). Along the way several domination-type identities for hypercubes are also obtained.

Original language	English
Article number	#P1.19
Journal	Electronic Journal of Combinatorics
Volume	24
Issue number	1
DOIs	https://doi.org/10.37236/6288
Publication status	Published - 3 Feb 2017

Keywords

Cartesian product of graphs
Covering codes
Domination
Hypercube
Hypergraph transversal
Total domination

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.37236/6288

Cite this

@article{c25545de1db34fec8c94c347bd0b38f8,

title = "(Total) domination in prisms",

abstract = "Using hypergraph transversals it is proved that γt(Qn+1) = 2γ(Qn), where γt(G) and γ(G) denote the total domination number and the domination number of G, respectively, and Qn is the n-dimensional hypercube. More generally, it is shown that if G is a bipartite graph, then (formula presented). Further, we show that the bipartiteness condition is essential by constructing, for any k ≥ 1, a (non-bipartite) graph G such that formula presented). Along the way several domination-type identities for hypercubes are also obtained.",

keywords = "Cartesian product of graphs, Covering codes, Domination, Hypercube, Hypergraph transversal, Total domination",

author = "Jernej Azarija and Henning, {Michael A.} and Sandi Klav{\v z}ar",

year = "2017",

month = feb,

day = "3",

doi = "10.37236/6288",

language = "English",

volume = "24",

journal = "Electronic Journal of Combinatorics",

issn = "1077-8926",

publisher = "Electronic Journal of Combinatorics",

number = "1",

}

TY - JOUR

T1 - (Total) domination in prisms

AU - Azarija, Jernej

AU - Henning, Michael A.

AU - Klavžar, Sandi

PY - 2017/2/3

Y1 - 2017/2/3

N2 - Using hypergraph transversals it is proved that γt(Qn+1) = 2γ(Qn), where γt(G) and γ(G) denote the total domination number and the domination number of G, respectively, and Qn is the n-dimensional hypercube. More generally, it is shown that if G is a bipartite graph, then (formula presented). Further, we show that the bipartiteness condition is essential by constructing, for any k ≥ 1, a (non-bipartite) graph G such that formula presented). Along the way several domination-type identities for hypercubes are also obtained.

AB - Using hypergraph transversals it is proved that γt(Qn+1) = 2γ(Qn), where γt(G) and γ(G) denote the total domination number and the domination number of G, respectively, and Qn is the n-dimensional hypercube. More generally, it is shown that if G is a bipartite graph, then (formula presented). Further, we show that the bipartiteness condition is essential by constructing, for any k ≥ 1, a (non-bipartite) graph G such that formula presented). Along the way several domination-type identities for hypercubes are also obtained.

KW - Cartesian product of graphs

KW - Covering codes

KW - Domination

KW - Hypercube

KW - Hypergraph transversal

KW - Total domination

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

U2 - 10.37236/6288

DO - 10.37236/6288

M3 - Article

AN - SCOPUS:85011564561

SN - 1077-8926

VL - 24

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 1

M1 - #P1.19

ER -

(Total) domination in prisms

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this