Flows on the join of two graphs

Robert Lukoťka; Edita Rollová

Mathematica Bohemica (2013)

  • Volume: 138, Issue: 4, page 383-396
  • ISSN: 0862-7959

Abstract

top
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.

How to cite

top

Lukoťka, Robert, and Rollová, Edita. "Flows on the join of two graphs." Mathematica Bohemica 138.4 (2013): 383-396. <http://eudml.org/doc/260670>.

@article{Lukoťka2013,
abstract = {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.},
author = {Lukoťka, Robert, Rollová, Edita},
journal = {Mathematica Bohemica},
keywords = {nowhere-zero flow; graph join; nowhere-zero flow; graph join},
language = {eng},
number = {4},
pages = {383-396},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Flows on the join of two graphs},
url = {http://eudml.org/doc/260670},
volume = {138},
year = {2013},
}

TY - JOUR
AU - Lukoťka, Robert
AU - Rollová, Edita
TI - Flows on the join of two graphs
JO - Mathematica Bohemica
PY - 2013
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 138
IS - 4
SP - 383
EP - 396
AB - 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.
LA - eng
KW - nowhere-zero flow; graph join; nowhere-zero flow; graph join
UR - http://eudml.org/doc/260670
ER -

References

top
  1. Bondy, J. A., Murty, U. S. R., 10.1007/978-1-84628-970-5_1, Graduate Texts in Mathematics 244 Springer, Berlin (2008). (2008) Zbl1134.05001MR2368647DOI10.1007/978-1-84628-970-5_1
  2. Chen, J. J., Eschen, E., Lai, H.-J., Group connectivity of certain graphs, Ars Comb. 89 (2008), 141-158. (2008) Zbl1224.05267MR2456240
  3. Diestel, R., Graph Theory, Third ed. Graduate Texts in Mathematics 173 Springer, Berlin (2005). (2005) Zbl1074.05001MR2159259
  4. Fan, G., Lai, H., Xu, R., Zhang, C.-Q., Zhou, Ch., 10.1016/j.jctb.2008.02.008, J. Comb. Theory, Ser. B 98 (2008), 1325-1336. (2008) Zbl1171.05026MR2462322DOI10.1016/j.jctb.2008.02.008
  5. Imrich, W., Peterin, I., Špacarpan, S., Zhang, C.-Q., NZ-flows in strong products of graphs, J. Graph Theory 64 (2010), 267-276. (2010) MR2668543
  6. Imrich, W., Škrekovski, R., 10.1002/jgt.10100, J. Graph Theory 43 (2003), 93-98. (2003) Zbl1019.05058MR1978114DOI10.1002/jgt.10100
  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. (1988) Zbl0658.05034MR1205397
  8. Jaeger, F., Linial, N., Payan, C., Tarsi, M., 10.1016/0095-8956(92)90016-Q, J. Comb. Theory, Ser. B 56 (1992), 165-182. (1992) Zbl0824.05043MR1186753DOI10.1016/0095-8956(92)90016-Q
  9. Kochol, M., 10.1016/j.jctb.2009.12.001, J. Comb. Theory, Ser. B 100 (2010), 381-389. (2010) Zbl1211.05055MR2644241DOI10.1016/j.jctb.2009.12.001
  10. Nánásiová, M., Škoviera, M., 10.1007/s10801-008-0153-0, J. Algebr. Comb. 30 (2009), 103-111. (2009) Zbl1208.05053MR2519851DOI10.1007/s10801-008-0153-0
  11. Robertson, N., Seymour, P., Thomas, R., 10.1006/jctb.1997.1752, J. Comb. Theory, Ser. B 70 (1997), 166-183. (1997) Zbl0883.05055MR1441265DOI10.1006/jctb.1997.1752
  12. Rollová, E., Škoviera, M., 10.1016/j.ejc.2011.09.022, Eur. J. Comb. 33 (2012), 867-871. (2012) Zbl1293.05325MR2889520DOI10.1016/j.ejc.2011.09.022
  13. Seymour, P. D., 10.1016/0095-8956(81)90058-7, J. Comb. Theory, Ser. B 30 (1981), 130-135. (1981) Zbl0474.05028MR0615308DOI10.1016/0095-8956(81)90058-7
  14. Shahmohamad, H., On minimum flow number of graphs, Bull. Inst. Comb. Appl. 35 (2002), 26-36. (2002) Zbl0990.05072MR1901238
  15. Shu, J., Zhang, C.-Q., 10.1002/jgt.20095, J. Graph Theory 50 (2005), 79-89. (2005) Zbl1069.05040MR2157539DOI10.1002/jgt.20095
  16. Steffen, E., 10.1002/1097-0118(200101)36:1<24::AID-JGT3>3.0.CO;2-Q, J. Graph Theory 36 (2001), 24-34. (2001) Zbl0982.05060MR1803631DOI10.1002/1097-0118(200101)36:1<24::AID-JGT3>3.0.CO;2-Q
  17. Thomassen, C., 10.1016/j.jctb.2011.09.003, J. Comb. Theory, Ser. B 102 (2012), 521-529. (2012) Zbl1239.05083MR2885433DOI10.1016/j.jctb.2011.09.003
  18. Tutte, W. T., 10.1112/plms/s2-51.6.474, Proc. Lond. Math. Soc., II. Ser. 51 (1949), 474-483. (1949) Zbl0033.30803MR0029495DOI10.1112/plms/s2-51.6.474
  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). (2003) Zbl1018.05031MR1975755
  20. Zhang, Z., Zheng, Y., Mamut, A., 10.1002/jgt.20211, J. Graph Theory 54 (2007), 284-292. (2007) Zbl1121.05099MR2292666DOI10.1002/jgt.20211

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.