No Access

Requiring adjacent chords in cycles

Department of Mathematics & Statistics, Wright State University, Dayton, Ohio 45435, USA

https://doi.org/10.1142/S1793830918500039Cited by:0 (Source: Crossref)

Abstract

Define a new class of graphs by cycles of length 5 or more always having adjacent chords. This is equivalent to cycles of length 5 or more always having noncrossing chords, which is a property that has a known forbidden induced subgraph characterization. Another characterization comes from viewing the graphs in this class in contrast to distance-hereditary graphs (which are characterized by cycles of length 5 or more always having crossing chords). Moreover, the graphs in the new class are those in which every edge of every cycle $C$ $C$ of length 5 or more forms a triangle with a third vertex of $C$ $C$ (generalizing that a graph is chordal if and only if every edge of every cycle $C$ $C$ of length 4 or more forms a triangle with a third vertex of $C$ $C$ ). This leads to a strategically-required subgraph characterization of the new class.

Keywords:

AMSC: 05C75, 05C38

References

1. M. Aïder , Almost distance-hereditary graphs, Discrete Math. 242 (2002) 1–16. Crossref, Google Scholar
2. H.-J. Bandelt and H. M. Mulder , Distance-hereditary graphs, J. Combin. Theory, Ser. B 41 (1986) 182–208. Crossref, Google Scholar
3. A. Brandstädt, V. B. Le and J. P. Spinrad , Graph Classes: A Survey (Society for Industrial and Applied Mathematics, Philadelphia, 1999). Crossref, Google Scholar
4. G. J. Chang and G. L. Nemhauser , The $k$ $k$ -domination and $k$ $k$ -stability problems on sun-free chordal graphs, SIAM J. Algebr. Discrete Meth. 5 (1984) 332–345. Crossref, Google Scholar
5. E. Howorka , A characterization of distance-hereditary graphs, Quart. J. Math. Oxford, Ser. 2 28 (1977) 417–420. Crossref, Google Scholar
6. T. A. McKee , Uniquely hamiltonian characterizations of distance-hereditary and parity graphs, Electron. J. Combin. 15 (2008) Note 36, 5pp. Crossref, Google Scholar
7. T. A. McKee , Edge cycle extendable graphs, Discuss. Math. Graph Theory 32 (2012) 373–378. Crossref, Google Scholar
8. T. A. McKee , Requiring pairwise nonadjacent chords in cycles, J. Comb. 4 (2013) 357–372. Google Scholar
9. T. A. McKee, Uncrossed chords of cycles in chordal graphs, submitted. Google Scholar