Nowhere-zero 3-flows in matroid base graph

Abstract

The base graph of a simple matroid M=(E,ℬ) is the graph G such that V\left(G\right)=ℬ and E\left(G\right)=\{BB\prime :B,B\prime \in ℬ,|B\backslash B\prime |=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 Z₃-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 E_i (i≥2) of M, the matroid ase graph G_i of M_i = M|E_i has |V (G_i)|≥5, then G is Z₃-connected which also implies that G admits nowhere-zero 3-flow immediately.

Keywords

Matroid / base graph / nowhere-zero 3-flow / Z3-connectivity

References

[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

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

[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

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

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

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

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

[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

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

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

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

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

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

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg