Domination in partitioned graphs with minimum degree two

Michael A. Henning; Preben Dahl Vestergaard

doi:10.1016/j.disc.2006.07.024

Domination in partitioned graphs with minimum degree two

Michael A. Henning, Preben Dahl Vestergaard

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

2 Citations (Scopus)

Abstract

Let V₁, V₂ be a partition of the vertex set in a graph G. For i = 1, 2, let γ_i denote the least number of vertices needed in G to dominate V_i. It is known that if G has order n and minimum degree two, then γ₁ + γ₂ ≤ 2 n / 3. In this paper, we characterize those graphs of order n which are edge-minimal with respect to satisfying the conditions of connected, minimum degree at least two, and γ₁ + γ₂ = 2 n / 3.

Original language	English
Pages (from-to)	1115-1135
Number of pages	21
Journal	Discrete Mathematics
Volume	307
Issue number	9-10
DOIs	https://doi.org/10.1016/j.disc.2006.07.024
Publication status	Published - 6 May 2007
Externally published	Yes

Keywords

3-subdivision
Domination
Minimum degree two
Partitioned graphs

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.disc.2006.07.024

Cite this

@article{b1facaec63824d5f946032c8a3d2d2f3,

title = "Domination in partitioned graphs with minimum degree two",

abstract = "Let V1, V2 be a partition of the vertex set in a graph G. For i = 1, 2, let γi denote the least number of vertices needed in G to dominate Vi. It is known that if G has order n and minimum degree two, then γ1 + γ2 ≤ 2 n / 3. In this paper, we characterize those graphs of order n which are edge-minimal with respect to satisfying the conditions of connected, minimum degree at least two, and γ1 + γ2 = 2 n / 3.",

keywords = "3-subdivision, Domination, Minimum degree two, Partitioned graphs",

author = "Henning, {Michael A.} and Vestergaard, {Preben Dahl}",

year = "2007",

month = may,

day = "6",

doi = "10.1016/j.disc.2006.07.024",

language = "English",

volume = "307",

pages = "1115--1135",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "9-10",

}

TY - JOUR

T1 - Domination in partitioned graphs with minimum degree two

AU - Henning, Michael A.

AU - Vestergaard, Preben Dahl

PY - 2007/5/6

Y1 - 2007/5/6

N2 - Let V1, V2 be a partition of the vertex set in a graph G. For i = 1, 2, let γi denote the least number of vertices needed in G to dominate Vi. It is known that if G has order n and minimum degree two, then γ1 + γ2 ≤ 2 n / 3. In this paper, we characterize those graphs of order n which are edge-minimal with respect to satisfying the conditions of connected, minimum degree at least two, and γ1 + γ2 = 2 n / 3.

AB - Let V1, V2 be a partition of the vertex set in a graph G. For i = 1, 2, let γi denote the least number of vertices needed in G to dominate Vi. It is known that if G has order n and minimum degree two, then γ1 + γ2 ≤ 2 n / 3. In this paper, we characterize those graphs of order n which are edge-minimal with respect to satisfying the conditions of connected, minimum degree at least two, and γ1 + γ2 = 2 n / 3.

KW - 3-subdivision

KW - Domination

KW - Minimum degree two

KW - Partitioned graphs

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

U2 - 10.1016/j.disc.2006.07.024

DO - 10.1016/j.disc.2006.07.024

M3 - Article

AN - SCOPUS:33846820162

SN - 0012-365X

VL - 307

SP - 1115

EP - 1135

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 9-10

ER -

Domination in partitioned graphs with minimum degree two

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this