(Total) domination in prisms

MaRDI QIDQ510330zbMATH OpenFDO

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

Publication date 17 February 2017

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1606.08143, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p19

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

Cartesian product of graphscovering codesdominationhypercubehypergraph transversaltotal domination

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph operations (line graphs, products, etc.) (05C76)

Abstract: With the aid of hypergraph transversals it is proved that $gamm{a}_t(Q_{n+1})=2gamma(Q_n)$, where $gamm{a}_t(G)$ and $gamma(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 $gamm{a}_t(Gsquare{K}_2)=2gamma(G)$. Further, we show that the bipartite condition is essential by constructing, for any $kge1$, a (non-bipartite) graph $G$ such that $gamm{a}_t(Gsquare{K}_2)=2gamma(G)-k$. Along the way several domination-type identities for hypercubes are also obtained.

Review text

Summary: Using hypergraph transversals it is proved that \(\gamma_t(Q_{n+1}) = 2\gamma(Q_n)\), where \(\gamma_t(G)\) and \(\gamma(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 \(\gamma_t(G \square K_2) = 2\gamma(G)\). Further, we show that the bipartiteness condition is essential by constructing, for any \(k \geq 1\), a (non-bipartite) graph \(G\) such that \(\gamma_t(G\square K_2) = 2\gamma(G) - k\). Along the way several domination-type identities for hypercubes are also obtained.

Recommendations

• A note on domination and total domination in prisms
• On total domination in the Cartesian product of graphs
• On independent and \((d, n)\)-domination numbers of hypercubes
• scientific article; zbMATH DE number 2234856
• Total domination of Cartesian products of graphs

Cites work

• A note on total and paired domination of Cartesian product graphs
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• An updated table of binary/ternary mixed covering codes
• Bounds for covering codes over large alphabets
• Dominating sets in n‐cubes
• Handbook of product graphs
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 3417479 (Why is no real title available?)
• Hypergraphs with large transversal number and with edge sizes at least 3
• Improved sphere bounds on the covering radius of codes
• Independent domination in hypercubes
• Independent perfect domination sets in Cayley graphs
• On the concentration of the domination number of the random graph
• On the size of optimal binary codes of length 9 and covering radius 1
• On the total domination number of Cartesian products of graphs
• Optimal binary covering codes of length 2j
• Paired domination in graphs: a survey and recent results
• Paired-domination in graphs
• Partial product of graphs and Vizing's conjecture
• Perfect domination sets in Cayley graphs
• Total domination in graphs
• Total domination in the Cartesian product of a graph and K₂ or C_n
• Vizing's conjecture for graphs with domination number 3 -- a new proof
• Vizing's conjecture: a survey and recent results

Cited in

(15)

• A note on domination and total domination in prisms
• Bounding the k-rainbow total domination number
• Total domination in generalized prisms and a new domination invariant
• Domination in rose window graphs
• scientific article; zbMATH DE number 90561 (Why is no real title available?)
• scientific article; zbMATH DE number 1506499 (Why is no real title available?)
• On domination-type invariants of Fibonacci cubes and hypercubes
• scientific article; zbMATH DE number 6813626 (Why is no real title available?)
• Packings in bipartite prisms and hypercubes
• Partitioning the vertices of a graph or its complement into a total dominating set and an independent dominating set
• Optimal local identifying and local locating-dominating codes
• On k-rainbow total domination and a related conjecture
• Fractional eternal domination: securely distributing resources across a network
• Total and paired domination stability in prisms
• Domination and total domination in complementary prisms

This page was built for publication: (Total) domination in prisms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q510330)