scientific article; zbMATH DE number 4061286

From MaRDI portal
Publication:3795702





[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.











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)