| Title:
|
Join of two graphs admits a nowhere-zero $3$-flow (English) |
| Author:
|
Akbari, Saieed |
| Author:
|
Aliakbarpour, Maryam |
| Author:
|
Ghanbari, Naryam |
| Author:
|
Nategh, Emisa |
| Author:
|
Shahmohamad, Hossein |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
64 |
| Issue:
|
2 |
| Year:
|
2014 |
| Pages:
|
433-446 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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$. (English) |
| Keyword:
|
nowhere-zero $\lambda $-flow |
| Keyword:
|
minimum nowhere-zero flow number |
| Keyword:
|
join of two graphs |
| MSC:
|
05C20 |
| MSC:
|
05C21 |
| MSC:
|
05C78 |
| idZBL:
|
Zbl 06391503 |
| idMR:
|
MR3277745 |
| DOI:
|
10.1007/s10587-014-0110-0 |
| . |
| Date available:
|
2014-11-10T09:43:47Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/144007 |
| . |
| Reference:
|
[1] Jaeger, F.: Flows and generalized coloring theorems in graphs.J. Comb. Theory, Ser. B 26 (1979), 205-216. Zbl 0422.05028, MR 0532588, 10.1016/0095-8956(79)90057-1 |
| Reference:
|
[2] Jaeger, F.: Nowhere-zero flow problems.Selected Topics in Graph Theory 3 Academic Press, San Diego 71-95 (1988). Zbl 0658.05034, MR 1205397 |
| Reference:
|
[3] Luo, R., Zang, W., Zhang, C.: Nowhere-zero $4$-flows, simultaneous edge-colorings, and critical partial Latin squares.Combinatorica 24 (2004), 641-657. Zbl 1070.05042, MR 2096819, 10.1007/s00493-004-0039-2 |
| Reference:
|
[4] Seymour, P. D.: Nowhere-zero $6$-flows.J. Comb. Theory, Ser. B 30 (1981), 130-135. Zbl 0474.05028, MR 0615308, 10.1016/0095-8956(81)90058-7 |
| Reference:
|
[5] Shahmohamad, H.: On minimum flow number of graphs.Bull. Inst. Comb. Appl. 35 (2002), 26-36. Zbl 0990.05072, MR 1901238 |
| Reference:
|
[6] Thomassen, C., Toft, B.: Non-separating induced cycles in graphs.J. Comb. Theory, Ser. B 31 (1981), 199-224. Zbl 0456.05039, MR 0630983, 10.1016/S0095-8956(81)80025-1 |
| Reference:
|
[7] Tutte, W. T.: A contribution to the theory of chromatic polynomials.Can. J. Math. 6 (1954), 80-91. Zbl 0055.17101, MR 0061366, 10.4153/CJM-1954-010-9 |
| Reference:
|
[8] Tutte, W. T.: On the imbedding of linear graphs in surfaces.Proc. Lond. Math. Soc., II. Ser. 51 (1949), 474-483. Zbl 0033.30803, MR 0029495, 10.1112/plms/s2-51.6.474 |
| Reference:
|
[9] West, D. B.: Introduction to Graph Theory.Prentice Hall, Upper Saddle River (1996). Zbl 0845.05001, MR 1367739 |
| . |
