No label defined (Q3795702)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 4061286
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 4061286

      Statements

      0 references
      0 references
      1987
      0 references
      decomposition
      0 references
      Eulerian graph
      0 references
      cycles
      0 references
      [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.
      0 references

      Identifiers