Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
nowhere-zero $\lambda $-flow; minimum nowhere-zero flow number; join of two graphs
nowhere-zero $\lambda $-flow; minimum nowhere-zero flow number; join of two graphs
Summary:
Let $G$ be a graph, and $\lambda $ the smallest integer for which $G$ has a nowhere-zero $\lambda $-flow, i.e., an integer $\lambda $ for which $G$ admits a nowhere-zero $\lambda $-flow, but it does not admit a $(\lambda -1)$-flow. We denote the minimum flow number of $G$ by $\Lambda (G)$. In this paper we show that if $G$ and $H$ are two arbitrary graphs and $G$ has no isolated vertex, then $\Lambda (G \vee H) \leq 3$ except two cases: (i) One of the graphs $G$ and $H$ is $K_2$ and the other is $1$-regular. (ii) $H = K_1$ and $G$ is a graph with at least one isolated vertex or a component whose every block is an odd cycle. Among other results, we prove that for every two graphs $G$ and $H$ with at least $4$ vertices, $\Lambda (G \vee H) \leq 3$.
References:
[1] Jaeger, F.: Flows and generalized coloring theorems in graphs. J. Comb. Theory, Ser. B 26 (1979), 205-216. DOI 10.1016/0095-8956(79)90057-1 | MR 0532588 | Zbl 0422.05028
[2] Jaeger, F.: Nowhere-zero flow problems. Selected Topics in Graph Theory 3 Academic Press, San Diego 71-95 (1988). MR 1205397 | Zbl 0658.05034
[3] Luo, R., Zang, W., Zhang, C.: Nowhere-zero $4$-flows, simultaneous edge-colorings, and critical partial Latin squares. Combinatorica 24 (2004), 641-657. DOI 10.1007/s00493-004-0039-2 | MR 2096819 | Zbl 1070.05042
[4] Seymour, P. D.: Nowhere-zero $6$-flows. J. Comb. Theory, Ser. B 30 (1981), 130-135. DOI 10.1016/0095-8956(81)90058-7 | MR 0615308 | Zbl 0474.05028
[5] Shahmohamad, H.: On minimum flow number of graphs. Bull. Inst. Comb. Appl. 35 (2002), 26-36. MR 1901238 | Zbl 0990.05072
[6] Thomassen, C., Toft, B.: Non-separating induced cycles in graphs. J. Comb. Theory, Ser. B 31 (1981), 199-224. DOI 10.1016/S0095-8956(81)80025-1 | MR 0630983 | Zbl 0456.05039
[7] Tutte, W. T.: A contribution to the theory of chromatic polynomials. Can. J. Math. 6 (1954), 80-91. DOI 10.4153/CJM-1954-010-9 | MR 0061366 | Zbl 0055.17101
[8] Tutte, W. T.: On the imbedding of linear graphs in surfaces. Proc. Lond. Math. Soc., II. Ser. 51 (1949), 474-483. DOI 10.1112/plms/s2-51.6.474 | MR 0029495 | Zbl 0033.30803
[9] West, D. B.: Introduction to Graph Theory. Prentice Hall, Upper Saddle River (1996). MR 1367739 | Zbl 0845.05001
Search
Partner of
