Frontiers of Mathematics in China >

2013 , Vol. 8 >Issue 1: 217 - 227

DOI: https://doi.org/10.1007/s11464-012-0246-x

RESEARCH ARTICLE

Nowhere-zero 3-flows in matroid base graph

  • Yinghao ZHANG ,
  • Guizhen LIU
Expand
  • School of Mathematics, Shandong University, Jinan 250100, China

Received date: 22 Oct 2010

Accepted date: 16 Sep 2012

Published date: 01 Feb 2013

Copyright

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg
Fold

Abstract

The base graph of a simple matroid M=(E,ℬ) is the graph G such that V(G)=ℬ and E(G)={BB′:B,B′∈ℬ,|B\B′|=1}, where the same notation is used for the vertices of G and the bases of M. It is proved that the base graph G of connectedsimple matroid M is Z3-connected if |V (G)|≥5. We also proved that if M is not a connected simple matroid, then the base graph G of M does not admit a nowhere-zero 3-flow if and only if |V (G)| = 4. Furthermore, if for every connected component Ei (i≥2) of M, the matroid ase graph Gi of Mi = M|Ei has |V (Gi)|≥5, then G is Z3-connected which also implies that G admits nowhere-zero 3-flow immediately.

Key words： Matroid; base graph; nowhere-zero 3-flow; Z3-connectivity

Cite this article

Yinghao ZHANG , Guizhen LIU . Nowhere-zero 3-flows in matroid base graph[J]. Frontiers of Mathematics in China, 2013 , 8(1) : 217 -227 . DOI: 10.1007/s11464-012-0246-x

References

Publishing order | Descend order by publishing year | Descend order by cited within
1
Bondy J A, Murty U S R. Graph Theory with Application. New York: North-Holland, 1976

2
Cummins R L. Hamiltonian circuits in tree graph. IEEE Trans Circuits Syst, 1966, 13: 82-90

3
Fan G, Lai H, Xu R, Zhang C, Zhou C. Nowhere-zero 3-flows in triangularly connected graphs. J Combin Theory Ser B, 2008, 98: 1325-1336

DOI

4
Jaeger F. Flows and generalized coloring theorem in graphs. J Combin Theory Ser B, 1979, 26: 205-216

DOI

5
Jaeger F, Linial N, Payan C, Tarsi M. Group connectivity of graphs—a nonhomogeneous analogue of nowhere-zero flow properties. J Combin Theory Ser B, 1992, 56: 165-182

DOI

6
Lai H. Group connectivity of 3-edge-connected chordal graphs. Graphs Combin, 2000, 16: 165-176

DOI

7
Lai H. Nowhere-zero 3-flows in locally connected graphs. J Graph Theory, 2003, 42: 211-219

DOI

8
Liu G. A lower bound on connectivities of matroid base graphs. Discrete Math, 1988, 64: 55-66

DOI

9
Liu G, Li P. Paths in circuit graphs of matroid. Theoret Comput Sci, 2008, 396: 258-263

DOI

10
Oxley J G. Matroid Theory. New York: Oxford University Press, 1992

11
Potocnik P, Skoviera M, Skrekovski R. Nowhere-zero 3-flows in abelian Cayley graphs. Discrete Math, 2005, 297: 119-127

DOI

12
Seymour P D. Nowhere-zero 6-flows. J Combin Theory Ser B, 1981, 30: 82-94

DOI

13
Shu J, Zhang C. Nowhere-zero 3-flows in products of graphs. J Graph Theory, 2005, 50: 79-89

DOI

14
Tutte W T. A contribution on the theory of chromatic polynomial. Canad J Math, 1954, 6: 80-91

DOI

15
Tutte W T. On the algebraic theory of graph colorings. J Combin Theory, 1966, 1: 15-50

DOI

16
Zhang C. Integer Flows and Cycle Covers of Graphs. New York: Marcel Dekker, 1997

Options
Outlines

/

〈 〉