Nowhere-zero 3-flows in matroid base graph

doi:10.1007/s11464-012-0246-x

Front Math Chin

2013, Vol. 8

Issue (1) : 217-227 https://doi.org/10.1007/s11464-012-0246-x

RESEARCH ARTICLE

Nowhere-zero 3-flows in matroid base graph

Yinghao ZHANG, Guizhen LIU(

)

School of Mathematics, Shandong University, Jinan 250100, China

Download: PDF(117 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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 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

Corresponding Author(s): LIU Guizhen,Email:gzliu@sdu.edu.cn

Issue Date: 01 February 2013

Cite this article:

Yinghao ZHANG,Guizhen LIU. Nowhere-zero 3-flows in matroid base graph[J]. Front Math Chin, 2013, 8(1): 217-227.

URL:

https://academic.hep.com.cn/fmc/EN/10.1007/s11464-012-0246-x
https://academic.hep.com.cn/fmc/EN/Y2013/V8/I1/217

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: 10.1016/j.jctb.2008.02.008
4	Jaeger F. Flows and generalized coloring theorem in graphs. J Combin Theory Ser B , 1979, 26: 205-216 doi: 10.1016/0095-8956(79)90057-1
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: 10.1016/0095-8956(92)90016-Q
6	Lai H. Group connectivity of 3-edge-connected chordal graphs. Graphs Combin , 2000, 16: 165-176 doi: 10.1007/s003730050014
7	Lai H. Nowhere-zero 3-flows in locally connected graphs. J Graph Theory , 2003, 42: 211-219 doi: 10.1002/jgt.10085
8	Liu G. A lower bound on connectivities of matroid base graphs. Discrete Math , 1988, 64: 55-66 doi: 10.1016/0012-365X(88)90177-X
9	Liu G, Li P. Paths in circuit graphs of matroid. Theoret Comput Sci , 2008, 396: 258-263 doi: 10.1016/j.tcs.2008.01.033
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: 10.1016/j.disc.2005.04.013
12	Seymour P D. Nowhere-zero 6-flows. J Combin Theory Ser B , 1981, 30: 82-94 doi: 10.1016/S0095-8956(81)80013-5
13	Shu J, Zhang C. Nowhere-zero 3-flows in products of graphs. J Graph Theory , 2005, 50: 79-89 doi: 10.1002/jgt.20095
14	Tutte W T. A contribution on the theory of chromatic polynomial. Canad J Math , 1954, 6: 80-91 doi: 10.4153/CJM-1954-010-9
15	Tutte W T. On the algebraic theory of graph colorings. J Combin Theory , 1966, 1: 15-50 doi: 10.1016/S0021-9800(66)80004-2
16	Zhang C. Integer Flows and Cycle Covers of Graphs. New York: Marcel Dekker, 1997

[1]	Ziwen HUANG,Xiangwen LI. Degree sum of a pair of independent edges and Z₃-connectivity[J]. Front. Math. China, 2016, 11(6): 1533-1567.
[2]	Liangchen LI,Xiangwen LI. Nowhere-zero 3-flows in Cayley graphs on generalized dihedral group and generalized quaternion group[J]. Front. Math. China, 2015, 10(2): 293-302.
[3]	Hao FAN, Guizhen LIU. Properties of Hamilton cycles of circuit graphs of matroids[J]. Front Math Chin, 2013, 8(4): 801-809.
[4]	Erling WEI, Wenliang TANG, Xiaofeng WANG. Flows in 3-edge-connected bidirected graphs[J]. Front Math Chin, 2011, 6(2): 339-348.

Viewed

Full text

Abstract

Cited

Shared

Discussed