✦ LIBER ✦

The e-mail gossip number and the connected domination number

✍ Scribed by F. Harary; B. Raghavachari

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 184 KB
Volume: 10
Category: Article
ISSN: 0893-9659
DOI: 10.1016/s0893-9659(97)00052-9

No coin nor oath required. For personal study only.

✦ Synopsis

Our

object is to introduce eg(G), the e-mail gossip number of a connected graph G, and derive a simple equation expressing this new invariant in terms of the known [1] connected domination number cd(G). As a corollary we see that determining each of these numbers is NP-hard. In general we follow the graph theoretic notation and terminology of [2]. Throughout G = (V, E) is a connected graph with IV] = n nodes.

📜 SIMILAR VOLUMES

The connected hub number and the connect

The connected hub number and the connected domination number

✍ Peter Johnson; Peter Slater; Matt Walsh 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 189 KB

The difference between the domination nu

The difference between the domination number and the minus domination number of a cubic graph

✍ Xiaofan Yang; Qibin Hou; Xiangsheng Huang; Hengnong Xuan 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 325 KB

The closed neighborhood of a vertex subset S of a graph G = (V,E), denoted as N[Sj, is defined ss the union of S and the set of all the vertices adjacent to some vertex of S. A dominating set of a graph G = (V, E) is defined as a set S of vertices such that N[q = V. The domination number of a graph

The ratio of the irredundance number and

The ratio of the irredundance number and the domination number for block-cactus graphs

✍ Zverovich, V. E. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 96 KB 👁 2 views

Let γ(G) and ir(G) denote the domination number and the irredundance number of a graph G, respectively. Allan and Laskar [Proc. 9th Southeast Conf. on Combin., Graph Theory & Comp. (1978) 43-56] and Bollobás and Cock- ayne [J. Graph Theory (1979) 241-249] proved independently that γ(G) < 2ir(G) for

Inequalities between the domination numb

Inequalities between the domination number and the chromatic number of a graph

✍ Dieter Gernert 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 230 KB

Upper bounds for u + x and ax are proved, where u is the domination number and x the chromatic number of a graph.

The number of connected sparsely edged g

The number of connected sparsely edged graphs

✍ E. M. Wright 📂 Article 📅 1977 🏛 John Wiley and Sons 🌐 English ⚖ 472 KB

## Abstract An (__n, q__) graph has __n__ labeled points, __q__ edges, and no loops or multiple edges. The number of connected (__n, q__) graphs is __f(n, q)__. Cayley proved that __f(n, n__^‐1^) = __n__^n−2^ and Renyi found a formula for __f(n, n)__. Here I develop two methods to calculate the exp

Some results on characterizing the edges

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

✍ Laura A. Sanchis 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 821 KB

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 nu