Flow number of signed Halin graphs
作者：
Highlights：
• Bouchet [Nowhere-zero integral flows on a bidirected graph, J. Combin. Theory Ser. B., 34 (3) (1983): 279–292.] conjectured that every flow-admissible signed graph has flow number at most 6. This conjecture has been the mainstream problem of integer flows of signed graphs, and is still widely open. We show that every flow-admissible signed Halin graph has flow number at most 5, and thus confirm Bouchet’s conjecture for signed Halin graphs.
• We determine the flow numbers of signed Halin graphs with a (3,1)-caterpillar tree as its characteristic tree.
• We introduce a tool of shrinking a triangle into a vertex. This tool plays an important role in the proof of this paper and might be useful for other problems related to flows on signed graphs.
摘要
•Bouchet [Nowhere-zero integral flows on a bidirected graph, J. Combin. Theory Ser. B., 34 (3) (1983): 279–292.] conjectured that every flow-admissible signed graph has flow number at most 6. This conjecture has been the mainstream problem of integer flows of signed graphs, and is still widely open. We show that every flow-admissible signed Halin graph has flow number at most 5, and thus confirm Bouchet’s conjecture for signed Halin graphs.•We determine the flow numbers of signed Halin graphs with a (3,1)-caterpillar tree as its characteristic tree.•We introduce a tool of shrinking a triangle into a vertex. This tool plays an important role in the proof of this paper and might be useful for other problems related to flows on signed graphs.
论文关键词：Nowhere-zero integer flow,Flow number,Signed graph,Halin graph
论文评审过程：Received 15 July 2020, Revised 12 October 2020, Accepted 19 October 2020, Available online 4 November 2020, Version of Record 4 November 2020.
论文官网地址：https://doi.org/10.1016/j.amc.2020.125751
