2023/10/20 by Liangchen Li, Li, Liangchen, Chong Li +5
Computer Science · Mathematics · #05C15 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2310.13504
openalex publication_date 2023/10/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A triangle-path in a graph G is a sequence of distinct triangles T1,T2,…,Tm in G such that for any i, j with 1≤ i < j ≤ m, |E(Ti)∩ E(Ti+1)|=1 and E(Ti)∩ E(Tj)=∅ if j > i+1. A connected graph G is triangularly connected if for any two nonparallel edges e and e' there is a triangle-path T1T2⋯ Tm such that e∈ E(T1) and e'∈ E(Tm). For ordinary graphs, Fan \it et al.~(J. Combin. Theory Ser. B 98 (2008) 1325-1336) characterize all triangularly connected graphs that admit nowhere-zero 3-flows or 4-flows. Corollaries of this result include integer flow of some families of ordinary graphs, such as, locally connected graphs due to Lai (J. Graph Theory 42 (2003) 211-219) and some types of products of graphs due to Imrich et al.(J. Graph Theory 64 (2010) 267-276). In this paper, Fan's result for triangularly connected graphs is further extended to signed graphs. We proved that every flow-admissible triangularly connected signed graph admits a nowhere-zero 4-flow if and only if it is not the wheel W5 associated with a specific signature. Moreover, this result is sharp since there are infinitely many unbalanced triangularly connected signed graphs admitting a nowhere-zero 4-flow but not 3-flow.