The i-chords of cycles and paths

Terry A. McKee

Discussiones Mathematicae Graph Theory (2012)

  • Volume: 32, Issue: 4, page 607-615
  • ISSN: 2083-5892

Abstract

top
An i-chord of a cycle or path is an edge whose endpoints are a distance i ≥ 2 apart along the cycle or path. Motivated by many standard graph classes being describable by the existence of chords, we investigate what happens when i-chords are required for specific values of i. Results include the following: A graph is strongly chordal if and only if, for i ∈ {4,6}, every cycle C with |V(C)| ≥ i has an (i/2)-chord. A graph is a threshold graph if and only if, for i ∈ {4,5}, every path P with |V(P)| ≥ i has an (i -2)-chord.

How to cite

top

Terry A. McKee. "The i-chords of cycles and paths." Discussiones Mathematicae Graph Theory 32.4 (2012): 607-615. <http://eudml.org/doc/270941>.

@article{TerryA2012,
abstract = {An i-chord of a cycle or path is an edge whose endpoints are a distance i ≥ 2 apart along the cycle or path. Motivated by many standard graph classes being describable by the existence of chords, we investigate what happens when i-chords are required for specific values of i. Results include the following: A graph is strongly chordal if and only if, for i ∈ \{4,6\}, every cycle C with |V(C)| ≥ i has an (i/2)-chord. A graph is a threshold graph if and only if, for i ∈ \{4,5\}, every path P with |V(P)| ≥ i has an (i -2)-chord.},
author = {Terry A. McKee},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {chord; chordal graph; strongly chordal graph; ptolemaic graph; trivially perfect graph; threshold graph; Ptolemaic graph},
language = {eng},
number = {4},
pages = {607-615},
title = {The i-chords of cycles and paths},
url = {http://eudml.org/doc/270941},
volume = {32},
year = {2012},
}

TY - JOUR
AU - Terry A. McKee
TI - The i-chords of cycles and paths
JO - Discussiones Mathematicae Graph Theory
PY - 2012
VL - 32
IS - 4
SP - 607
EP - 615
AB - An i-chord of a cycle or path is an edge whose endpoints are a distance i ≥ 2 apart along the cycle or path. Motivated by many standard graph classes being describable by the existence of chords, we investigate what happens when i-chords are required for specific values of i. Results include the following: A graph is strongly chordal if and only if, for i ∈ {4,6}, every cycle C with |V(C)| ≥ i has an (i/2)-chord. A graph is a threshold graph if and only if, for i ∈ {4,5}, every path P with |V(P)| ≥ i has an (i -2)-chord.
LA - eng
KW - chord; chordal graph; strongly chordal graph; ptolemaic graph; trivially perfect graph; threshold graph; Ptolemaic graph
UR - http://eudml.org/doc/270941
ER -

References

top
  1. [1] H.-J. Bandelt and H.M. Mulder, Distance-hereditary graphs, J. Combin. Theory (B) 41 (1986) 182-208, doi: 10.1016/0095-8956(86)90043-2. Zbl0605.05024
  2. [2] A. Brandstädt, V.B. Le and J.P. Spinrad, Graph Classes: A Survey (Society for Industrial and Applied Mathematics, Philadelphia, 1999). 
  3. [3] M.B. Cozzens and L.L. Kelleher, Dominating cliques in graphs, Discrete Math. 86 (1990) 101-116, doi: 10.1016/0012-365X(90)90353-J. Zbl0729.05043
  4. [4] M. Farber, Characterizations of strongly chordal graphs, Discrete Math. 43 (1983) 173-189, doi: 10.1016/0012-365X(83)90154-1. Zbl0514.05048
  5. [5] E. Howorka, A characterization of ptolemaic graphs, J. Graph Theory 5 (1981) 323-331, doi: 10.1002/jgt.3190050314. Zbl0437.05046
  6. [6] J. Liu and H.S. Zhou, Dominating subgraphs in graphs with some forbidden structures, Discrete Math. 135 (1994) 163-168, doi: 10.1016/0012-365X(93)E0111-G. Zbl0812.05052
  7. [7] N.V.R. Mahadev and U.N. Peled, Threshold Graphs and Related Topics (North-Holland, Amsterdam, 1995). Zbl0852.05001
  8. [8] A. McKee, Constrained chords in strongly chordal and distance-hereditary graphs, Utilitas Math. 87 (2012) 3-12. Zbl1264.05112
  9. [9] T.A. McKee and F.R. McMorris, Topics in Intersection Graph Theory (Society for Industrial and Applied Mathematics, Philadelphia, 1999). Zbl0945.05003
  10. [10] E.S. Wolk, The comparability graph of a tree, Proc. Amer. Math. Soc. 13 (1962) 789-795, doi: 10.1090/S0002-9939-1962-0172273-0. Zbl0109.16402

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.