THE E-MAIL GOSSIP NUMBER AND THE CONNECTED DOMINATION NUMBER

Authors
HARARY F RAGHAVACHARI B
Citation
F. Harary et B. Raghavachari, THE E-MAIL GOSSIP NUMBER AND THE CONNECTED DOMINATION NUMBER, Applied mathematics letters, 10(4), 1997, pp. 15-17
Citations number
5
Categorie Soggetti
Mathematics,Mathematics
Journal title
Applied mathematics letters → ACNP
ISSN journal
08939659
Volume
10
Issue
4
Year of publication
1997
Pages
15 - 17
Database
ISI
SICI code
0893-9659(1997)10:4<15:TEGNAT>2.0.ZU;2-G
Abstract
Our object is to introduce eg(G), the e-mail gossip number of a connec ted graph G, and derive a simple equation expressing this new invarian t in terms of the known [1] connected domination number cd(G). As a co rollary we see that determining each of these numbers is NP-hard. In g eneral we follow the graph theoretic notation and terminology of [2]. Throughout G = (V, E) is a connected graph with \V\ = n nodes.