Signed Circuit Cover of Bridgeless Signed Graphs
- PDF / 658,741 Bytes
- 21 Pages / 439.37 x 666.142 pts Page_size
- 28 Downloads / 232 Views
(0123456789().,-volV)(0123456789().,-volV)
ORIGINAL PAPER
Signed Circuit Cover of Bridgeless Signed Graphs Mengmeng Xie1 • Chuixiang Zhou2 Received: 4 March 2019 / Revised: 7 February 2020 Ó Springer Japan KK, part of Springer Nature 2020
Abstract Let ðG; rÞ be a 2-edge-connected flow-admissible signed graph. In this paper, we prove that ðG; rÞ has a signed circuit cover with length at most 3|E(G)|. Keywords Signed graph Flow-admissible Signed circuit cover
Mathematics Subject Classification 05C35 05C75
1 Introduction All graphs in this paper may have multiple edges and loops. A loop is also treated as an edge. We follow the notation from the book [17]. A circuit is a connected 2-regular graph, which is a minimal dependent set of the graphic matroid defined on G. A graph is even, if every vertex has even degree. An Eulerian graph is a connected even graph. A circuit cover F of a graph is a family of circuits which covers all edges of G. The length of a circuit is the number of its edges. The length of a circuit cover is the total length of all elements of it, denoted by ‘ðF Þ. The shortest length of a circuit cover of a graph G is denoted by scc(G). A well known conjecture, the Shortest Cycle Cover Conjecture, was proposed by Alon and Tarsi [1] as follows. Conjecture 1.1 (Alon and Tarsi [1]) Let G be a 2-edge-connected graph. Then sccðGÞ 75 jEðGÞj.
This research is supported by NSFC (11971110,11671087). & Chuixiang Zhou [email protected] 1
School of Mathematics and Statistics, Ningbo University, Ningbo 315211, China
2
Center for Discrete Mathematics, Fuzhou University, Fujian 350003, China
123
Graphs and Combinatorics
Jamshy and Tarsi [7] proved that Conjecture 1.1 implies the well-known Cycle Double Cover Conjecture proposed by Seymour [12] and Szekeres [13]. The best known result about Conjecture 1.1 is the following theorem obtained by Bermond, Jackson, Jaeger [2] and Alon, Tarsi [1],independently. Theorem 1.2 (Bermond et al. [2], Alon and Tarsi [1]) Let G be a 2-edge-connected graph. Then sccðGÞ 53 jEðGÞj. Itai and Rodeh [8] conjectured that sccðGÞ jEðGÞj þ jVðGÞj 1 for 2-edgeconnected graph G, which was confirmed by Fan [6]. Theorem 1.3 (Fan [6]) Let sccðGÞ jEðGÞj þ jVðGÞj 1.
G
be
a
2-edge-connected
graph.
Then
A signed graph ðG; rÞ is a graph G associated with a signature r : EðGÞ ! fþ1; 1g. An edge e 2 EðGÞ is positive if rðeÞ ¼ 1 and negative if rðeÞ ¼ 1. For a signed graph ðG; rÞ, E ðG; rÞ (resp. Eþ ðG; rÞ) denotes the set of all negative (resp. positive) edges. If no confusion is caused, we use E and Eþ to denote E ðG; rÞ and Eþ ðG; rÞ, respectively. Let G0 be a subgraph of G, the signature of G0 is defined to be rðG0 Þ ¼ Pe2EðG0 Þ rðeÞ. A circuit C of G is balanced if rðCÞ ¼ 1, and unbalanced if rðCÞ ¼ 1. A short barbell of a signed graph consists of two unbalanced circuits with exact one common vertex, and a long barbell of a signed graph consists of two vertex disjoint unbalanced circuits joined by a path P which is internally disjoint with the two unbalanced
Data Loading...
