Back to Search
Start Over
Spanning Triangle-trees and Flows of Graphs
- Publication Year :
- 2019
-
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$.<br />16 pages, 8 figures
- 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
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....4059179ede2f94a85df8420a86713ca7