Cycle Double Covers of Infinite Planar Graphs

• Autorzy: Mohammad Javaheri
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

cycle double cover; infinite planar graph

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2016
• Tom: 36
• Numer: 3
• Strony: 523-544

Daty

wydano

2016-08-01

otrzymano

2014-12-08

poprawiono

2015-05-23

zaakceptowano

2015-08-16

online

2016-07-06

Twórcy

autor

Mohammad Javaheri

• 515 Loudon Road School of Science, Siena College Loudonville, NY 12211, USA

Bibliografia

• [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] 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]
• [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] M. Chan, A survey of the cycle double cover conjecture, (2009).
• [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.
• [6] R. Diestel, The cycle space of an infinite graph, Combin. Probab. Comput. 14 (2005) 59-79. doi:10.1017/S0963548304006686[Crossref]
• [7] R. Diestel and D. Kühl, On infinite cycles I, Combinatorica 24 (2004) 69-89. doi:10.1007/s00493-004-0005-z[Crossref]
• [8] R. Diestel and D. Kühl, On infinite cycles II, Combinatorica 24 (2004) 91-116. doi:10.1007/s00493-004-0006-y[Crossref]
• [9] G. Fan, Covering graphs by cycles, SIAM J. Discrete Math. 5 (1992) 491-496. doi:10.1137/0405039[Crossref]
• [10] I. Fary, On straight line representations of planar graphs, Acta Sci. Math. (Szeged) 11 (1984) 229-233.
• [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]
• [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]
• [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]
• [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]
• [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]
• [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]
• [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]
• [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] F. Jaeger, On circular flows in graphs, Proc. Colloq. Math. Janos Bolyai (1982) 391-402.
• [20] S. MacLane, A combinatorial condition for planar graphs, Fund. Math. 28 (1937) 22-32.
• [21] P.D. Seymour, Disjoint paths in graphs, Discrete Math. 29 (1980) 293-309. doi:10.1016/0012-365X(80)90158-2[Crossref]
• [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]
• [23] G. Szekeres, Polyhedral decompositions of cubic graphs, Bull. Aust. Math. Soc. 8 (1973) 367-387. doi:10.1017/S0004972700042660[Crossref]
• [24] P.G. Tait, Remarks on the colourings of maps, Proc. Roy. Soc. Edinburgh Sect. A 10 (1880) 729.[Crossref]
• [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] 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]
• [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] K. Wagner, Fastplättbare Graphen, J. Combin. Theory 3 (1967) 326-365. doi:10.1016/S0021-9800(67)80103-0[Crossref]
• [29] R. Xu, Strong 5-cycle double covers of graphs, Graphs Combin. 30 (2014) 495-499. doi:10.1007/s00373-012-1266-8[Crossref]
• [30] D. Ye, Perfect Matching and Circuit Cover of Graphs (Ph.D. Dissertation, West Virginia University, 2012).

Identyfikatory

DOI

10.7151/dmgt.1879