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
关键词
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
相关论文
共 5 条
[1]  
[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
[2]  
Harary F., 1969, GRAPH THEORY
[3]  
HAYNES TW, 1997, IN PRESS FUNDAMENTAL
[4]   BIBLIOGRAPHY ON DOMINATION IN GRAPHS AND SOME BASIC DEFINITIONS OF DOMINATION PARAMETERS [J].
HEDETNIEMI, ST ;
LASKAR, RC .
DISCRETE MATHEMATICS, 1990, 86 (1-3) :257-277
[5]  
Sampathkumar E., 1979, Int. J. Phys. Math. Sci., V16, P607