DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


Authors:

T.A. McKee

Title:

Dualizing distance-hereditary graphs

Source:

Discussiones Mathematicae Graph Theory

Received: 2018-05-04, Revised: 2018-10-23, Accepted: 2018-10-23, https://doi.org/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

PDF
Close