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
1987
0 references
decomposition
0 references
Eulerian graph
0 references
cycles
0 references
0.9054671
0 references
0.9013813
0 references
0.89822865
0 references
0.89326084
0 references
0.89121807
0 references
0.8820596
0 references
0 references
0.8782283
0 references
0.87715733
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