Extremal 3-connected graphs
Theorem 2: Let G be a 3-connected graph with minimum degree at least d and with at least 2d-1 vertices. Then for any 3 distinct vertices x, y, z there is a path from x to z through y and having length at least 2d-2. Furthermore, suppose that G has at least 2d vertices, that no set of exactly d vertices meets every edge and that for every vertex \(v\neq x\), z, G-\(\{\) x,v,z\(\}\) has a component which is not a complete graph \(K_{d-2}\). Then there is a path from x to z through y and having length at least 2d-1. From the proof of this theorem it follows that there are only the next two extremal examples of graphs having more than 2d-1 vertices. Example 1. Let H be any graph on d vertices and let S be an independent set of vertices disjoint from H, \(| S| \geq d-1\). Let G be the graph obtained by adding edges from every vertex of S to every vertex of H. Example 2. Let H be the disjoint union of complete graphs each having d-2 vertices. Let x, z, v be three vertices disjoint from H and let F be any graph with \(V(F)=\{x,v,z\}\). Let G be the graph obtained by joining every vertex of H to every vertex of F.
- A generalization of Dirac's theorem
- Graph theory
- scientific article; zbMATH DE number 3929041 (Why is no real title available?)
- scientific article; zbMATH DE number 3685495 (Why is no real title available?)
- Long paths and large cycles in finite graphs
- Relative lengths of paths and cycles in k-connected graphs
This page was built for publication: Extremal 3-connected graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1106857)
