×

Circular flow numbers of regular multigraphs. (English) Zbl 0982.05060

Author’s abstract: The circular flow number \(F_c(G)\) of a graph \(G= (V,E)\) is the minimum \(r\in Q\) such that \(G\) admits a flow \(\phi\) with \(1\leq \phi(e)\leq r-1\), for each \(e\in E\). We determine the circular flow number of some regular multigraphs. In particular, we characterize the bipartite \((2t+1)\)-regular graphs \((t\geq 1)\). Our results imply that there are gaps for possible circular flow numbers for \((2t+1)\)-regular graphs, e.g., there is no cubic graph \(G\) with \(3< F_c(G)< 4\). We further show that there are snarks with circular flow number arbitrarily close to 4, answering a question of X. Zhu.
Reviewer: C.Lai (Zhangzhou)

MSC:

05C35 Extremal problems in graph theory
05C75 Structural characterization of families of graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bondy, Congressus Numerantium XIV pp 109– (1975)
[2] Graphentheorie, Springer-Verlag, Berlin, Heidelberg, 1996. · doi:10.1007/978-3-662-07551-7
[3] A. Goddyn, J Graph Theory 28 pp 155– (1998) · Zbl 0922.05027 · doi:10.1002/(SICI)1097-0118(199807)28:3<155::AID-JGT5>3.0.CO;2-J
[4] Isaacs, Am Math Monthly 82 pp 221– (1975) · Zbl 0311.05109 · doi:10.2307/2319844
[5] Jaeger, Proc Am Math Soc 55 pp 237– (1975) · doi:10.1090/S0002-9939-1976-0427156-5
[6] Jaeger, J Comb Theory Ser (B) 26 pp 205– (1979) · Zbl 0422.05028 · doi:10.1016/0095-8956(79)90057-1
[7] On circular flows in graphs, finite and infinite sets, Vol. I, II (Eger, 1981), Colloq Math Soc Janós Bolyai 37, North-Holland, Amsterdam-New-York, 1984, pp. 391-402.
[8] ?Nowhere-zero flow problems,? Topics in graph theory 3, (Editors), Academic Press, London, 1988, pp. 70-95.
[9] Meredith, J Comb Theory Ser B 14 pp 55– (1973) · Zbl 0237.05106 · doi:10.1016/S0095-8956(73)80006-1
[10] Seymour, J Comb Theory Ser B 30 pp 130– (1981) · Zbl 0474.05028 · doi:10.1016/0095-8956(81)90058-7
[11] ?Nowhere-zero flows,? (Editors), Handbook of combinatorics, Elsevier Science B.V., Amsterdam, 1995, 289-299.
[12] Steffen, J Graph Theory 22 pp 309– (1996) · Zbl 0857.05022 · doi:10.1002/(SICI)1097-0118(199608)22:4<309::AID-JGT5>3.0.CO;2-P
[13] Tutte, Proc London Math Soc Ser 2 51 pp 474– (1949) · Zbl 0033.30803 · doi:10.1112/plms/s2-51.6.474
[14] Tutte, Can J Math 6 pp 80– (1954) · Zbl 0055.17101 · doi:10.4153/CJM-1954-010-9
[15] Integer flows and cycle covers of graphs, Marcel Dekker, New York, Basel, Hong Kong, 1997.
[16] Planar graphs with circular chromatic number between 3 and 4 manuscript, 1997.
[17] Circular chromatic number: a survey, manuscript, 1998.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.