Homogeneously orderable graphs

AbstractIn this paper we introduce homogeneously orderable graphs which are a common generalization of distance-hereditary graphs, dually chordal graphs and homogeneous graphs. We present a characterization of the new class in terms of a tree structure of the closed neighborhoods of homogeneous sets in 2-graphs which is closely related to the defining elimination ordering.Moreover, we characterize the hereditary homogeneously orderable graphs by forbidden induced subgraphs as the house-hole-domino-sun-free graphs.The local structure of homogeneously orderable graphs implies a simple polynomial-time recognition algorithm for these graphs.Finally, we give a polynomial-time solution for the Steiner tree problem on homogeneously orderable graphs which extends the efficient solutions of that problem on distance-hereditary graphs, dually chordal graphs and homogeneous graphs