Guaranteed upper bounds on the length of a shortest cycle through k ≤ 5 prescribed vertices of a polyhedral graph or plane triangulation are proved.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1293,
author = {Erhard Hexel},
title = {On short cycles through prescribed vertices of a polyhedral graph},
journal = {Discussiones Mathematicae Graph Theory},
volume = {25},
year = {2005},
pages = {419-426},
zbl = {1105.05038},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1293}
}
Erhard Hexel. On short cycles through prescribed vertices of a polyhedral graph. Discussiones Mathematicae Graph Theory, Tome 25 (2005) pp. 419-426. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1293/
[000] [1] B. Bollobás and G. Brightwell, Cycles through specified vertices, Combinatorica 13 (1993) 147-155, doi: 10.1007/BF01303200. | Zbl 0780.05033
[001] [2] G.A. Dirac, 4-crome Graphen und vollständige 4-Graphen, Math. Nachr. 22 (1960) 51-60, doi: 10.1002/mana.19600220106. | Zbl 0096.17902
[002] [3] F. Göring, J. Harant, E. Hexel and Zs. Tuza, On short cycles through prescribed vertices of a graph, Discrete Math. 286 (2004) 67-74, doi: 10.1016/j.disc.2003.11.047.
[003] [4] J. Harant, On paths and cycles through specified vertices, Discrete Math. 286 (2004) 95-98, doi: 10.1016/j.disc.2003.11.059. | Zbl 1048.05050
[004] [5] R. Diestel, Graph Theory (Springer, Graduate Texts in Mathematics 173, 2000).
[005] [6] A.K. Kelmans and M.V. Lomonosov, When m vertices in a k-connected graph cannot be walked round along a simple cycle, Discrete Math. 38 (1982) 317-322, doi: 10.1016/0012-365X(82)90299-0. | Zbl 0475.05053
[006] [7] T. Sakai, Long paths and cycles through specified vertices in k-connected graphs, Ars Combin. 58 (2001) 33-65. | Zbl 1065.05059