Graph classes between parity and distance-hereditary graphs

DOI10.1016/S0166-218X(99)00075-XMaRDI QIDQ1302157zbMATH OpenOpenAlexFDO

Authors Serafino Cicerone, Gabriele Di Stefano

Publication date 22 March 2000

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0166-218x(99)00075-x

zbMATH Keywords

graph isomorphismrecognition algorithmsplit decompositiondistance-hereditary graphparity graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Distance in graphs (05C12) Structural characterization of families of graphs (05C75)

Recommendations

• scientific article; zbMATH DE number 1222095
• On the extension of bipartite to parity graphs
• Recognition of probe distance-hereditary graphs
• scientific article; zbMATH DE number 3889564
• Using split composition to extend distance-hereditary graphs in a generative way (extended abstract)

Cited in

(11)

• Practical and efficient split decomposition via graph-labelled trees
• Graphs with bounded induced distance
• Efficient enumeration of non-isomorphic distance-hereditary graphs and related graphs
• (\(k,+\))-distance-hereditary graphs
• Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
• Networks with small stretch number
• A tight relation between series-parallel graphs and bipartite distance hereditary graphs
• Distance-hereditary comparability graphs
• Equistable distance-hereditary graphs
• Using split composition to extend distance-hereditary graphs in a generative way (extended abstract)
• Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs

This page was built for publication: Graph classes between parity and distance-hereditary graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1302157)