Shortest circuit covers of signed graphs

DOI10.1016/J.JCTB.2018.06.001MaRDI QIDQ1633748zbMATH OpenOpenAlexFDO

Authors You Lu, Jian Cheng, Rong Luo, Cun-Quan Zhang

Publication date 20 December 2018

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

Full work available at URL https://arxiv.org/abs/1510.05717

zbMATH Keywords

signed graphshortest circuit covergeneralized barbellnegativenesssigned circuit cover

Mathematics Subject Classification ID

Distance in graphs (05C12) Signed and weighted graphs (05C22)

Abstract: A shortest circuit cover $calF$ of a bridgeless graph $G$ is a family of circuits that covers every edge of $G$ and is of minimum total length. The total length of a shortest circuit cover $calF$ of $G$ is denoted by $SCC(G)$. For ordinary graphs (graphs without sign), the subject of shortest circuit cover is closely related to some mainstream areas, such as, Tutte's integer flow theory, circuit double cover conjecture, Fulkerson conjecture, and others. For signed graphs $G$, it is proved recently by M'av{c}ajov'a, Raspaud, Rollov'a and v{S}koviera that $SCC(G)leq11|E|$ if $G$ is s-bridgeless, and $SCC(G)leq9|E|$ if $G$ is $2$-edge-connected. In this paper this result is improved as follows, ${\displaystyle }$SCC(G) ~ leq ~ |E| + 3|V| +z${\displaystyle }$ where $z=minfrac23|E|+frac43epsilo{n}_N-7,|V|+2epsilo{n}_N-8$ and $epsilo{n}_N$ is the negativeness of $G$. The above upper bound can be further reduced if $G$ is $2$-edge-connected with even negativeness.

Recommendations

• Short signed circuit covers of signed graphs
• Shorter signed circuit covers of graphs
• Circuit covers of signed graphs
• Circuit \(k\)-covers of signed graphs
• scientific article; zbMATH DE number 3904620
• Circuit covers of signed Eulerian graphs
• Circuit covers of signed Eulerian graphs
• Signed circuit cover of bridgeless signed graphs
• Circuit covers of cubic signed graphs
• Shortest circuit covers of cubic graphs

Cites work

• scientific article; zbMATH DE number 3600081 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• Circuit covers of signed graphs
• Circular flow on signed graphs
• Covering Multigraphs by Simple Circuits
• Flows and generalized coloring theorems in graphs
• Fulkerson's conjecture and circuit covers
• Graph theory
• Graph theory
• Graphs with the Circuit Cover Property
• Minimum cycle coverings and integer flows
• Nowhere-zero 6-flows
• Nowhere-zero integral flows on a bidirected graph
• Proofs of two minimum circuit cover conjectures
• Short circuit covers for regular matroids with a nowhere zero 5-flow
• Short cycle covers and the cycle double cover conjecture
• Short cycle covers of cubic graphs
• Short cycle covers of graphs and nowhere-zero flows
• Shortest Circuit Covers and Postman Tours in Graphs with a Nowhere Zero 4
• Shortest circuit covers of cubic graphs
• Shortest coverings of graphs with cycles
• The 7/5‐conjecture strengthens itself

Cited in

(8)

• Short signed circuit covers of signed graphs
• Circuit covers of signed Eulerian graphs
• Signed circuit cover of bridgeless signed graphs
• Circuit covers of signed Eulerian graphs
• Circuit \(k\)-covers of signed graphs
• Flow polynomials of a signed graph
• A note on shortest sign-circuit cover of signed 3-edge-colorable cubic graphs
• Minimum \(T\)-joins and signed-circuit covering

This page was built for publication: Shortest circuit covers of signed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1633748)