Strongly pancyclic and dual-pancyclic graphs

Terry A. McKee

Discussiones Mathematicae Graph Theory (2009)

  • Volume: 29, Issue: 1, page 5-14
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Terry A. McKee. "Strongly pancyclic and dual-pancyclic graphs." Discussiones Mathematicae Graph Theory 29.1 (2009): 5-14. <http://eudml.org/doc/270211>.

@article{TerryA2009,
abstract = {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.},
author = {Terry A. McKee},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {pancyclic graph; cycle extendable; chordal graph; pancyclic matroid; dual-chordal graph},
language = {eng},
number = {1},
pages = {5-14},
title = {Strongly pancyclic and dual-pancyclic graphs},
url = {http://eudml.org/doc/270211},
volume = {29},
year = {2009},
}

TY - JOUR
AU - Terry A. McKee
TI - Strongly pancyclic and dual-pancyclic graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2009
VL - 29
IS - 1
SP - 5
EP - 14
AB - 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.
LA - eng
KW - pancyclic graph; cycle extendable; chordal graph; pancyclic matroid; dual-chordal graph
UR - http://eudml.org/doc/270211
ER -

References

top
  1. [1] B. Beavers and J. Oxley, On pancyclic representable matroids, Discrete Math. 305 (2005) 337-343, doi: 10.1016/j.disc.2005.10.008. Zbl1080.05015
  2. [2] L. Cai, Spanning 2-trees, in: Algorithms, Concurrency and Knowledge (Pathumthani, 1995) 10-22, Lecture Notes in Comput. Sci. 1023 (Springer, Berlin, 1995). 
  3. [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. Zbl0839.05058
  4. [4] R. Faudree, Z. Ryjácek and I. Schiermeyer, Forbidden subgraphs and cycle extendability, J. Combin. Math. Combin. Comput. 19 (1995) 109-128. Zbl0839.05059
  5. [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). 
  6. [6] T.A. McKee, Recognizing dual-chordal graphs, Congr. Numer. 150 (2001) 97-103. Zbl0993.05118
  7. [7] T.A. McKee, Dualizing chordal graphs, Discrete Math. 263 (2003) 207-219, doi: 10.1016/S0012-365X(02)00577-0. Zbl1014.05040
  8. [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. Zbl0945.05003
  9. [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. 
  10. [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). Zbl1282.68131

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.