Shortest coverings of graphs with cycles

DOI10.1016/0095-8956(83)90056-4zbMath0559.05037OpenAlexW1968068042MaRDI QIDQ802571

François Jaeger, Bill Jackson, Jean-Claude Bermond

Publication date: 1983

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://hal.inria.fr/hal-02447197/file/58-BJJ83-coveringcycles.pdf

zbMATH Keywords

cycles bridgeless graph edge covering

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Eulerian and Hamiltonian graphs (05C45)

Related Items

Covering Multigraphs by Simple Circuits, Idealness of k-wise Intersecting Families, Semi-duality and the cycle double cover conjecture, Shortest circuit covers of signed graphs, A cycle cover of a 2-edge-connected graph embedded with large face-width on an orientable surface, An overview of graph covering and partitioning, Characteristic flows on signed graphs and short circuit covers, A note on shortest cycle covers of cubic graphs, Extensions of flow theorems, The construction and reduction of strong snarks, Short cycle covers of cubic graphs, Smallest (1, 2)‐eulerian weight and shortest cycle covering, Supereulerian graphs and excluded induced minors, Circuit Covers of Signed Graphs, Shipper collaboration, On Cubic Bridgeless Graphs Whose Edge-Set Cannot be Covered by Four Perfect Matchings, Short circuit covers for regular matroids with a nowhere zero 5-flow, Circuit $k$-covers of signed graphs, A note on shortest sign-circuit cover of signed 3-edge-colorable cubic graphs, Short signed circuit covers of signed graphs, Berge–Fulkerson coloring for C(12)‐linked permutation graphs, On $d$-dimensional nowhere-zero $r$-flows on a graph, Lightweight paths in graphs, On the approximation ratio of the random Chinese postman tour for network search, Minimum $T$-Joins and Signed-Circuit Covering, Covering a graph with cycles., Short cycle covers of graphs with at most 77\% vertices of degree two, On bipartite restrictions of binary matroids, Circuit covers of signed Eulerian graphs, Signed circuit cover of bridgeless signed graphs, The lattice of cycles of an undirected graph, Signed cycle double covers, Integer flows and cycle covers, Integer 4-flows and cycle covers, Circuit decompositions and shortest circuit coverings of hypergraphs, Cubic Graphs with No Short Cycle Covers, Postman tours and cycle covers, Short cycle covers and the cycle double cover conjecture, A bound on the total size of a cut cover, Graphs with the Circuit Cover Property, Graph theory (algorithmic, algebraic, and metric problems), Edge-disjoint spanning trees and forests of graphs, Cycle double covers of infinite planar graphs, Berge-Fulkerson coloring for some families of superposition snarks, Short Cycle Covers of Cubic Graphs and Intersecting 5-Circuits, Projective, affine, and abelian colorings of cubic graphs, Group flow, complex flow, unit vector flow, and the $(2 + \epsilon)$-flow conjecture, Covering weighted graphs by even subgraphs, 1‐Factor and Cycle Covers of Cubic Graphs, Circuit Covers of Signed Eulerian Graphs, Short Cycle Covers on Cubic Graphs by Choosing a 2-Factor, Proofs of two minimum circuit cover conjectures, Short cycle covers of graphs and nowhere-zero flows, A note on Berge-Fulkerson coloring, Circuit Double Covers of Graphs, A note about shortest cycle covers, Cycle covering in bridgeless graphs, Nowhere zero flow and circuit covering in regular matroids, On shortest cocycle covers of graphs, Sharp bounds for the Chinese postman problem in 3-regular graphs and multigraphs, Idealness of $k$-wise intersecting families

Cites Work