Integer domination of Cartesian product graphs

DOI10.1016/J.DISC.2015.01.032MaRDI QIDQ2339441zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 1 April 2015

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1209.1842

zbMATH Keywords

domination theoryproduct graphsVizing's conjecture

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph operations (line graphs, products, etc.) (05C76)

Abstract: Given a graph $G$, a dominating set $D$ is a set of vertices such that any vertex in $G$ has at least one neighbor (or possibly itself) in $D$. A $k$-dominating multiset $D_k$ is a multiset of vertices such that any vertex in $G$ has at least $k$ vertices from its closed neighborhood in $D_k$ when counted with multiplicity. In this paper, we utilize the approach developed by Clark and Suen (2000) and properties of binary matrices to prove a "Vizing-like" inequality on minimum $k$-dominating multisets of graphs $G,H$ and the Cartesian product graph $GBoxH$. Specifically, denoting the size of a minimum $k$-dominating multiset as $gamm{a}_k(G)$, we demonstrate that $gamm{a}_k(G)gamm{a}_k(H)leq2kgamm{a}_k(GBoxH)$.

Recommendations

• Graph products and integer domination
• On integer domination in graphs and Vizing-like problems
• A note on total and paired domination of Cartesian product graphs
• On Vizing's conjecture
• On dominating the Cartesian product of a graph and K₂

Cites work

• A note on total and paired domination of Cartesian product graphs
• An inequality related to Vizing's conjecture
• scientific article; zbMATH DE number 5543109 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• scientific article; zbMATH DE number 867701 (Why is no real title available?)
• scientific article; zbMATH DE number 3284071 (Why is no real title available?)
• On integer domination in graphs and Vizing-like problems
• On the \(\{k\}\)-domination number of Cartesian products of graphs
• Paired domination of Cartesian products of graphs
• Vizing's conjecture: a survey and recent results

Cited in

(6)

• Domination parameters with number 2: interrelations and algorithmic consequences
• Graph products and integer domination
• 3-tuple total domination number of Rook's graphs
• Integer-programming bounds on pebbling numbers of Cartesian-product graphs
• Cartesian product graphs and \(k\)-tuple total domination
• On integer domination in graphs and Vizing-like problems

This page was built for publication: Integer domination of Cartesian product graphs

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