Simultaneous Domination in Graphs

Yair Caro; Michael A. Henning

doi:10.1007/s00373-013-1353-5

Simultaneous Domination in Graphs

Yair Caro, Michael A. Henning

Mathematics and Applied Mathematics

University of Haifa

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

5 Citations (Scopus)

Abstract

Let F₁, F₂, …, F_k be graphs with the same vertex set V. A subset S ⊆ V is a simultaneous dominating set if for every i, 1 ≤ i ≤ k, 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.

Original language	English
Pages (from-to)	1399-1416
Number of pages	18
Journal	Graphs and Combinatorics
Volume	30
Issue number	6
DOIs	https://doi.org/10.1007/s00373-013-1353-5
Publication status	Published - 14 Oct 2014

Keywords

Factor domination

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1007/s00373-013-1353-5

Cite this

@article{f349b0aed79a43b8be1a9abf8156951d,

title = "Simultaneous Domination in Graphs",

abstract = "Let F1, F2, …, Fk be graphs with the same vertex set V. A subset S ⊆ V is a simultaneous dominating set if for every i, 1 ≤ i ≤ k, every vertex of Fi not in S is adjacent to a vertex in S in Fi; that is, the set S is simultaneously a dominating set in each graph Fi. 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, Fi, are r-regular or the disjoint union of copies of Kr. Further we study the case when each factor is a cycle.",

keywords = "Factor domination",

author = "Yair Caro and Henning, {Michael A.}",

note = "Publisher Copyright: {\textcopyright} 2013, Springer Japan.",

year = "2014",

month = oct,

day = "14",

doi = "10.1007/s00373-013-1353-5",

language = "English",

volume = "30",

pages = "1399--1416",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "6",

}

TY - JOUR

T1 - Simultaneous Domination in Graphs

AU - Caro, Yair

AU - Henning, Michael A.

PY - 2014/10/14

Y1 - 2014/10/14

N2 - Let F1, F2, …, Fk be graphs with the same vertex set V. A subset S ⊆ V is a simultaneous dominating set if for every i, 1 ≤ i ≤ k, every vertex of Fi not in S is adjacent to a vertex in S in Fi; that is, the set S is simultaneously a dominating set in each graph Fi. 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, Fi, are r-regular or the disjoint union of copies of Kr. Further we study the case when each factor is a cycle.

AB - Let F1, F2, …, Fk be graphs with the same vertex set V. A subset S ⊆ V is a simultaneous dominating set if for every i, 1 ≤ i ≤ k, every vertex of Fi not in S is adjacent to a vertex in S in Fi; that is, the set S is simultaneously a dominating set in each graph Fi. 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, Fi, are r-regular or the disjoint union of copies of Kr. Further we study the case when each factor is a cycle.

KW - Factor domination

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

U2 - 10.1007/s00373-013-1353-5

DO - 10.1007/s00373-013-1353-5

M3 - Article

AN - SCOPUS:84918819367

SN - 0911-0119

VL - 30

SP - 1399

EP - 1416

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 6

ER -

Simultaneous Domination in Graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this