(Total) Domination in Prisms

2016/06/27 by Azarija, Jernej, Henning, Michael A., Klavžar, Sandi · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1606.08143

Abstract

With the aid of 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 γ_t(G \square K₂) = 2γ(G). Further, we show that the bipartite condition is essential by constructing, for any k ≥ 1, a (non-bipartite) graph G such that γ_t (G \square K₂ ) = 2γ(G) - k. Along the way several domination-type identities for hypercubes are also obtained.

Cited by

• On the forts and related parameters of the hypercube graph

Related

• The domination number of the graph defined by two levels of the n-cube, II
• New Upper Bounds on the Minimal Domination Numbers of High-Dimensional Hypercubes
• Partial Domination in Prisms of Graphs
• Some results on domination number of the graph defined by two levels of the n-cube
• An upper bound for the k-power domination number in r-uniform hypergraphs