Geodesic
The eavesdropping number of a graph
Czechoslovak Mathematical Journal, Tome 59 (2009) no. 3, pp. 623-636 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
Classification : 05C40
Keywords: eavesdropping number; edge connectivity; maximally locally connected; cartesian product; vertex disjoint paths 
@article{CMJ_2009_59_3_a5,
     author = {Stuart, Jeffrey L.},
     title = {The eavesdropping number of a graph},
     journal = {Czechoslovak Mathematical Journal},
     pages = {623--636},
     year = {2009},
     volume = {59},
     number = {3},
     mrnumber = {2545645},
     zbl = {1224.05273},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_2009_59_3_a5/}
}
TY  - JOUR
AU  - Stuart, Jeffrey L.
TI  - The eavesdropping number of a graph
JO  - Czechoslovak Mathematical Journal
PY  - 2009
SP  - 623
EP  - 636
VL  - 59
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/CMJ_2009_59_3_a5/
LA  - en
ID  - CMJ_2009_59_3_a5
ER  - 
%0 Journal Article
%A Stuart, Jeffrey L.
%T The eavesdropping number of a graph
%J Czechoslovak Mathematical Journal
%D 2009
%P 623-636
%V 59
%N 3
%U http://geodesic.mathdoc.fr/item/CMJ_2009_59_3_a5/
%G en
%F CMJ_2009_59_3_a5
Stuart, Jeffrey L. The eavesdropping number of a graph. Czechoslovak Mathematical Journal, Tome 59 (2009) no. 3, pp. 623-636. http://geodesic.mathdoc.fr/item/CMJ_2009_59_3_a5/

[1] Cai, C.: The maximal size of graphs with at most $k$ edge-disjoint paths connecting any two adjacent vertices. Discrete Math. 85 (1990), 43-52. | DOI | MR | Zbl

[2] Chartrand, G., Harary, F.: Graphs with prescribed connectivities. Theory of Graphs, Proc. Colloq., Tihany, Hungary, 1966 Académiai Kiadói Budapest (1968), 61-63. | MR | Zbl

[3] Chartrand, G., Oellermann, O. R.: Applied and Algorithmic Graph Theory. McGraw-Hill New York (1993). | MR

[4] Fricke, G., Oellermann, O. R., Swart, H. C.: The edge-connectivity, average edge-connectivity and degree conditions. Manuscript (2000).

[5] Hellwig, A.: Maximally connected graphs and digraphs. Doctoral dissertation Rheinisch-Westfälishchen Technische Hochschule Aachen (2005).

[6] Hellwig, A., Volkmann, L.: Maximally local-edge-connected graphs and digraphs. Ars. Comb. 72 (2004), 295-306. | MR | Zbl

[7] Huck, A., Okamura, H.: Counterexamples to a conjecture of Mader about cycles through specified vertices in $n$-edge-connected graphs. Graphs Comb. 8 (1992), 253-258. | DOI | MR | Zbl

[8] Mader, W.: Existenz gewisser Konfigurationen in $n$-gesättigten Graphen und in Graphen genügend grosser Kantendichte. Math. Ann. 194 (1971), 295-312 German. | DOI | MR | Zbl

[9] Whitney, H.: Congruent graphs and the connectivity of graphs. Am. J. Math. 54 (1932), 150-168. | DOI | MR | Zbl

[10] Xu, J.-M., Yang, C.: Connectivity of Cartesian product graphs. Discrete Math. 306 (2006), 159-165. | DOI | MR | Zbl