Connected graph

Connected graph — связный граф.

A graph [math]\displaystyle{ \,G }[/math] is a connected graph if for all [math]\displaystyle{ \,u,v \in V(G) }[/math], [math]\displaystyle{ \,u \neq v }[/math], there is a chain [math]\displaystyle{ \,(v_{1}, \ldots, v_{k}) }[/math] in [math]\displaystyle{ \,G }[/math] with [math]\displaystyle{ \,\{v_{1}, v_{k}\} = \{u,v\} }[/math], (the chain connects [math]\displaystyle{ \,u }[/math] and [math]\displaystyle{ \,v }[/math]). Otherwise, the graph is called disconnected.

A graph [math]\displaystyle{ \,G = (V,E) }[/math] is maximum edge-connected (in short, max-[math]\displaystyle{ \,\lambda }[/math]) if [math]\displaystyle{ \,\lambda = [2q/p] }[/math], where [math]\displaystyle{ \,p = |V|, \; q = |E| }[/math] and [math]\displaystyle{ \,\lambda = \lambda(G) }[/math] is edge-connectivity of [math]\displaystyle{ \,G }[/math]. Note that the set of edges adjacent to a point [math]\displaystyle{ \,u }[/math] of degree [math]\displaystyle{ \,\lambda }[/math] is certainly a minimum edge-disconneting set. Similarly, [math]\displaystyle{ \,G }[/math] is maximum point-connected (in short, max-[math]\displaystyle{ \,\kappa }[/math]) if [math]\displaystyle{ \,\kappa = [2q/p] }[/math], where [math]\displaystyle{ \,\kappa = \kappa(G) }[/math] is the point-connectivity of [math]\displaystyle{ \,G }[/math]. Also, the set of points adjacent to [math]\displaystyle{ \,u }[/math] of degree [math]\displaystyle{ \,\kappa }[/math] is certainly a minimum point-disconnecting set. In this context, such an edge or a point set is called trivial. A graph [math]\displaystyle{ \,G }[/math] is called super edge-connected if [math]\displaystyle{ \,G }[/math] is max-[math]\displaystyle{ \,\lambda }[/math] and every minimum edge-disconnecting set is trivial. Analogously, [math]\displaystyle{ \,G }[/math] is super point connected if [math]\displaystyle{ \,G }[/math] is max-[math]\displaystyle{ \,\kappa }[/math] and every minimum point-disconnecting set is trivial.

Литература

• Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.