Shortest circuit covers of signed graphs
Shortest circuit covers of signed graphs
复制标题
DOI：
10.1016/j.jctb.2018.06.001
复制
发表时间：
2015-10
期刊：
影响因子：
--
通讯作者：
You Lu;Jian Cheng;Rong Luo;Cun-Quan Zhang
中科院分区：
文献类型：
--
作者：
You Lu;Jian Cheng;Rong Luo;Cun-Quan Zhang
无桥图G的最短路覆盖F是覆盖G的每条边且总长度最小的路族。G的最短路覆盖F的总长度记为SC C（G）。对于普通图（无符号图），最短路覆盖问题与Tutte的整数流理论、路双覆盖猜想、Fulkerson猜想等主流领域密切相关。对于符号图G，最近由Máčajová，Raspaud，Rollová和Škoviera证明了S C C（G）≤ 11| e|若G是无s桥的，且SC C（G）≤ 9| e|如果G是2-边连通的。本文改进了这一结果，S C C（G）≤| e| +3个|v| + z其中z = min {2 3| e| +4 3 N − 7，|v| + 2 $> N-8}且$> N是G的负值。当G是2-边连通的偶负图时，上述上界可进一步减小。
A shortest circuit cover F 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 F of G is denoted by S C C (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áčajová, Raspaud, Rollová and Škoviera that S C C (G)≤ 11| E| if G is s-bridgeless, and S C C (G)≤ 9| E| if G is 2-edge-connected. In this paper this result is improved as follows, S C C (G)≤| E|+ 3| V|+ z where z= min{2 3| E|+ 4 3 ϵ N− 7,| V|+ 2 ϵ N− 8} and ϵ N is the negativeness of G. The above upper bound can be further reduced if G is 2-edge-connected with even negativeness.