Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
eavesdropping number; edge connectivity; maximally locally connected; cartesian product; vertex disjoint paths
eavesdropping number; edge connectivity; maximally locally connected; cartesian product; vertex disjoint paths
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.
References:
[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 10.1016/0012-365X(90)90161-A | MR 1078310 | Zbl 0749.05041
[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 0236048 | Zbl 0186.27503
[3] Chartrand, G., Oellermann, O. R.: Applied and Algorithmic Graph Theory. McGraw-Hill New York (1993). MR 1211413
[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 2069069 | Zbl 1082.05055
[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 10.1007/BF02349962 | MR 1185404 | Zbl 0770.05067
[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 10.1007/BF01350130 | MR 0289344 | Zbl 0213.50801
[9] Whitney, H.: Congruent graphs and the connectivity of graphs. Am. J. Math. 54 (1932), 150-168. DOI 10.2307/2371086 | MR 1506881 | Zbl 0003.32804
[10] Xu, J.-M., Yang, C.: Connectivity of Cartesian product graphs. Discrete Math. 306 (2006), 159-165. DOI 10.1016/j.disc.2005.11.010 | MR 2202083 | Zbl 1085.05042
Search
Partner of
