Nowhere-zero 3-flows in matroid base graph

Abstract

The base graph of a simple matroid M = (E,B) is the graph G such that V (G) = B and E(G) = {BB′: B,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 connected simple 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 base 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 / Z₃-connectivity

References

[1] Bondy J. A., Murty U. S. R.. Graph Theory with Application, 1976, New York: North-Holland

[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, 1992, New York: Oxford University Press

[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, 1997, New York: Marcel Dekker