An upper bound on the paired-domination number in terms of the number of edges in the graph

Michael A. Henning

doi:10.1016/j.disc.2010.06.033

An upper bound on the paired-domination number in terms of the number of edges in the graph

Michael A. Henning

Mathematics and Applied Mathematics

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

5 Citations (Scopus)

Abstract

In this paper, we continue the study of paired domination in graphs introduced by Haynes and Slater [T.W. Haynes, P.J. Slater, Paired-domination in graphs, Networks 32 (1998) 199-206]. A paired-dominating set of a graph is a dominating set whose induced subgraph contains a perfect matching. The paired-domination number of a graph G, denoted by γ_pr(G), is the minimum cardinality of a paired-dominating set in G. We show that if G is a connected graph of size m ≥ 18 with minimum degree at least 2, then γ_pr(G) ≤ 4m/7 and we characterize the (infinite family of) graphs that achieve equality in this bound.

Original language	English
Pages (from-to)	2847-2857
Number of pages	11
Journal	Discrete Mathematics
Volume	310
Issue number	21
DOIs	https://doi.org/10.1016/j.disc.2010.06.033
Publication status	Published - 6 Nov 2010

Keywords

Bounds
Minimum degree 2
Paired domination
Size

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.disc.2010.06.033

Cite this

@article{10fa0d5ba65443ad95a57d0c0096e060,

title = "An upper bound on the paired-domination number in terms of the number of edges in the graph",

abstract = "In this paper, we continue the study of paired domination in graphs introduced by Haynes and Slater [T.W. Haynes, P.J. Slater, Paired-domination in graphs, Networks 32 (1998) 199-206]. A paired-dominating set of a graph is a dominating set whose induced subgraph contains a perfect matching. The paired-domination number of a graph G, denoted by γpr(G), is the minimum cardinality of a paired-dominating set in G. We show that if G is a connected graph of size m ≥ 18 with minimum degree at least 2, then γpr(G) ≤ 4m/7 and we characterize the (infinite family of) graphs that achieve equality in this bound.",

keywords = "Bounds, Minimum degree 2, Paired domination, Size",

author = "Henning, {Michael A.}",

year = "2010",

month = nov,

day = "6",

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

language = "English",

volume = "310",

pages = "2847--2857",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "21",

}

TY - JOUR

T1 - An upper bound on the paired-domination number in terms of the number of edges in the graph

AU - Henning, Michael A.

PY - 2010/11/6

Y1 - 2010/11/6

N2 - In this paper, we continue the study of paired domination in graphs introduced by Haynes and Slater [T.W. Haynes, P.J. Slater, Paired-domination in graphs, Networks 32 (1998) 199-206]. A paired-dominating set of a graph is a dominating set whose induced subgraph contains a perfect matching. The paired-domination number of a graph G, denoted by γpr(G), is the minimum cardinality of a paired-dominating set in G. We show that if G is a connected graph of size m ≥ 18 with minimum degree at least 2, then γpr(G) ≤ 4m/7 and we characterize the (infinite family of) graphs that achieve equality in this bound.

AB - In this paper, we continue the study of paired domination in graphs introduced by Haynes and Slater [T.W. Haynes, P.J. Slater, Paired-domination in graphs, Networks 32 (1998) 199-206]. A paired-dominating set of a graph is a dominating set whose induced subgraph contains a perfect matching. The paired-domination number of a graph G, denoted by γpr(G), is the minimum cardinality of a paired-dominating set in G. We show that if G is a connected graph of size m ≥ 18 with minimum degree at least 2, then γpr(G) ≤ 4m/7 and we characterize the (infinite family of) graphs that achieve equality in this bound.

KW - Bounds

KW - Minimum degree 2

KW - Paired domination

KW - Size

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

U2 - 10.1016/j.disc.2010.06.033

DO - 10.1016/j.disc.2010.06.033

M3 - Article

AN - SCOPUS:79952987666

SN - 0012-365X

VL - 310

SP - 2847

EP - 2857

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 21

ER -

An upper bound on the paired-domination number in terms of the number of edges in the graph

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this