Flow number of signed Halin graphs

Xiao Wang, You Lu, Shenggui Zhang

Research output: Contribution to journalArticlepeer-review

Abstract

The flow number of a signed graph (G,Σ) is the smallest positive integer k such that (G,Σ) admits a nowhere-zero integer k-flow. In 1983, Bouchet (JCTB) conjectured that every flow-admissible signed graph has flow number at most 6. This conjecture remains open for general signed graphs even for signed planar graphs. A Halin graph is a plane graph consisting of a tree without vertices of degree two and a circuit connecting all leaves of the tree. In this paper, we prove that every flow-admissible signed Halin graph has flow number at most 5, and determine the flow numbers of signed Halin graphs with a (3,1)-caterpillar tree as its characteristic tree.

Original languageEnglish
Article number125751
JournalApplied Mathematics and Computation
Volume393
DOIs
StatePublished - 15 Mar 2021

Keywords

  • Flow number
  • Halin graph
  • Nowhere-zero integer flow
  • Signed graph

Fingerprint

Dive into the research topics of 'Flow number of signed Halin graphs'. Together they form a unique fingerprint.

Cite this