The eavesdropping number of a graph
Jeffrey L. Stuart · Czechoslovak Mathematical Journal · 2009
Let G be a connected, undirected graph without loops and without multiple edges. For a pair of distinct vertices u and v , a minimum { u, v }-separating set is a smallest set of edges in G whose removal disconnects u and v . The edge connectivity of G , denoted λ ( G ), is defined to be the minimum cardinality of a minimum { u, v }-separating set as u and v range over all pairs of distinct vertices in G . We introduce and investigate the eavesdropping number, denoted ε ( G ), which is defined to be the maximum cardinality of a minimum { u, v }-separating set as u and v range over all pairs of distinct vertices in G . Results are presented for regular graphs and maximally locally connected graphs, as well as for a number of common families of graphs.