There Exist Highly Critically Connected Graphs of Diameter Three |
| |
Authors: | Matthias Kriesell |
| |
Affiliation: | 1. Mathematisches Seminar der Universit?t Hamburg, Bundesstra?e 55, D–20146, Hamburg, Germany
|
| |
Abstract: | Let κ(G) denote the (vertex) connectivity of a graph G. For ℓ≥0, a noncomplete graph of finite connectivity is called ℓ-critical if κ(G−X)=κ(G)−|X| for every X⊆V(G) with |X|≤ℓ. Mader proved that every 3-critical graph has diameter at most 4 and asked for 3-critical graphs having diameter exceeding 2. Here we give an affirmative answer by constructing an ℓ-critical graph of diameter 3 for every ℓ≥3. |
| |
Keywords: | Critical connectivity Diameter |
本文献已被 SpringerLink 等数据库收录! |