Convexity and HHD-Free Graphs

DOI10.1137/S0895480195321718zbMath0916.05060OpenAlexW2006591476MaRDI QIDQ4255812

Andreas Brandstädt, Falk Nicolai, Feodor F. Dragan

Publication date: 27 June 1999

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0895480195321718

zbMATH Keywords

convexityantimatroidchordal graphsconvex geometrylexicographic breadth first searchHHD-free graphsweak bipolarizable graphssemisimplicial orderingdominating clique problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75)

Related Items (34)

Powers of hhd-free graphs^∗ ⋮ Generating and enumerating digitally convex sets of trees ⋮ Induced path transit function, monotone and Peano axioms ⋮ On the geodetic hull number of \(P_{k}\)-free graphs ⋮ Geodetic Convexity Parameters for Graphs with Few Short Induced Paths ⋮ A general framework for path convexities ⋮ Reconstructing trees from digitally convex sets ⋮ Duchet-type theorems for powers of HHD-free graphs ⋮ On the Carathéodory number of interval and graph convexities ⋮ Convex Partitions of Graphs ⋮ Computing the hull and interval numbers in the weakly toll convexity ⋮ On the monophonic convexity in complementary prisms ⋮ Steiner distance and convexity in graphs ⋮ The convexity of induced paths of order three and applications: complexity aspects ⋮ Finding a central vertex in an HHD-free graph ⋮ LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem ⋮ On the contour of graphs ⋮ On the geodeticity of the contour of a graph ⋮ Graphs with a minimal number of convex sets ⋮ On the contour of bipartite graphs ⋮ On finite convexity spaces induced by sets of paths in graphs ⋮ The induced path function, monotonicity and betweenness ⋮ On the Steiner, geodetic and hull numbers of graphs ⋮ Polynomial time algorithm for computing a minimum geodetic set in outerplanar graphs ⋮ Geodetic convexity parameters for \((q, q - 4)\)-graphs ⋮ Polynomial Time Algorithms for Computing a Minimum Hull Set in Distance-Hereditary and Chordal Graphs ⋮ Local Steiner convexity ⋮ On the Convexity of Paths of Length Two in Undirected Graphs ⋮ Steiner intervals, geodesic intervals, and betweenness ⋮ On 3-Steiner simplicial orderings ⋮ Oracles for vertex elimination orderings ⋮ Eccentricity function in distance-hereditary graphs ⋮ Convex geometries over induced paths with bounded length ⋮ On the spectrum and number of convex sets in graphs

This page was built for publication: Convexity and HHD-Free Graphs