Article in volume
Authors:
Title:
Nowhere-zero unoriented 6-flows on certain triangular graphs
PDFSource:
Discussiones Mathematicae Graph Theory 42(3) (2022) 727-746
Received: 2019-01-02 , Revised: 2020-01-07 , Accepted: 2020-01-07 , Available online: 2020-06-29 , https://doi.org/10.7151/dmgt.2341
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 $\{\pm1, \ldots,
\pm(k - 1)\}$, for short we call it NZ-unoriented $k$-flow. Let $H_1$ and $H_2$
be two graphs, $H_1\oplus H_2$ denote the 2-sum of $H_1$ and $H_2$, if
$E(H_1\oplus H_2)=E(H_1)\cup E(H_2)$, $|V(H_1)\cap V(H_2)|=2$, and $|E(H_1)\cap
E(H_2)|=1$. A triangle-path in a graph $G$ is a sequence of distinct triangles
$T_1, T_2, \ldots, T_m$ in $G$ such that for $1\le i\le m$, $|E(T_i)\cap
E(T_{i+1})|=1$ and $E(T_i)\cap E(T_j)=\emptyset$ 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 $H_1,H_2,\ldots,H_t$ such that $G=H_1\oplus H_2
\oplus \cdots \oplus H_t$. In this paper, we prove that $G$ except a
triangle-star admits an NZ-unoriented $6$-flow. Moreover, if each $H_i$ 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
References:
- 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 - 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 - S. Akbari, A. Daemi, O. Hatami, A. Javanmard and A. Mehrabian, Nowhere-zero unoriented flows in Hamiltonian graphs, Ars Combin. 120 (2015) 51–63.
- 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 - 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 - M. DeVos, Flows in bidirected graphs, Mathematics 43 (2013) 95–115.
- 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 - 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.
- 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 - B. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms (Springer, Berlin, 2006).
https://doi.org/10.1007/3-540-29297-7 - 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 - 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 - O. Zyka, Nowhere-zero 30-flows on bidirected graphs, Thesis (Charles University, Praha, 1987).
- 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
Close