Search

Your search keyword '"shortest cycle cover"' showing total 5 results
Start Over Descriptor "shortest cycle cover"
5 results on '"shortest cycle cover"'

1. On Cubic Bridgeless Graphs Whose Edge-Set Cannot be Covered by Four Perfect Matchings.

Author

Esperet, L. and Mazzuoccolo, G.

Subjects
*GRAPHIC methods, *GRAPH theory, *CUBIC curves, *ALGEBRAIC curves, *ELLIPTIC curves
Abstract

The problem of establishing the number of perfect matchings necessary to cover the edge-set of a cubic bridgeless graph is strictly related to a famous conjecture of Berge and Fulkerson. In this article, we prove that deciding whether this number is at most four for a given cubic bridgeless graph is NP-complete. We also construct an infinite family [ABSTRACT FROM AUTHOR]

Published
2014
Full Text
View/download PDF

2. A note on shortest cycle covers of cubic graphs.

Author

Hou, Xinmin and Zhang, Cun-Quan

Abstract

Let SCC3( G) be the length of a shortest 3-cycle cover of a bridgeless cubic graph G. It is proved in this note that if G contains no circuit of length 5 (an improvement of Jackson's ( JCTB 1994) result: if G has girth at least 7) and if all 5-circuits of G are disjoint (a new upper bound of SCC3( G) for the special class of graphs). [ABSTRACT FROM AUTHOR]

Published
2012
Full Text
View/download PDF

3. SHORT CYCLE COVERS OF GRAPHS WITH MINIMUM DEGREE THREE.

Author

Kaiser, Tomás, Král, Daniel, Lidický, Bernard, Nejedlý, Pavel, and Šámal, Robert

Subjects
*GRAPH theory, *MATHEMATICAL analysis, *ALGEBRAIC cycles, *LENGTH measurement, *SET theory, *CYCLIC permutations
Abstract

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 ≈ 1.619m, and every bridgeless graph with minimum degree three has a cycle cover of total length at most 44m/27 ≈ 1.630m. [ABSTRACT FROM AUTHOR]

Published
2010
Full Text
View/download PDF

4. A note about shortest cycle covers

Author

Shu, Jinlong and Zhang, Cun-Quan

Subjects
*GRAPH theory, *GRAPHIC methods, *COMBINATORICS, *ALGEBRA
Abstract

Abstract: Let G be a graph with odd edge-connectivity r. It is proved in this paper that if , then G has a 3-cycle -cover of total length at most . [Copyright &y& Elsevier]

Published
2005
Full Text
View/download PDF

5. On cubic bridgeless graphs whose edge-set cannot be covered by four perfect matchings

Author

Louis Esperet, Giuseppe Mazzuoccolo, Optimisation Combinatoire (G-SCOP_OC), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS), Università degli Studi di Modena e Reggio Emilia (UNIMORE), and ANR-10-JCJC-0204,HEREDIA,Classes héréditaires de graphes(2010)

Subjects
cubic graphs, 0102 computer and information sciences, Edge (geometry), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Combinatorics, Set (abstract data type), Berge-Fulkerson conjecture, perfect matchings, shortest cycle cover, snarks, Snark (graph theory), Computer Science::Discrete Mathematics, FOS: Mathematics, Mathematics - Combinatorics, 0101 mathematics, ComputingMilieux_MISCELLANEOUS, Mathematics, Conjecture, 010102 general mathematics, Berge-Fulkerson conjecture, cubic graphs, perfect matchings, shortest cycle cover, snarks, Girth (graph theory), Edge coloring, 05C15, 010201 computation theory & mathematics, Cubic graph, Cover (algebra), Combinatorics (math.CO)
Abstract

The problem of establishing the number of perfect matchings necessary to cover the edge-set of a cubic bridgeless graph is strictly related to a famous conjecture of Berge and Fulkerson. In this paper we prove that deciding whether this number is at most 4 for a given cubic bridgeless graph is NP-complete. We also construct an infinite family $\cal F$ of snarks (cyclically 4-edge-connected cubic graphs of girth at least five and chromatic index four) whose edge-set cannot be covered by 4 perfect matchings. Only two such graphs were known. It turns out that the family $\cal F$ also has interesting properties with respect to the shortest cycle cover problem. The shortest cycle cover of any cubic bridgeless graph with $m$ edges has length at least $\tfrac43m$, and we show that this inequality is strict for graphs of $\cal F$. We also construct the first known snark with no cycle cover of length less than $\tfrac43m+2$., Comment: 17 pages, 8 figures

Published
2013
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results