Geodesic
Nowhere-Zero Unoriented 6-Flows on Certain Triangular Graphs
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 3, pp. 727-746.

Voir la notice de l'article provenant de la source Library of Science

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 gt;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 
@article{DMGT_2022_42_3_a2,
     author = {Yang, Fan and Li, Liangchen and Zhou, Sizhong},
     title = {Nowhere-Zero {Unoriented} {6-Flows} on {Certain} {Triangular} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {727--746},
     publisher = {mathdoc},
     volume = {42},
     number = {3},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a2/}
}
TY  - JOUR
AU  - Yang, Fan
AU  - Li, Liangchen
AU  - Zhou, Sizhong
TI  - Nowhere-Zero Unoriented 6-Flows on Certain Triangular Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 727
EP  - 746
VL  - 42
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a2/
LA  - en
ID  - DMGT_2022_42_3_a2
ER  - 
%0 Journal Article
%A Yang, Fan
%A Li, Liangchen
%A Zhou, Sizhong
%T Nowhere-Zero Unoriented 6-Flows on Certain Triangular Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 727-746
%V 42
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a2/
%G en
%F DMGT_2022_42_3_a2
Yang, Fan; Li, Liangchen; Zhou, Sizhong. Nowhere-Zero Unoriented 6-Flows on Certain Triangular Graphs. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 3, pp. 727-746. http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a2/

[1] S. Akbari, N. Ghareghani, G.B. Khosrovshahi and A. Mahmoody, On zero-sum 6- flows of graphs, Linear Algebra Appl. 430 (2009) 3047–3052. https://doi.org/10.1016/j.laa.2009.01.027

[2] S. Akbari, A. Daemi, O. Hatami, A. Javanmard and A. Mehrabian, Zero-sum flows in regular graphs, Graphs Combin. 26 (2010) 603–615. https://doi.org/10.1007/s00373-010-0946-5

[3] S. Akbari, A. Daemi, O. Hatami, A. Javanmard and A. Mehrabian, Nowhere-zero unoriented flows in Hamiltonian graphs, Ars Combin. 120 (2015) 51–63.

[4] S. Akbari, N. Ghareghani, G.B. Khosrovshahi and S. Zare, A note on zero-sum 5- flows in regular graphs, Electron. J. Combin. 19 (2012) #P7. https://doi.org/10.37236/2145

[5] A. Bouchet, Nowhere-zero integeral flows on a bidirected graph, J. Combin. Theory Ser. B 34 (1983) 279–292. https://doi.org/10.1016/0095-8956(83)90041-2

[6] M. DeVos, Flows in bidirected graphs, Mathematics 43 (2013) 95–115.

[7] J. Edmonds, Maximum matching and a polyhedron with 0, 1 -vertices, J. Res. Nat. Bur. Stand. 69B (1965) 125–130. https://doi.org/10.6028/jres.069B.013

[8] F. Jaeger, Nowhere-zero flow problems, in: Selected topics in Graph Theory 3, L.W. Beineke and R.J. Wilson (Ed(s)), (Academic Press, London, 1988) 70–95.

[9] M. Kano, Factors of regular graphs, J. Combin. Theory Ser. B 41 (1986) 27–36. https://doi.org/10.1016/0095-8956(86)90025-0

[10] B. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms (Springer, Berlin, 2006). https://doi.org/10.1007/3-540-29297-7

[11] A. Raspaud and X. Zhu, Circular flow on signed graphs, J. Combin. Theory Ser. B 101 (2011) 464–479. https://doi.org/10.1016/j.jctb.2011.02.007

[12] W.T. Tutte, On the imbedding of linear graphs in surfaces, Proc. Lond. Math. Soc. (2) 51 (1949) 474–483. https://doi.org/10.1112/plms/s2-51.6.474

[13] O. Zyka, Nowhere-zero 30-flows on bidirected graphs, Thesis (Charles University, Praha, 1987).

[14] F. Yang and X. Li, Zero-sum 6-flows in 5-regular graphs, Bull. Malays. Math. Sci. Soc. 42 (2019) 1319–1327. https://doi.org/10.1007/s40840-017-0547-z