The eavesdropping number of a graph

Stuart, Jeffrey L.

Czechoslovak Mathematical Journal, Tome 59 (2009) no. 3, pp. 623-636.

Résumé

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 $\lambda (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 $\varepsilon (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.

Détail

Classification : 05C40
Keywords: eavesdropping number; edge connectivity; maximally locally connected; cartesian product; vertex disjoint paths