Authors:
T.A. McKee
Title:
Dualizing distance-hereditary graphs
Source:
Discussiones Mathematicae Graph Theory
Received 04.05.2018, Revised 23.10.2018, Accepted 23.10.2018, doi: 10.7151/dmgt.2192

Abstract:
Distance-hereditary graphs can be characterized by every cycle of length at least 5 having crossing chords. This makes distance-hereditary graphs susceptible to dualizing, using the common extension of geometric face/vertex planar graph duality to cycle/cutset duality as in abstract matroidal duality. The resulting ``DH* graphs'' are characterized and then analyzed in terms of connectivity. These results are used in a special case of plane-embedded graphs to justify viewing DH* graphs as the duals of distance-hereditary graphs.
Keywords:
distance-hereditary graph, dual graph, graph duality

Links:
PDF