Strongly pancyclic and dual-pancyclic graphs
Terry A. McKee
Discussiones Mathematicae Graph Theory, Tome 29 (2009), p. 5-14 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

Say that a cycle C almost contains a cycle C¯ if every edge except one of C¯ is an edge of C. Call a graph G strongly pancyclic if every nontriangular cycle C almost contains another cycle C¯ and every nonspanning cycle C is almost contained in another cycle C⁺. This is equivalent to requiring, in addition, that the sizes of C¯ and C⁺ differ by one from the size of C. Strongly pancyclic graphs are pancyclic and chordal, and their cycles enjoy certain interpolation and extrapolation properties with respect to almost containment. Much of this carries over from graphic to cographic matroids; the resulting 'dual-pancyclic' graphs are shown to be exactly the 3-regular dual-chordal graphs.

Publié le : 2009-01-01
EUDML-ID : urn:eudml:doc:270211 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1429,
     author = {Terry A. McKee},
     title = {Strongly pancyclic and dual-pancyclic graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {29},
     year = {2009},
     pages = {5-14},
     zbl = {1182.05072},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1429}
}

Terry A. McKee. Strongly pancyclic and dual-pancyclic graphs. Discussiones Mathematicae Graph Theory, Tome 29 (2009) pp. 5-14. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1429/

[000] [1] B. Beavers and J. Oxley, On pancyclic representable matroids, Discrete Math. 305 (2005) 337-343, doi: 10.1016/j.disc.2005.10.008. | Zbl 1080.05015

[001] [2] L. Cai, Spanning 2-trees, in: Algorithms, Concurrency and Knowledge (Pathumthani, 1995) 10-22, Lecture Notes in Comput. Sci. 1023 (Springer, Berlin, 1995).

[002] [3] R.J. Faudree, R.J. Gould, M.S. Jacobson and L.M. Lesniak, Degree conditions and cycle extendability, Discrete Math. 141 (1995) 109-122, doi: 10.1016/0012-365X(93)E0193-8. | Zbl 0839.05058

[003] [4] R. Faudree, Z. Ryjácek and I. Schiermeyer, Forbidden subgraphs and cycle extendability, J. Combin. Math. Combin. Comput. 19 (1995) 109-128. | Zbl 0839.05059

[004] [5] K.P. Kumar and C.E. Veni Madhavan, A new class of separators and planarity of chordal graphs, in: Foundations of Software Technology and Theoretical Computer Science (Bangalore, 1989) 30-43, Lecture Notes in Comput. Sci. 405 (Springer, Berlin, 1989).

[005] [6] T.A. McKee, Recognizing dual-chordal graphs, Congr. Numer. 150 (2001) 97-103. | Zbl 0993.05118

[006] [7] T.A. McKee, Dualizing chordal graphs, Discrete Math. 263 (2003) 207-219, doi: 10.1016/S0012-365X(02)00577-0. | Zbl 1014.05040

[007] [8] T.A. McKee and F.R. McMorris, Topics in Intersection Graph Theory (Society for Industrial and Applied Mathematics, Philadelphia, 1999), doi: 10.1137/1.9780898719802. | Zbl 0945.05003

[008] [9] J.G. Oxley, Matroidal methods in graph theory, in: Handbook of Graph Theory, Discrete Mathematics and its Applications, J.L. Gross and J. Yellen, eds CRC Press (Boca Raton, FL, 2004) 574-598.

[009] [10] M. Yannakakis, Node- and edge-deletion NP-complete problems, Conference Record of the Tenth Annual ACM Symposium on Theory of Computing (San Diego, Calif., 1978), 253-264 (ACM, New York, 1978). | Zbl 1282.68131