Nowhere-Zero Unoriented 6-Flows on Certain Triangular Graphs

Abstract

A nowhere-zero unoriented flow of graph G is an assignment of non-zero real numbers to the edges of G such that the sum of the values of all edges incident with each vertex is zero. Let k be a natural number. A nowhere-zero unoriented k-flow is a flow with values from the set {±1, . . ., ±(k − 1)}, for short we call it NZ-unoriented k-flow. Let H1 and H2 be two graphs, H1 ⊕H2 denote the 2-sum of H1 and H2, if E(H1 ⊕ H2) = E(H1) ∪ E(H2), |V (H1)∩V (H2)| = 2, and |E(H1)∩E(H2)| = 1. A triangle-path in a graph G is a sequence of distinct triangles T1, T2, . . ., Tm in G such that for 1 ≤ i ≤ m, |E(Ti) ∩ E(Ti+1)| = 1 and E(Ti) ∩ E(Tj) = ∅ if j > i + 1. A triangle-star is a graph with triangles such that each triangle having one common edges with other triangles. Let G be a graph which can be partitioned into some triangle-paths or wheels H1, H2, . . ., Ht such that G = H1 ⊕H2 ⊕ ⊕Ht. In this paper, we prove that G except a triangle-star admits an NZ-unoriented 6-flow. Moreover, if each Hi is a triangle-path, then G except a triangle-star admits an NZ-unoriented 5-flow.

Keywords

• nowhere-zero k-flow
• triangle-tree
• triangle-star
• bidirected graph
• 05c21