scientific article; zbMATH DE number 4061286
[For the entire collection see Zbl 0608.00016.] Let G be an Eulerian graph of order n and \(c=c(G)\) be a minimum number of edge-disjoint cycles needed to partition the edge set of G. Hajós conjecture [see \textit{C. Berge}: ``Graphs and hypergraphs (2nd rev. ed., translation into English) (1976; Zbl 0311.05101), pp. 232-234] that \(c\leq \lfloor n/2\rfloor\). It is known that \(c\leq \lfloor (n-1)/2\rfloor\) for complete graphs of odd order and for complete graphs of even order with a perfect matching removed. The two main results of this paper are: Theorem 1. For every Eulerian graph G of order n with maximum degree at most 4, c(G)\(\leq \lfloor (n-1)/2\rfloor\). Theorem 2. For every integer \(n\geq 3\) and every integer i, \(1\leq i\leq \lfloor (n-1)/2\rfloor\), there exists an Eulerian graph \(G_ i\) of order n with maximum degree at most 4 such that \(c(G_ i)=i\). The authors ask whether the bound \(c\leq \lfloor (n- 1)/2\rfloor\) is sharp for 4-regular graphs.
- On the Eulerian cycle decomposition conjecture and complete multipartite graphs
- Hajós' conjecture and connectivity of Eulerian graphs
- Hajós' conjecture and cycle power graphs
- A cycle decomposition conjecture for Eulerian graphs
- Vertex-minors and the Erdős-Hajnal conjecture
- The Erdős-Hajnal property for graphs with no fixed cycle as a pivot-minor
- On the Hajós number of graphs
- On partition dimension of some cycle-related graphs
- On Hadwiger conjecture for certain families of graphs with restricted number of cycles
- On the minimum number of Hamiltonian cycles in regular graphs
- Hajós' conjecture and small cycle double covers of planar graphs
- Hajós' conjecture and projective graphs
- Hajós' conjecture and connectivity of Eulerian graphs
- Long cycles, heavy cycles and cycle decompositions in digraphs
- Decomposing toroidal graphs into circuits and edges
- Parity equivalence in eulerian graphs
- scientific article; zbMATH DE number 5016710 (Why is no real title available?)
- scientific article; zbMATH DE number 3948320 (Why is no real title available?)
- What is the smallest number of dicycles in a dicycle decomposition of an eulerian digraph?
- scientific article; zbMATH DE number 63789 (Why is no real title available?)
- -MINIMUM SPANNING LENGTHS AND AN EXTENSION TO BURNSIDE’S THEOREM ON IRREDUCIBILITY
- Cycle decompositions of pathwidth-6 graphs
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3795702)