1. Spanning Triangle-trees and Flows of Graphs
- Author
-
Jiaao Li, Xueliang Li, and Meiling Wang
- Subjects
Spanning tree ,0211 other engineering and technologies ,021107 urban & regional planning ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Graph ,Theoretical Computer Science ,Combinatorics ,010201 computation theory & mathematics ,FOS: Mathematics ,Discrete Mathematics and Combinatorics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,Flow properties ,Classical theorem ,05C21, 05C40, 05C05 ,Mathematics - Abstract
In this paper we study the flow-property of graphs containing a spanning triangle-tree. Our main results provide a structure characterization of graphs with a spanning triangle-tree admitting a nowhere-zero $3$-flow. All these graphs without nowhere-zero $3$-flows are constructed from $K_4$ by a so-called bull-growing 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$., 16 pages, 8 figures
- Published
- 2019