Simultaneous domination in graphs

DOI10.1007/S00373-013-1353-5zbMATH Open1306.05177arXiv1301.4008OpenAlexW2085152491MaRDI QIDQ489305FDOQ489305

Authors: Yair Caro, Michael A. Henning 

Publication date: 20 January 2015

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: Let $F_1,F_2,\mathrm{...},F_k$ be graphs with the same vertex set $V$. A subset $SsubseteqV$ is a simultaneous dominating set if for every $i$, $1leilek$, every vertex of $F_i$ not in $S$ is adjacent to a vertex in $S$ in $F_i$; that is, the set $S$ is simultaneously a dominating set in each graph $F_i$. The cardinality of a smallest such set is the simultaneous domination number. We present general upper bounds on the simultaneous domination number. We investigate bounds in special cases, including the cases when the factors, $F_i$, are $r$-regular or the disjoint union of copies of $K_r$. Further we study the case when each factor is a cycle.

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

Recommendations

• Simultaneous graph parameters: factor domination and factor total domination
• Factor domination in graphs
• Simultaneously dominating all spanning trees of a graph
• On upper bounds for multiple domination numbers of graphs
• Domination versus independent domination in graphs of small regularity

zbMATH Keywords

factor domination

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• A new bound for the 2/3 conjecture
• New approach to the \(k\)-independence number of a graph
• Factor domination in graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Factor domination and minimum degree
• Simultaneous graph parameters: factor domination and factor total domination
• Dominating a family of graphs with small connected subgraphs

Cited In (5)

• Simultaneous graph parameters: factor domination and factor total domination
• Global domination
• On simultaneous domination and mixed connectivity in graphs
• Tropical dominating sets in vertex-coloured graphs
• Simultaneously dominating all spanning trees of a graph

This page was built for publication: Simultaneous domination in graphs

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