Distance-hereditary graphs

From MaRDI portal

Publication:1084114

Jump to:navigation, search

DOI10.1016/0095-8956(86)90043-2zbMath0605.05024OpenAlexW2041910029MaRDI QIDQ1084114

Henry Martyn Mulder, Hans-Jürgen Bandelt

Publication date: 1986

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0095-8956(86)90043-2

zbMATH Keywords

four-point condition distance-hereditary graph block graph isometric subgraph distance forbidden subgraphs

Mathematics Subject Classification ID

Paths and cycles (05C38) Structural characterization of families of graphs (05C75)

Related Items

Alternating cycle-free matchings ⋮ Enumerating minimal connected dominating sets in graphs of bounded chordality ⋮ Pseudo-modular graphs ⋮ A polyhedral investigation of star colorings ⋮ Clique cycle-transversals in distance-hereditary graphs ⋮ Efficient parallel recognition algorithms of cographs and distance hereditary graphs ⋮ Reconstruction of distance hereditary 2-connected graphs ⋮ Structure and linear time recognition of 3-leaf powers ⋮ Weighted efficient domination problem on some perfect graphs ⋮ On the hyperbolicity of bipartite graphs and intersection graphs ⋮ On the null-homotopy of bridged graphs ⋮ Isotropic systems ⋮ Complexity of determining the maximum infection time in the geodetic convexity ⋮ Powers of distance-hereditary graphs ⋮ Notes on a theorem of Naji ⋮ Vertex-minors, monadic second-order logic, and a conjecture by Seese ⋮ Complexity of \(k\)-tuple total and total \(\{k\}\)-dominations for some subclasses of bipartite graphs ⋮ Trees, taxonomy, and strongly compatible multi-state characters ⋮ Characterization and recognition of some opposition and coalition graph classes ⋮ Steiner intervals and Steiner geodetic numbers in distance-hereditary graphs ⋮ Hereditary modular graphs ⋮ On edge perfectness and classes of bipartite graphs ⋮ On hypergraph acyclicity and graph chordality ⋮ Total dominating sequences in trees, split graphs, and under modular decomposition ⋮ A note on distance matrices with unicyclic graph realizations ⋮ Linear rank-width of distance-hereditary graphs II. vertex-minor obstructions ⋮ Networks with small stretch number ⋮ A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion ⋮ A Helly theorem in weakly modular space ⋮ A note on \(r\)-dominating cliques ⋮ Quasi-threshold graphs ⋮ Enumeration and maximum number of minimal connected vertex covers in graphs ⋮ Finding a sun in building-free graphs ⋮ Homogeneously orderable graphs ⋮ A characterization of line graphs that are squares of graphs ⋮ Set graphs. IV. Further connections with claw-freeness ⋮ Fat Hoffman graphs with smallest eigenvalue greater than \(-3\) ⋮ On the hyperbolicity of random graphs ⋮ Weighted maximum-clique transversal sets of graphs ⋮ The maximum infection time in the geodesic and monophonic convexities ⋮ On the geodetic iteration number of distance-hereditary graphs ⋮ Towards an isomorphism dichotomy for hereditary graph classes ⋮ Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs ⋮ A note on connected dominating sets of distance-hereditary graphs ⋮ Subgraph trees in graph theory ⋮ MAD trees and distance-hereditary graphs ⋮ Completely separable graphs ⋮ Proximity and average eccentricity of a graph ⋮ Simple linear-time algorithms for counting independent sets in distance-hereditary graphs ⋮ On factorial properties of chordal bipartite graphs ⋮ Partial characterizations of circle graphs ⋮ The Chen-Chvátal conjecture for metric spaces induced by distance-hereditary graphs ⋮ Clique-width with an inactive label ⋮ Twin subgraphs and core-semiperiphery-periphery structures ⋮ (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization. ⋮ Forests and trees among Gallai graphs ⋮ Representations of graphs and networks (coding, layouts and embeddings) ⋮ Dominating induced matchings for \(P_7\)-free graphs in linear time ⋮ A parity domination problem in graphs with bounded treewidth and distance-hereditary graphs ⋮ Metric characterization of parity graphs ⋮ Pseudo-median graphs: Decomposition via amalgamation and Cartesian multiplication ⋮ Geodetic and Steiner geodetic sets in 3-Steiner distance hereditary graphs ⋮ \textsc{Max-Cut} parameterized above the Edwards-Erdős bound ⋮ Compatible decompositions and block realizations of finite metrics ⋮ Polynomial time recognition of squares of Ptolemaic graphs and 3-sun-free split graphs ⋮ New results on Ptolemaic graphs ⋮ Coloring graphs without fan vertex-minors and graphs without cycle pivot-minors ⋮ Extremal perfect graphs for a bound on the domination number ⋮ Polyhedral studies of vertex coloring problems: the standard formulation ⋮ Polynomial time algorithms for Hamiltonian problems on bipartite distance-hereditary graphs ⋮ Recognizing locally equivalent graphs ⋮ On distance-preserving elimination orderings in graphs: complexity and algorithms ⋮ Linear rank-width of distance-hereditary graphs. I. A polynomial-time algorithm ⋮ Distance-hereditary graphs and signpost systems ⋮ Distance-hereditary comparability graphs ⋮ Helly theorems for 3-Steiner and 3-monophonic convexity in graphs ⋮ Rooted directed path graphs are leaf powers ⋮ Characterising \((k,\ell )\)-leaf powers ⋮ Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width ⋮ \(O(m\log n)\) split decomposition of strongly-connected graphs ⋮ On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width ⋮ Distance-hereditary digraphs ⋮ Boundary properties of graphs for algorithmic graph problems ⋮ On the partial order competition dimensions of chordal graphs ⋮ The induced path transit function and the Pasch axiom ⋮ Isotropic matroids. I: Multimatroids and neighborhoods ⋮ Clique-width of graphs defined by one-vertex extensions ⋮ Excluded vertex-minors for graphs of linear rank-width at most \(k\) ⋮ Cover-incomparability graphs of posets ⋮ Weighted connected domination and Steiner trees in distance-hereditary graphs ⋮ On an extension of distance hereditary graphs ⋮ A graph-theoretical invariant of topological spaces ⋮ Laminar structure of ptolemaic graphs with applications ⋮ (\(k,+\))-distance-hereditary graphs ⋮ Chordal bipartite graphs of bounded tree- and clique-width ⋮ A forbidden induced subgraph characterization of distance-hereditary 5-leaf powers ⋮ Eccentricity function in distance-hereditary graphs ⋮ Block duplicate graphs and a hierarchy of chordal graphs ⋮ Clique graphs and Helly graphs ⋮ Hyperbolic bridged graphs ⋮ Functionality of box intersection graphs ⋮ On the Advice Complexity of Online Edge- and Node-Deletion Problems ⋮ The Weisfeiler-Leman dimension of distance-hereditary graphs ⋮ Make a graph singly connected by edge orientations ⋮ Efficient enumeration of non-isomorphic distance-hereditary graphs and related graphs ⋮ First-order logic axiomatization of metric graph theory ⋮ On computing the Galois lattice of bipartite distance hereditary graphs ⋮ A tight relation between series-parallel graphs and bipartite distance hereditary graphs ⋮ Distance approximating spanning trees ⋮ Decycling with a matching ⋮ Dominating cliques in distance-hereditary graphs ⋮ A divide-and-conquer approach for reconstruction of \(\{C_{ \geq 5}\}\)-free graphs via betweenness queries ⋮ Extremal cubic graphs for fault-tolerant locating domination ⋮ Injective hulls of various graph classes ⋮ Symmetric graph-theoretic roles of two-pairs and chords of cycles ⋮ Applying clique-decomposition for computing Gromov hyperbolicity ⋮ The use of a pruned modular decomposition for \textsc{maximum matching} algorithms on some graph classes ⋮ Rank-width: algorithmic and structural results ⋮ On Strict (Outer-)Confluent Graphs ⋮ Grammars and clique-width bounds from split decompositions ⋮ An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion ⋮ Characterizing k-chordal unichord-free graphs ⋮ Lattices of regular closed subsets of closure spaces ⋮ New graph classes characterized by weak vertex separators and two-pairs ⋮ Mutual visibility in graphs ⋮ A linear-time algorithm for the identifying code problem on block graphs ⋮ On the Galois Lattice of Bipartite Distance Hereditary Graphs ⋮ On polygon numbers of circle graphs and distance hereditary graphs ⋮ Completion to chordal distance-hereditary graphs: a quartic vertex-kernel ⋮ Linear-time algorithms for three domination-based separation problems in block graphs ⋮ On some graph classes related to perfect graphs: a survey ⋮ Graph reconstruction in the congested clique ⋮ A polynomial kernel for 3-leaf power deletion ⋮ On stability of spanning tree degree enumerators ⋮ Unique response Roman domination: complexity and algorithms ⋮ On the general position numbers of maximal outerplane graphs ⋮ Improved approximation algorithms for hitting 3-vertex paths ⋮ On Strong Tree-Breadth ⋮ The axiomatic characterization of the interval function of distance hereditary graphs ⋮ Twin-distance-hereditary digraphs ⋮ Exact-2-relation graphs ⋮ Probe Ptolemaic Graphs ⋮ Variations of maximum-clique transversal sets on graphs ⋮ Requiring adjacent chords in cycles ⋮ Obstructions for linear rank-width at most 1 ⋮ Graphs of small rank-width are pivot-minors of graphs of small tree-width ⋮ Dualizing distance-hereditary graphs ⋮ A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs ⋮ LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem ⋮ On the complexity of the black-and-white coloring problem on some classes of perfect graphs ⋮ Which distance-hereditary graphs are cover-incomparability graphs? ⋮ Dynamic Distance Hereditary Graphs Using Split Decomposition ⋮ Homogeneous sets and domination: A linear time algorithm for distance?hereditary graphs ⋮ 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 ⋮ Online node- and edge-deletion problems with advice ⋮ The \(b\)-\textsc{Matching} problem in distance-hereditary graphs and beyond ⋮ Exploring the complexity boundary between coloring and list-coloring ⋮ NP-hard graph problems and boundary classes of graphs ⋮ Using Split Composition to Extend Distance-Hereditary Graphs in a Generative Way ⋮ Maximal Matching and Path Matching Counting in Polynomial Time for Graphs of Bounded Clique Width ⋮ Bipartite almost distance-hereditary graphs ⋮ Equistable distance-hereditary graphs ⋮ Graphs with bounded induced distance ⋮ Paired-domination problem on distance-hereditary graphs ⋮ The Hamiltonian problem on distance-hereditary graphs ⋮ Distance-hereditary graphs are clique-perfect ⋮ Distance Hereditary Graphs and the Interlace Polynomial ⋮ Weighted connected \(k\)-domination and weighted \(k\)-dominating clique in distance-hereditary graphs ⋮ A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs ⋮ False-twin-free graphs with a fixed number of negative eigenvalues ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Domination in distance-hereditary graphs ⋮ Dominating sets reconfiguration under token sliding ⋮ Polynomial Time Algorithms for Computing a Minimum Hull Set in Distance-Hereditary and Chordal Graphs ⋮ Steiner Wiener index of block graphs ⋮ On the non-commuting graph of dihedral group ⋮ A polynomial kernel for distance-hereditary vertex deletion ⋮ Ptolemaic Graphs and Interval Graphs Are Leaf Powers ⋮ Vertex deletion on split graphs: beyond 4-hitting set ⋮ Graph functionality ⋮ Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs ⋮ Minimum Eccentricity Shortest Paths in Some Structured Graph Classes ⋮ Modular decomposition of graphs and the distance preserving property ⋮ A note on the triameter of graphs ⋮ Linear-time algorithm for the matched-domination problem in cographs ⋮ Characterizations of Graphs with Stretch Number less than 2 ⋮ Generalizations of the matching polynomial to the multivariate independence polynomial ⋮ Rank-width and vertex-minors ⋮ Self-spanner graphs ⋮ Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs ⋮ Rebuilding convex sets in graphs ⋮ Requiring chords in cycles ⋮ Computing maximum stable sets for distance-hereditary graphs ⋮ On an edge partition and root graphs of some classes of line graphs ⋮ On the spectrum and number of convex sets in graphs ⋮ Fast and simple algorithms for counting dominating sets in distance-hereditary graphs ⋮ Solutions of a problem of Ore on spanning trees and its generalization ⋮ Extended Distance-Hereditary Graphs ⋮ The bi-join decomposition ⋮ On an extension of distance-hereditary graphs ⋮ On the Galois lattice of bipartite distance hereditary graphs ⋮ Conflict-free coloring: graphs of bounded clique width and intersection graphs

Cites Work

This page was built for publication: Distance-hereditary graphs

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:1084114&oldid=13107825"