Edge-superconnectivity

Материал из WikiGrapp
Версия от 11:49, 13 апреля 2011; KEV (обсуждение | вклад)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

Edge-superconnectivity — рёберная суперсвязность.

Superconnectivity is a stronger measure of connectivity. A maximally edge-connected graph is called super-[math]\displaystyle{ \lambda }[/math] if every edge cut [math]\displaystyle{ (C,\bar{C}) }[/math] of cardinality [math]\displaystyle{ \delta(G) }[/math] satisfies either [math]\displaystyle{ |C| = 1 }[/math] or [math]\displaystyle{ |\bar{C}| = 1 }[/math]. In order to measure the super edge-connectivity, we use the following parameter:

[math]\displaystyle{ \lambda_{1}(G) = \min \{|(C,\bar{C})|, \; (C,\bar{C}) \mbox{ is a nontrivial edge cut}\}. }[/math]

We define the edge-superconnectivity of a graph [math]\displaystyle{ G }[/math] as the value of [math]\displaystyle{ \lambda_{1}(G) }[/math].