Informace o publikaci
SHORT CYCLE COVERS OF GRAPHS WITH MINIMUM DEGREE THREE
| Autoři | |
|---|---|
| Rok publikování | 2010 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | SIAM Journal on Discrete Mathematics |
| Citace | |
| Doi | http://dx.doi.org/10.1137/080717468 |
| Klíčová slova | cycle cover; cycle double cover; shortest cycle cover |
| Popis | The shortest cycle cover conjecture of Alon and Tarsi asserts that the edges of every bridgeless graph with m edges can be covered by cycles of total length at most 7m/5 = 1.400m. We show that every cubic bridgeless graph has a cycle cover of total length at most 34m/21 approximate to 1.619m, and every bridgeless graph with minimum degree three has a cycle cover of total length at most 44m/27 approximate to 1.630m. |