PDF
Discussiones Mathematicae Graph Theory 32(2) (2012)
373-378
DOI: https://doi.org/10.7151/dmgt.1606
Edge Cycle Extendable Graphs
| Terry A. McKee
Department of Mathematics and Statistics |
Abstract
A graph is edge cycle extendable if every cycle C that is formed from edges and one chord of a larger cycle C+ is also formed from edges and one chord of a cycle C ′ of length one greater than C with V(C ′) ⊆ V(C+). Edge cycle extendable graphs are characterized by every block being either chordal (every nontriangular cycle has a chord) or chordless (no nontriangular cycle has a chord); equivalently, every chord of a cycle of length five or more has a noncrossing chord.
Keywords: cycle extendable graph, chordal graph, chordless graph, minimally 2-connected graph
2010 Mathematics Subject Classification: 05C75, 05C38.
References
| [1] | A. Brandstädt, V.B. Le and J.P. Spinrad, Graph Classes: A Survey (Society for Industrial and Applied Mathematics, Philadelphia, 1999). |
| [2] | G.A. Dirac, Minimally 2-connected graphs, J. Reine Angew. Math. 228 (1967) 204--216, doi: 10.1515/crll.1967.228.204. |
| [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. |
| [4] | B.Lévêque, F. Maffray and N. Trotignon, On graphs with no induced subdivision of K4, submitted. |
| [5] | T.A. McKee, Strongly pancyclic and dual-pancyclic graphs, Discuss. Math. Graph Theory 29 (2009) 5--14, doi: 10.7151/dmgt.1429. |
| [6] | T.A. McKee and F.R. McMorris, Topics in Intersection Graph Theory (Society for Industrial and Applied Mathematics, Philadelphia, 1999). |
| [7] | M.D. Plummer, On minimal blocks, Trans. Amer. Math. Soc. 134 (1968) 85--94, doi: 10.1090/S0002-9947-1968-0228369-8. |
Received 29 October 2010
Revised 8 June 2011
Accepted 8 June 2011
Close