Path and cycle factors of cubic bipartite graphs
M. Kano ; Changwoo Lee ; Kazuhiro Suzuki
Discussiones Mathematicae Graph Theory, Tome 28 (2008), p. 551-556 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

For a set S of connected graphs, a spanning subgraph F of a graph is called an S-factor if every component of F is isomorphic to a member of S. It was recently shown that every 2-connected cubic graph has a {Cₙ | n ≥ 4}-factor and a {Pₙ | n ≥ 6}-factor, where Cₙ and Pₙ denote the cycle and the path of order n, respectively (Kawarabayashi et al., J. Graph Theory, Vol. 39 (2002) 188-193). In this paper, we show that every connected cubic bipartite graph has a {Cₙ | n ≥ 6}-factor, and has a {Pₙ | n ≥ 8}-factor if its order is at least 8.

Publié le : 2008-01-01
EUDML-ID : urn:eudml:doc:270380 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1426,
     author = {M. Kano and Changwoo Lee and Kazuhiro Suzuki},
     title = {Path and cycle factors of cubic bipartite graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {28},
     year = {2008},
     pages = {551-556},
     zbl = {1173.05028},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1426}
}

M. Kano; Changwoo Lee; Kazuhiro Suzuki. Path and cycle factors of cubic bipartite graphs. Discussiones Mathematicae Graph Theory, Tome 28 (2008) pp. 551-556. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1426/

[000] [1] J. Akiyama and M. Kano, Path factors of a graph, Graphs and applications (Boulder, Colo., 1982), 1-21, Wiley-Intersci. Publ., Wiley, New York, 1985. | Zbl 0587.05048

[001] [2] A. Kaneko, A necessary and sufficient condition for the existence of a path factor every component of which is a path of length at least two, J. Combin. Theory (B) 88 (2003) 195-218, doi: 10.1016/S0095-8956(03)00027-3. | Zbl 1029.05125

[002] [3] M. Kano, G.Y. Katona and Z. Király, Packing paths of length at least two, Discrete Math. 283 (2004) 129-135, doi: 10.1016/j.disc.2004.01.016. | Zbl 1042.05084

[003] [4] K. Kawarabayashi, H. Matsuda, Y. Oda and K. Ota, Path factors in cubic graphs, J. Graph Theory 39 (2002) 188-193, doi: 10.1002/jgt.10022. | Zbl 1176.05064

[004] [5] J. Petersen, Die Theorie der regulären Graphen, Acta Math. 15 (1891) 193-220, doi: 10.1007/BF02392606.