A characterization of ptolemaic graphs
From MaRDI portal
Publication:3877730
DOI10.1002/jgt.3190050314zbMath0437.05046OpenAlexW2020674756WikidataQ29398583 ScholiaQ29398583MaRDI QIDQ3877730
Publication date: 1981
Published in: Journal of Graph Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/jgt.3190050314
shortest pathundirected graphminimal cutsettriangulated graphptolemaic graphsHusimi treesmetric space associated with an undirected graphptolemaic inequality
Related Items (51)
Distance-hereditary graphs ⋮ Tree spanners on chordal graphs: complexity and algorithms ⋮ The recognition of geodetically connected graphs ⋮ When every k-cycle has at least f(k) chords ⋮ Ptolemaic and chordal cover-incomparability graphs ⋮ Convexity in Graphs and Hypergraphs ⋮ Reconstruction of distance hereditary 2-connected graphs ⋮ The structure of the centroid in a Ptolemaic graph ⋮ Towards constant-factor approximation for chordal/distance-hereditary vertex deletion ⋮ Powers of distance-hereditary graphs ⋮ A note on path domination ⋮ Towards a characterization of leaf powers by clique arrangements ⋮ The center and the distance center of a Ptolemaic graph ⋮ On hypergraph acyclicity and graph chordality ⋮ Algorithms for deletion problems on split graphs ⋮ Good characterizations and linear time recognition for 2-probe block graphs ⋮ Ptolemaic and planar cover-incomparability graphs ⋮ A note on sparseness conditions on chordless vertices of cycles ⋮ On polygon numbers of circle graphs and distance hereditary graphs ⋮ Completion to chordal distance-hereditary graphs: a quartic vertex-kernel ⋮ On the geodetic iteration number of distance-hereditary graphs ⋮ Axiomatic characterizations of Ptolemaic and chordal graphs ⋮ Probe Ptolemaic Graphs ⋮ Efficient enumeration of non-isomorphic distance-hereditary graphs and related graphs ⋮ First-order logic axiomatization of metric graph theory ⋮ Intersection of longest paths in graph classes ⋮ Forests and trees among Gallai graphs ⋮ Representations of graphs and networks (coding, layouts and embeddings) ⋮ Finding a minimum path cover of a distance-hereditary graph in polynomial time ⋮ Recognition of Probe Ptolemaic Graphs ⋮ Efficient enumeration of non-isomorphic distance-hereditary graphs and Ptolemaic graphs ⋮ Enumerations, forbidden subgraph characterizations, and the split-decomposition ⋮ Geodetic and Steiner geodetic sets in 3-Steiner distance hereditary graphs ⋮ Polynomial time recognition of squares of Ptolemaic graphs and 3-sun-free split graphs ⋮ New results on Ptolemaic graphs ⋮ CHARACTERISTIC PROPERTIES AND RECOGNITION OF GRAPHS IN WHICH GEODESIC AND MONOPHONIC CONVEXITIES ARE EQUIVALENT ⋮ Peakless functions on graphs ⋮ Extremal perfect graphs for a bound on the domination number ⋮ Some new classes of open distance-pattern uniform graphs ⋮ On the strong chromatic index and maximum induced matching of tree-cographs, permutation graphs and chordal bipartite graphs ⋮ Rooted directed path graphs are leaf powers ⋮ Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width ⋮ Restricted unimodular chordal graphs ⋮ On metric properties of certain clique graphs ⋮ On the Steiner, geodetic and hull numbers of graphs ⋮ Graph theory (algorithmic, algebraic, and metric problems) ⋮ Cycle Extendability of Hamiltonian Strongly Chordal Graphs ⋮ Ptolemaic Graphs and Interval Graphs Are Leaf Powers ⋮ Laminar structure of ptolemaic graphs with applications ⋮ Rebuilding convex sets in graphs ⋮ Clique graphs and Helly graphs
Cites Work
This page was built for publication: A characterization of ptolemaic graphs
