Spanning Triangle-Trees and Flows of Graphs
- PDF / 607,671 Bytes
- 18 Pages / 439.37 x 666.142 pts Page_size
- 87 Downloads / 233 Views
(0123456789().,-volV)(0123456789().,-volV)
ORIGINAL PAPER
Spanning Triangle-Trees and Flows of Graphs Jiaao Li1 • Xueliang Li2 • Meiling Wang2 Received: 11 October 2019 / Revised: 4 June 2020 Ó Springer Japan KK, part of Springer Nature 2020
Abstract In this paper we study the flow properties of graphs containing a spanning triangletree. Our main results provide a structure characterization of graphs with a spanning triangle-tree admitting a nowhere-zero 3-flow. All these graphs without nowherezero 3-flows are constructed from K4 by a so-called bull-growth operation. This generalizes a result of Fan et al. in 2008 on triangularly-connected graphs and particularly shows that every 4-edge-connected graph with a spanning triangle-tree has a nowhere-zero 3-flow. A well-known classical theorem of Jaeger in 1979 shows that every graph with two edge-disjoint spanning trees admits a nowhere-zero 4-flow. We prove that every graph with two edge-disjoint spanning triangle-trees has a flow strictly less than 3. Keywords Nowhere-zero flow 3-Flow flow index Triangularly-connected Triangle-tree 2-Tree
Mathematics Subject Classification 05C21 05C40 05C05
1 Introduction We shall introduce some necessary notation and terminology and the concepts of 3-flows, circular flows and group connectivity in the next subsections. & Xueliang Li [email protected] Jiaao Li [email protected] Meiling Wang [email protected] 1
School of Mathematical Sciences and LPMC, Nankai University, Tianjin 300071, China
2
Center for Combinatorics and LPMC, Nankai University, Tianjin 300071, China
123
Graphs and Combinatorics
1.1 Nowhere-Zero 3-Flows Graphs considered here may contain parallel edges, but no loops. We follow the textbook [3] for undefined terminology and notation. For a graph G, we use V(G) and E(G) to denote the vertex set and edge set of G, respectively. When S is an edge subset of E(G) or a vertex subset of V(G), we use G[S] to denote the edge-induced subgraph or the vertex-induced subgraph from S. For a vertex u 2 VðGÞ, dG ðuÞ denotes the degree of u in G. Sometimes the subscript is omitted for convenience. We call u a k-vertex (kþ -vertex, resp.) if dðuÞ ¼ k (dðuÞ k, resp.). A k-cut is an edge-cut of size k. Let D be an orientation of G. The set of outgoing arcs incident to u is denoted by EDþ ðuÞ, while the set of incoming arcs is denoted by ED ðuÞ. We use dDþ ðuÞ ¼ jEDþ ðuÞj and dD ðuÞ ¼ jED ðuÞj to denote the out-degree and in-degree of u, respectively. D and a function f from E(G) to f1; 2; . . .; ðk 1Þg, if P P Given an orientation f ðeÞ ¼ þ e2ED ðvÞ e2ED ðvÞ f ðeÞ for each vertex v 2 VðGÞ, then we call (D, f) a nowhere-zero k-flow, abbreviated as k-NZF. The flow theory was initiated by Tutte [21], generalizing face-colorings of plane graphs to flows of arbitrary graphs by duality. Tutte proposed the well-known 3-flow conjecture, which was selected by Bondy among the Beautiful Conjectures in Graph Theory [2] with high evaluation. Conjecture 1.1 (Tutte’s 3-flow conjecture) Every 4-edge-connected g
Data Loading...
