| Title:
|
The eavesdropping number of a graph (English) |
| Author:
|
Stuart, Jeffrey L. |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
59 |
| Issue:
|
3 |
| Year:
|
2009 |
| Pages:
|
623-636 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
eavesdropping number |
| Keyword:
|
edge connectivity |
| Keyword:
|
maximally locally connected |
| Keyword:
|
cartesian product |
| Keyword:
|
vertex disjoint paths |
| MSC:
|
05C40 |
| idZBL:
|
Zbl 1224.05273 |
| idMR:
|
MR2545645 |
| . |
| Date available:
|
2010-07-20T15:30:17Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/140505 |
| . |
| Reference:
|
[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. Zbl 0749.05041, MR 1078310, 10.1016/0012-365X(90)90161-A |
| Reference:
|
[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. Zbl 0186.27503, MR 0236048 |
| Reference:
|
[3] Chartrand, G., Oellermann, O. R.: Applied and Algorithmic Graph Theory.McGraw-Hill New York (1993). MR 1211413 |
| Reference:
|
[4] Fricke, G., Oellermann, O. R., Swart, H. C.: The edge-connectivity, average edge-connectivity and degree conditions.Manuscript (2000). |
| Reference:
|
[5] Hellwig, A.: Maximally connected graphs and digraphs.Doctoral dissertation Rheinisch-Westfälishchen Technische Hochschule Aachen (2005). |
| Reference:
|
[6] Hellwig, A., Volkmann, L.: Maximally local-edge-connected graphs and digraphs.Ars. Comb. 72 (2004), 295-306. Zbl 1082.05055, MR 2069069 |
| Reference:
|
[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. Zbl 0770.05067, MR 1185404, 10.1007/BF02349962 |
| Reference:
|
[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. Zbl 0213.50801, MR 0289344, 10.1007/BF01350130 |
| Reference:
|
[9] Whitney, H.: Congruent graphs and the connectivity of graphs.Am. J. Math. 54 (1932), 150-168. Zbl 0003.32804, MR 1506881, 10.2307/2371086 |
| Reference:
|
[10] Xu, J.-M., Yang, C.: Connectivity of Cartesian product graphs.Discrete Math. 306 (2006), 159-165. Zbl 1085.05042, MR 2202083, 10.1016/j.disc.2005.11.010 |
| . |
