Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
nowhere-zero flow; graph join
nowhere-zero flow; graph join
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.
References:
[1] Bondy, J. A., Murty, U. S. R.: Graph Theory. Graduate Texts in Mathematics 244 Springer, Berlin (2008). DOI 10.1007/978-1-84628-970-5_1 | MR 2368647 | Zbl 1134.05001
[2] Chen, J. J., Eschen, E., Lai, H.-J.: Group connectivity of certain graphs. Ars Comb. 89 (2008), 141-158. MR 2456240 | Zbl 1224.05267
[3] Diestel, R.: Graph Theory. Third ed. Graduate Texts in Mathematics 173 Springer, Berlin (2005). MR 2159259 | Zbl 1074.05001
[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. DOI 10.1016/j.jctb.2008.02.008 | MR 2462322 | Zbl 1171.05026
[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
[6] Imrich, W., Škrekovski, R.: A theorem on integer flows on Cartesian products of graphs. J. Graph Theory 43 (2003), 93-98. DOI 10.1002/jgt.10100 | MR 1978114 | Zbl 1019.05058
[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. MR 1205397 | Zbl 0658.05034
[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. DOI 10.1016/0095-8956(92)90016-Q | MR 1186753 | Zbl 0824.05043
[9] Kochol, M.: Smallest counterexample to the 5-flow conjecture has girth at least eleven. J. Comb. Theory, Ser. B 100 (2010), 381-389. DOI 10.1016/j.jctb.2009.12.001 | MR 2644241 | Zbl 1211.05055
[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. DOI 10.1007/s10801-008-0153-0 | MR 2519851 | Zbl 1208.05053
[11] Robertson, N., Seymour, P., Thomas, R.: Tutte's edge-colouring conjecture. J. Comb. Theory, Ser. B 70 (1997), 166-183. DOI 10.1006/jctb.1997.1752 | MR 1441265 | Zbl 0883.05055
[12] Rollová, E., Škoviera, M.: Nowhere-zero flows in Cartesian bundles of graphs. Eur. J. Comb. 33 (2012), 867-871. DOI 10.1016/j.ejc.2011.09.022 | MR 2889520 | Zbl 1293.05325
[13] 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
[14] Shahmohamad, H.: On minimum flow number of graphs. Bull. Inst. Comb. Appl. 35 (2002), 26-36. MR 1901238 | Zbl 0990.05072
[15] Shu, J., Zhang, C.-Q.: Nowhere-zero $3$-flows in products of graphs. J. Graph Theory 50 (2005), 79-89. DOI 10.1002/jgt.20095 | MR 2157539 | Zbl 1069.05040
[16] Steffen, E.: Circular flow numbers of regular multigraphs. J. Graph Theory 36 (2001), 24-34. DOI 10.1002/1097-0118(200101)36:1<24::AID-JGT3>3.0.CO;2-Q | MR 1803631 | Zbl 0982.05060
[17] Thomassen, C.: The weak $3$-flow conjecture and the weak circular flow conjecture. J. Comb. Theory, Ser. B 102 (2012), 521-529. DOI 10.1016/j.jctb.2011.09.003 | MR 2885433 | Zbl 1239.05083
[18] 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
[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). MR 1975755 | Zbl 1018.05031
[20] Zhang, Z., Zheng, Y., Mamut, A.: Nowhere-zero flows in tensor product of graphs. J. Graph Theory 54 (2007), 284-292. DOI 10.1002/jgt.20211 | MR 2292666 | Zbl 1121.05099
Search
Partner of
