The e-mail gossip number and the connected domination number

被引：4

作者：

Harary, F ^{[1
]}

Raghavachari, B ^{[1
]}

机构：

[1] UNIV TEXAS,COMP SCI PROGRAM,RICHARDSON,TX 75083

来源：

APPLIED MATHEMATICS LETTERS | 1997年 / 10卷 / 04期

关键词：

combinatorial problems; graphs; domination in graphs; gossip problems;

D O I：

10.1016/S0893-9659(97)00052-9

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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 \V\ = n nodes.

引用

页码：15 / 17

页数：3