✦ LIBER ✦

Upper bounds on the paired-domination number

✍ Scribed by Xue-gang Chen; Wai Chee Shiu; Wai Hong Chan

Publisher: Elsevier Science
Year: 2008
Tongue: English
Weight: 199 KB
Volume: 21
Category: Article
ISSN: 0893-9659
DOI: 10.1016/j.aml.2007.10.029

No coin nor oath required. For personal study only.

✦ Synopsis

A set S of vertices in a graph G is a paired-dominating set of G if every vertex of G is adjacent to some vertex in S and the subgraph induced by S contains a perfect matching. The minimum cardinality of a paired-dominating set of G is the paireddomination number of G, denoted by γ pr (G). In this work, we present several upper bounds on the paired-domination number in terms of the maximum degree, minimum degree, girth and order.

📜 SIMILAR VOLUMES

A note on the upper bound for the paired

A note on the upper bound for the paired-domination number of a graph with minimum degree at least two

✍ Shenwei Huang; Erfang Shan 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 70 KB 👁 1 views

An Upper Bound for the Independent Domin

An Upper Bound for the Independent Domination Number

✍ Liang Sun; Jianfang Wang 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 87 KB

Let G be a simple graph of order n and minimum degree $. The independent domination number i(G) is defined to be the minimum cardinality among all maximal independent sets of vertices of G. In this paper, we show that i(G) n+2$&2 -n$. Thus a conjecture of Favaron is settled in the affirmative.

Bounds on the -domination number of a gr

Bounds on the -domination number of a graph

✍ Ermelinda DeLaViña; Wayne Goddard; Michael A. Henning; Ryan Pepper; Emil R. Vaug 📂 Article 📅 2011 🏛 Elsevier Science 🌐 English ⚖ 200 KB

The k-domination number of a graph is the cardinality of a smallest set of vertices such that every vertex not in the set is adjacent to at least k vertices of the set. We prove two bounds on the k-domination number of a graph, inspired by two conjectures of the computer program Graffiti.pc. In part

A sharp upper bound on algebraic connect

A sharp upper bound on algebraic connectivity using domination number

✍ M. Aouchiche; P. Hansen; D. Stevanović 📂 Article 📅 2010 🏛 Elsevier Science 🌐 English ⚖ 760 KB

Let G be a connected graph of order n. The algebraic connectivity of G is the second smallest eigenvalue of the Laplacian matrix of G. A dominating set in G is a vertex subset S such that each vertex of G that is not in S is adjacent to a vertex in S. The least cardinality of a dominating set is the

Some upper bounds for the product of the

Some upper bounds for the product of the domination number and the chromatic number of a graph

✍ Jerzy Topp; Lutz Volkmann 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 199 KB

Topp, J. and L. Volkmann, Some upper bounds for the product of the domination number and the chromatic number of a graph, Discrete Mathematics 118 (1993) 2899292. Some new upper bounds for yx are proved, where y is the domination number and x is the chromatic number of a graph. All graphs consider

An upper bound for the k-domination numb

An upper bound for the k-domination number of a graph

✍ E. J. Cockayne; B. Gamble; B. Shepherd 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 82 KB 👁 2 views

The kdomination number of a graph G, y k ( G ) , is the least cardinality of a set U of verticies such that any other vertex is adjacent to at least k vertices of U. We prove that if each vertex has degree at least k. then YAG) 5 kp/(k + 1).