๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Some results on characterizing the edges of connected graphs with a given domination number

โœ Scribed by Laura A. Sanchis

Publisher
Elsevier Science
Year
1995
Tongue
English
Weight
821 KB
Volume
140
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

โœฆ Synopsis

A dominatin# set for a graph G = (V, E) is a subset of vertices V' c_ V such that for all v โ€ข V-V' there exists some uโ€ข V' for which {v,u} โ€ขE. The domination number of G is the size of its smallest dominating set(s). For a given graph G with minimum size dominating set D, let mz(G, D) denote the number of edges that have neither endpoint in D, and let m2(G,D ) denote the number of edges that have at least one endpoint in D. We characterize the possible values that the pair (mz(G,D),m2(G,D)) can attain for connected graphs having a given domination number.

๐Ÿ“œ SIMILAR VOLUMES

A remark on the number of vertices of de
A remark on the number of vertices of degree k in a minimally k-edge-connected graph
โœ Mao-cheng Cai ๐Ÿ“‚ Article ๐Ÿ“… 1992 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 395 KB

Let G be a minimally k-edge-connected simple graph and u\*(G) be the number of vertices of degree k in G. proved that (i) uk(G) 2 l(jGl -1)/(2k + l)] + k + 1 for even k, and (ii) uI(G) 2 [lGl/(k + l)] + k for odd k 35 and u,(G) 2 lZlGl/(k + l)] + k -2 for odd k 27, where ICI denotes the number of v