The e-mail gossip number and the connected domination number (Q1372291)

A new numerical invariant of a graph, named the e-mail gossip number, is introduced. The vertices of the graph are considered as persons; each person knows an information which is not known to any other person. The edges represent direct phone connections. Each person sends e-mail messages to the others; always such a message is sent to all neighbours of the given vertex at the same time. The minimum number of such messages needed for each person to acquire all items is called the e-mail gossip number \(\text{eg}(G)\) of the graph \(G\). In the paper it is proved that \(\text{eg}(G)= n-1+\text{cd}(G)\), where \(n\) is the number of vertices of \(G\) and \(\text{cd}(G)\) is the connected domination number of \(G\), i.e. the minimum number of vertices of a dominating set of \(G\) which induces a connected subgraph. At the end, it is proved that the problem whether \(\text{eg}(G)\leq k\), for a given \(G\) and given integer \(k\), is NP-complete.