On circuits through five edges
type: Item
instance of: scholarly article
title: On circuits through five edges
zbMATH Open document ID: 0864.05054
DOI: 10.1016/0012-365X(95)00079-C
author: Daniel P. Sanders
published in: Discrete Mathematics
publication date: 1997-06-22T00:00:00Z
review text: \textit{L. Lovász} [Problem 5, Period. Math. Hung. 4, 82 (1974)] and \textit{D. R. Woodall} [J. Comb. Theory, Ser. B 22, 274-278 (1977; Zbl 0362.05069)] independently conjectured that if \(L\) is an independent set of \(k\) vertices in a \(k\)-connected graph \(G\), then \(G\) has a circuit containing the edges of \(L\) iff \(L\) is not an odd edge cut. Lovász [op. cit.] proved the conjecture true for \(k=3\) while the case \(k=4\) was settled affirmatively, independently, by Robertson (unpublished manuscript), \textit{P. L. Erdös} and \textit{E. Györi} [Acta Math. Hung. 46, 311-313 (1985; Zbl 0588.05024)], and \textit{M. V. Lomonosov} [Cycles through prescribed elements in a graph, Paths, flows, and VLSI-layout, Proc. Meet., Bonn/Ger. 1988, Algorithms Comb. 9, 215-234 (1990; Zbl 0751.05059)]. The author shows the conjecture is true for the case \(k=5\).
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 955094
zbMATH Keywords: independent set
zbMATH Keywords: circuit
zbMATH Keywords: conjecture
reviewed by: R. C. Entringer
MaRDI profile type: Publication
cites work: Cycles through four edges in 3-connected cubic graphs
cites work: In abstrakten Graphen vorhandene vollständige 4‐Graphen und ihre Unterteilungen
cites work: Any four independent edges of a 4-connected graph are contained in a circuit
cites work: Circuits through specified edges
cites work: Q3972952
cites work: Note on circuits containing specified edges
cites work: Circuits containing specified edges
description: scientific article; zbMATH DE number 955094