Geodesic
Flows on the join of two graphs
Mathematica Bohemica, Tome 138 (2013) no. 4, pp. 383-396

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

MR Zbl
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.
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.
DOI : 10.21136/MB.2013.143511
Classification : 05C21
Keywords: nowhere-zero flow; graph join 
Lukoťka, Robert; Rollová, Edita. Flows on the join of two graphs. Mathematica Bohemica, Tome 138 (2013) no. 4, pp. 383-396. doi: 10.21136/MB.2013.143511
@article{10_21136_MB_2013_143511,
     author = {Luko\v{t}ka, Robert and Rollov\'a, Edita},
     title = {Flows on the join of two graphs},
     journal = {Mathematica Bohemica},
     pages = {383--396},
     year = {2013},
     volume = {138},
     number = {4},
     doi = {10.21136/MB.2013.143511},
     mrnumber = {3231093},
     zbl = {06260039},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.2013.143511/}
}
TY  - JOUR
AU  - Lukoťka, Robert
AU  - Rollová, Edita
TI  - Flows on the join of two graphs
JO  - Mathematica Bohemica
PY  - 2013
SP  - 383
EP  - 396
VL  - 138
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.2013.143511/
DO  - 10.21136/MB.2013.143511
LA  - en
ID  - 10_21136_MB_2013_143511
ER  - 
%0 Journal Article
%A Lukoťka, Robert
%A Rollová, Edita
%T Flows on the join of two graphs
%J Mathematica Bohemica
%D 2013
%P 383-396
%V 138
%N 4
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.2013.143511/
%R 10.21136/MB.2013.143511
%G en
%F 10_21136_MB_2013_143511

[1] Bondy, J. A., Murty, U. S. R.: Graph Theory. Graduate Texts in Mathematics 244 Springer, Berlin (2008). | DOI | MR | Zbl

[2] Chen, J. J., Eschen, E., Lai, H.-J.: Group connectivity of certain graphs. Ars Comb. 89 (2008), 141-158. | MR | Zbl

[3] Diestel, R.: Graph Theory. Third ed. Graduate Texts in Mathematics 173 Springer, Berlin (2005). | MR | Zbl

[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 | MR | Zbl

[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

[6] Imrich, W., Škrekovski, R.: A theorem on integer flows on Cartesian products of graphs. J. Graph Theory 43 (2003), 93-98. | DOI | MR | Zbl

[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 | Zbl

[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 | MR | Zbl

[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 | MR | Zbl

[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 | MR | Zbl

[11] Robertson, N., Seymour, P., Thomas, R.: Tutte's edge-colouring conjecture. J. Comb. Theory, Ser. B 70 (1997), 166-183. | DOI | MR | Zbl

[12] Rollová, E., Škoviera, M.: Nowhere-zero flows in Cartesian bundles of graphs. Eur. J. Comb. 33 (2012), 867-871. | DOI | MR | Zbl

[13] Seymour, P. D.: Nowhere-zero $6$-flows. J. Comb. Theory, Ser. B 30 (1981), 130-135. | DOI | MR | Zbl

[14] Shahmohamad, H.: On minimum flow number of graphs. Bull. Inst. Comb. Appl. 35 (2002), 26-36. | MR | Zbl

[15] Shu, J., Zhang, C.-Q.: Nowhere-zero $3$-flows in products of graphs. J. Graph Theory 50 (2005), 79-89. | DOI | MR | Zbl

[16] Steffen, E.: Circular flow numbers of regular multigraphs. J. Graph Theory 36 (2001), 24-34. | DOI | MR | Zbl

[17] Thomassen, C.: The weak $3$-flow conjecture and the weak circular flow conjecture. J. Comb. Theory, Ser. B 102 (2012), 521-529. | DOI | MR | Zbl

[18] Tutte, W. T.: On the imbedding of linear graphs in surfaces. Proc. Lond. Math. Soc., II. Ser. 51 (1949), 474-483. | DOI | MR | Zbl

[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 | Zbl

[20] Zhang, Z., Zheng, Y., Mamut, A.: Nowhere-zero flows in tensor product of graphs. J. Graph Theory 54 (2007), 284-292. | DOI | MR | Zbl

Cité par Sources :