Shortest circuit covers of signed graphs

DOI10.1016/J.JCTB.2018.06.001zbMATH Open1402.05095arXiv1510.05717OpenAlexW2963140626MaRDI QIDQ1633748FDOQ1633748

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)

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.

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

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

zbMATH Keywords

signed graphshortest circuit covergeneralized barbellnegativenesssigned circuit cover

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (8)

• Short signed circuit covers of signed graphs
• Circuit covers of signed Eulerian graphs
• Circuit covers of signed Eulerian graphs
• Signed circuit cover of bridgeless signed 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)