Hajós' conjecture and small cycle double covers of planar graphs (Q1197036): Difference between revisions
From MaRDI portal
Created a new Item |
Created claim: Wikidata QID (P12): Q122927381, #quickstatements; #temporary_batch_1706326753173 |
||
Property / Wikidata QID | |||
Property / Wikidata QID: Q122927381 / rank | |||
Normal rank |
Revision as of 05:42, 27 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Hajós' conjecture and small cycle double covers of planar graphs |
scientific article |
Statements
Hajós' conjecture and small cycle double covers of planar graphs (English)
0 references
16 January 1993
0 references
A graph is said to be even if all its vertices have even degree, and it is well known that the edge set of a graph \(G\) can be partitioned into cycles if and only if \(G\) is even. Such a partition of the edges of a graph is called a cycle decomposition of the graph. We let \(c(G)\) denote the minimum number of cycles required in a cycle decomposition of an even graph \(G\). A cycle double cover, \({\mathcal C}\), of a graph \(G\) is a collection of cycles containing every edge of \(G\) exactly twice. If \(G\) has \(n\) vertices, then \({\mathcal C}\) is called a small cycle double cover if it contains at most \(n-1\) cycles. There exist even graphs \(G\) on \(n\) vertices for which \(c(G)\geq\lfloor(n-1)/2\rfloor\), and \textit{G. Hajós} conjectured that every simple even graph \(G\) on \(n\) vertices has \(c(G)\leq\lfloor(n-1)/2\rfloor\). We prove this conjecture for planar graphs (a somewhat incomplete proof was given earlier by \textit{J. Tao}). We then discuss the connection between this result and small cycle double covers of graphs.
0 references
Hajós' conjecture
0 references
cycle decomposition
0 references
cycle double cover
0 references
planar graphs
0 references