Cycle Double Covers of Infinite Planar Graphs

Mohammad Javaheri

Discussiones Mathematicae Graph Theory (2016)

  • Volume: 36, Issue: 3, page 523-544
  • ISSN: 2083-5892

Abstract

top
In this paper, we study the existence of cycle double covers for infinite planar graphs. We show that every infinite locally finite bridgeless k-indivisible graph with a 2-basis admits a cycle double cover.

How to cite

top

Mohammad Javaheri. "Cycle Double Covers of Infinite Planar Graphs." Discussiones Mathematicae Graph Theory 36.3 (2016): 523-544. <http://eudml.org/doc/285515>.

@article{MohammadJavaheri2016,
abstract = {In this paper, we study the existence of cycle double covers for infinite planar graphs. We show that every infinite locally finite bridgeless k-indivisible graph with a 2-basis admits a cycle double cover.},
author = {Mohammad Javaheri},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {cycle double cover; infinite planar graph},
language = {eng},
number = {3},
pages = {523-544},
title = {Cycle Double Covers of Infinite Planar Graphs},
url = {http://eudml.org/doc/285515},
volume = {36},
year = {2016},
}

TY - JOUR
AU - Mohammad Javaheri
TI - Cycle Double Covers of Infinite Planar Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2016
VL - 36
IS - 3
SP - 523
EP - 544
AB - In this paper, we study the existence of cycle double covers for infinite planar graphs. We show that every infinite locally finite bridgeless k-indivisible graph with a 2-basis admits a cycle double cover.
LA - eng
KW - cycle double cover; infinite planar graph
UR - http://eudml.org/doc/285515
ER -

References

top
  1. [1] J.C. Bermond, B. Jackson and F. Jaeger, Shortest coverings of graphs with cycles, J. Combin. Theory Ser. B 35 (1993) 297-308. doi:10.1016/0095-8956(83)90056-4[Crossref] 
  2. [2] G. Brinkmann, J. Goedgebeur, J. Hägglund and K. Markström, Generation and properties of snarks, J. Combin. Theory Ser. B 103 (2013) 468-488. doi:10.1016/j.jctb.2013.05.001[WoS][Crossref] Zbl1301.05119
  3. [3] H. Bruhn and M. Stein, MacLane’s planarity criterion for locally finite graphs, J. Combin. Theory Ser. B 96 (2006) 225-239. doi:10.1016/j.jctb.2005.07.005[Crossref] 
  4. [4] M. Chan, A survey of the cycle double cover conjecture, (2009). 
  5. [5] N.G. de Bruijn and P. Erdős, A colour problem for infinite graphs and a problem in the theory of relations, Nederl. Akad. Wetensch. Porc. Ser. A 54 (1951) 369-373. Zbl0044.38203
  6. [6] R. Diestel, The cycle space of an infinite graph, Combin. Probab. Comput. 14 (2005) 59-79. doi:10.1017/S0963548304006686[Crossref] Zbl1067.05037
  7. [7] R. Diestel and D. Kühl, On infinite cycles I, Combinatorica 24 (2004) 69-89. doi:10.1007/s00493-004-0005-z[Crossref] Zbl1063.05076
  8. [8] R. Diestel and D. Kühl, On infinite cycles II, Combinatorica 24 (2004) 91-116. doi:10.1007/s00493-004-0006-y[Crossref] Zbl1063.05076
  9. [9] G. Fan, Covering graphs by cycles, SIAM J. Discrete Math. 5 (1992) 491-496. doi:10.1137/0405039[Crossref] Zbl0777.05087
  10. [10] I. Fary, On straight line representations of planar graphs, Acta Sci. Math. (Szeged) 11 (1984) 229-233. 
  11. [11] H. Fleischner, Proof of the strong 2-cover conjecture for planar graphs, J. Combin. Theory Ser. B 40 (1986) 229-230. doi:10.1016/0095-8956(86)90080-8[Crossref] Zbl0587.05041
  12. [12] H. Fleischner and R. Häggkvist, Circuit double covers in special types of cubic graphs, Discrete Math. 309 (2009) 5724-5728. doi:10.1016/j.disc.2008.05.018[WoS][Crossref] Zbl1218.05129
  13. [13] L. Goddyn, A girth requirement for the double cycle cover conjecture, Ann. Discrete Math. 27 (1985) 13-26. doi:10.1016/s0304-0208(08)72994-3[Crossref] Zbl0585.05013
  14. [14] J. Hägglund and K. Markström, On stable cycles and cycle double covers of graphs with large circumference, Discrete Math. 312 (2012) 2540-2544. doi:10.1016/j.disc.2011.08.024[WoS][Crossref] Zbl1246.05086
  15. [15] A. Hoffmann-Ostenhof, A note on 5-cycle double covers, Graphs Combin. 29 (2013) 977-979. doi:10.1007/s00373-012-1169-8[Crossref] Zbl1268.05158
  16. [16] A. Huck, Reducible configurations for the cycle double cover conjecture, Discrete Appl. Math. 99 (2000) 71-90. doi:10.1016/S0166-218X(99)00126-2[Crossref] Zbl0966.05045
  17. [17] R. Isaacs, Infinite families of nontrivial trivalent graphs which are not Tait colorable, Amer. Math. Monthly 82 (1975) 221-239. doi:10.2307/2319844[Crossref] Zbl0311.05109
  18. [18] F. Jaeger, A survey of the cycle double cover conjecture, Ann. Discrete Math. 27 (1985) 1-12. doi:10.1016/s0304-0208(08)72993-1[Crossref] 
  19. [19] F. Jaeger, On circular flows in graphs, Proc. Colloq. Math. Janos Bolyai (1982) 391-402. 
  20. [20] S. MacLane, A combinatorial condition for planar graphs, Fund. Math. 28 (1937) 22-32.  Zbl0015.37501
  21. [21] P.D. Seymour, Disjoint paths in graphs, Discrete Math. 29 (1980) 293-309. doi:10.1016/0012-365X(80)90158-2[Crossref] 
  22. [22] P.D. Seymour, Nowhere-zero 6-flows, J. Combin. Theory Ser. B 30 (1981) 130-135. doi:10.1016/0095-8956(81)90058-7[Crossref] Zbl0474.05028
  23. [23] G. Szekeres, Polyhedral decompositions of cubic graphs, Bull. Aust. Math. Soc. 8 (1973) 367-387. doi:10.1017/S0004972700042660[Crossref] Zbl0249.05111
  24. [24] P.G. Tait, Remarks on the colourings of maps, Proc. Roy. Soc. Edinburgh Sect. A 10 (1880) 729.[Crossref] 
  25. [25] C. Thomassen, Planarity and duality of finite and infinite graphs, J. Combin. Theory Ser. B 29 (1980) 244-271. doi:10.1016/0095-8956(80)90083-0[Crossref] 
  26. [26] C. Thomassen, Straight line representation of infinite planar graphs, J. Lond. Math. Soc. (2) 16 (1977) 411-423. doi:10.1112/jlms/s2-16.3.411[Crossref] Zbl0373.05032
  27. [27] W.T. Tutte, A contribution to the theory of chromatic polynomials, Canad. J. Math. 6 (1954) 80-91. doi:10.4153/CJM-1954-010-9[Crossref] 
  28. [28] K. Wagner, Fastplättbare Graphen, J. Combin. Theory 3 (1967) 326-365. doi:10.1016/S0021-9800(67)80103-0[Crossref] 
  29. [29] R. Xu, Strong 5-cycle double covers of graphs, Graphs Combin. 30 (2014) 495-499. doi:10.1007/s00373-012-1266-8[Crossref] Zbl1298.05180
  30. [30] D. Ye, Perfect Matching and Circuit Cover of Graphs (Ph.D. Dissertation, West Virginia University, 2012). 

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.