Premium
The Set of Circular Flow Numbers of Regular Graphs
Author(s) -
Schubert Michael,
Steffen Eckhard
Publication year - 2014
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21766
Subject(s) - mathematics , combinatorics , indifference graph , chordal graph , maximal independent set , discrete mathematics , interval (graph theory) , pathwidth , flow (mathematics) , 1 planar graph , graph , line graph , geometry
This article determines the set of the circular flow numbers of regular graphs. LetF c be the set of the circular flow numbers of graphs, andF d c be the set of the circular flow numbers of d ‐regular graphs. If d is even, thenF d c = { 2 } . For d = 2 k + 1( k ≥ 1 ) it is known [6][E. Steffen, 2001] thatF 2 k + 1 c ∩ ( 2 + 1 k , 2 + 2 2 k − 1 ) = ∅ . We show thatF 2 k + 1 c = ( F c − [ 2 , 2 + 2 2 k − 1 ) ) ∪ { 2 + 1 k } . Hence, the interval ( 2 + 1 k , 2 + 2 2 k − 1 ) is the only gap for circular flow numbers of ( 2 k + 1 ) ‐regular graphs between 2 + 1 kand 5. Furthermore, if Tutte's 5‐flow conjecture is false, then it follows, that gaps for circular flow numbers of graphs in the interval [5, 6] are due for all graphs not just for regular graphs.