| Title:
|
Flows on the join of two graphs (English) |
| Author:
|
Lukoťka, Robert |
| Author:
|
Rollová, Edita |
| Language:
|
English |
| Journal:
|
Mathematica Bohemica |
| ISSN:
|
0862-7959 (print) |
| ISSN:
|
2464-7136 (online) |
| Volume:
|
138 |
| Issue:
|
4 |
| Year:
|
2013 |
| Pages:
|
383-396 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
The join of two graphs $G$ and $H$ is a graph formed from disjoint copies of $G$ and $H$ by connecting each vertex of $G$ to each vertex of $H$. We determine the flow number of the resulting graph. More precisely, we prove that the join of two graphs admits a nowhere-zero $3$-flow except for a few classes of graphs: a single vertex joined with a graph containing an isolated vertex or an odd circuit tree component, a single edge joined with a graph containing only isolated edges, a single edge plus an isolated vertex joined with a graph containing only isolated vertices, and two isolated vertices joined with exactly one isolated vertex plus some number of isolated edges. (English) |
| Keyword:
|
nowhere-zero flow |
| Keyword:
|
graph join |
| MSC:
|
05C21 |
| idZBL:
|
Zbl 06260039 |
| idMR:
|
MR3231093 |
| DOI:
|
10.21136/MB.2013.143511 |
| . |
| Date available:
|
2013-11-09T20:24:23Z |
| Last updated:
|
2020-07-29 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/143511 |
| . |
| Reference:
|
[1] Bondy, J. A., Murty, U. S. R.: Graph Theory.Graduate Texts in Mathematics 244 Springer, Berlin (2008). Zbl 1134.05001, MR 2368647, 10.1007/978-1-84628-970-5_1 |
| Reference:
|
[2] Chen, J. J., Eschen, E., Lai, H.-J.: Group connectivity of certain graphs.Ars Comb. 89 (2008), 141-158. Zbl 1224.05267, MR 2456240 |
| Reference:
|
[3] Diestel, R.: Graph Theory.Third ed. Graduate Texts in Mathematics 173 Springer, Berlin (2005). Zbl 1074.05001, MR 2159259 |
| Reference:
|
[4] Fan, G., Lai, H., Xu, R., Zhang, C.-Q., Zhou, Ch.: Nowhere-zero $3$-flows in triangularly connected graphs.J. Comb. Theory, Ser. B 98 (2008), 1325-1336. Zbl 1171.05026, MR 2462322, 10.1016/j.jctb.2008.02.008 |
| Reference:
|
[5] Imrich, W., Peterin, I., Špacarpan, S., Zhang, C.-Q.: NZ-flows in strong products of graphs.J. Graph Theory 64 (2010), 267-276. MR 2668543 |
| Reference:
|
[6] Imrich, W., Škrekovski, R.: A theorem on integer flows on Cartesian products of graphs.J. Graph Theory 43 (2003), 93-98. Zbl 1019.05058, MR 1978114, 10.1002/jgt.10100 |
| Reference:
|
[7] Jaeger, F.: Nowhere-zero flow problems.L. W. Beineke, R. J. Wilson Selected Topics in Graph Theory 3 Academic Press, San Diego, CA (1988), 71-95. Zbl 0658.05034, MR 1205397 |
| Reference:
|
[8] Jaeger, F., Linial, N., Payan, C., Tarsi, M.: Group connectivity of graphs---a nonhomogeneous analogue of nowhere-zero flow properties.J. Comb. Theory, Ser. B 56 (1992), 165-182. Zbl 0824.05043, MR 1186753, 10.1016/0095-8956(92)90016-Q |
| Reference:
|
[9] Kochol, M.: Smallest counterexample to the 5-flow conjecture has girth at least eleven.J. Comb. Theory, Ser. B 100 (2010), 381-389. Zbl 1211.05055, MR 2644241, 10.1016/j.jctb.2009.12.001 |
| Reference:
|
[10] Nánásiová, M., Škoviera, M.: Nowhere-zero $3$-flows in Cayley graphs and Sylow $2$-subgroups.J. Algebr. Comb. 30 (2009), 103-111. Zbl 1208.05053, MR 2519851, 10.1007/s10801-008-0153-0 |
| Reference:
|
[11] Robertson, N., Seymour, P., Thomas, R.: Tutte's edge-colouring conjecture.J. Comb. Theory, Ser. B 70 (1997), 166-183. Zbl 0883.05055, MR 1441265, 10.1006/jctb.1997.1752 |
| Reference:
|
[12] Rollová, E., Škoviera, M.: Nowhere-zero flows in Cartesian bundles of graphs.Eur. J. Comb. 33 (2012), 867-871. Zbl 1293.05325, MR 2889520, 10.1016/j.ejc.2011.09.022 |
| Reference:
|
[13] 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:
|
[14] Shahmohamad, H.: On minimum flow number of graphs.Bull. Inst. Comb. Appl. 35 (2002), 26-36. Zbl 0990.05072, MR 1901238 |
| Reference:
|
[15] Shu, J., Zhang, C.-Q.: Nowhere-zero $3$-flows in products of graphs.J. Graph Theory 50 (2005), 79-89. Zbl 1069.05040, MR 2157539, 10.1002/jgt.20095 |
| Reference:
|
[16] Steffen, E.: Circular flow numbers of regular multigraphs.J. Graph Theory 36 (2001), 24-34. Zbl 0982.05060, MR 1803631, 10.1002/1097-0118(200101)36:1<24::AID-JGT3>3.0.CO;2-Q |
| Reference:
|
[17] Thomassen, C.: The weak $3$-flow conjecture and the weak circular flow conjecture.J. Comb. Theory, Ser. B 102 (2012), 521-529. Zbl 1239.05083, MR 2885433, 10.1016/j.jctb.2011.09.003 |
| Reference:
|
[18] 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:
|
[19] Xu, R., Zhang, C.-Q.: Nowhere-zero $3$-flows in squares of graphs.Electron. J. Comb. 10 (2003), Research paper R5, 8 pages printed version J. Comb. 10 (2003). Zbl 1018.05031, MR 1975755 |
| Reference:
|
[20] Zhang, Z., Zheng, Y., Mamut, A.: Nowhere-zero flows in tensor product of graphs.J. Graph Theory 54 (2007), 284-292. Zbl 1121.05099, MR 2292666, 10.1002/jgt.20211 |
| . |
