2018-06-01
Hendry's Conjecture on Chordal Graph Subclasses
Gerek, Aydin
Graduate Student
Mathematics
Isaak, Garth ; Skandera, Mark A. ; Coll, Vincent ; Gordon, Gary
text
dissertations
2017-01-01
2017
Lehigh University
eng
electronic documents
application/pdf
A cycle is extendable if there exists another cycle on the same set of vertices plus one more vertex. G.R.T. Hendry conjectured (1990) that every non spanning cycle in a Hamiltonian chordal graph is extendable. This has recently been disproved (2015), but is still open for classes of strongly chordal graphs. Hendry’s Conjecture has been shown to hold for the following subclasses of chordal graphs: planar chordal graphs (2002), interval graphs, strongly chordal graphs with (two specific) forbidden subgraphs, split graphs (2006), and spider intersection graphs (2013). Chapter 1 of this dissertation is an introduction to the subject matter. In chapter 2 we verify that Hendry’s Conjecture holds for Ptolemaic graphs which are a subclass of strongly chordal graphs, alongside with a strong result on how smoothly the extension can happen. In chapter 3 we develop tools for working on tree representations of chordal graphs with Hendry’s Conjecture in mind. Chapter 4 is an application of these tools to interval graphs, another subclass of chordal graphs. Chapter 5 is about manipulating the aformentioned counterexample to Hendry’s Conjecture, and applying tools from chapter 3 on it. This yields information on the structure of graphs for which Hendry’s conjecture holds.
chordal graphs Hamiltonian cycle Hendry's Conjecture interval graphs Ptolemaic graphs
https://asa.lib.lehigh.edu/Record/10773783