Extremal 3-connected graphs
type: Item
instance of: scholarly article
title: Extremal 3-connected graphs
zbMATH Open document ID: 0652.05028
DOI: 10.1016/0012-365X(88)90117-3
author: S. C. Locke
published in: Discrete Mathematics
publication date: 1988-01-01T00:00:00Z
review text: 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.
reviewed by: M.Koman
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 4063121
zbMATH Keywords: 2-connected graphs
zbMATH Keywords: longest path
zbMATH Keywords: independent set
zbMATH Keywords: 3-connected graph
MaRDI profile type: Publication
cites work: Q3703921
cites work: Q5422499
cites work: Long paths and large cycles in finite graphs
cites work: A generalization of Dirac's theorem
cites work: Relative lengths of paths and cycles in k-connected graphs
cites work: Q3880849
full work available at URL: 0012-365x(88)90117-3
OpenAlex ID: W2019516099
description: scientific article; zbMATH DE number 4063121