A method for enumerating pairwise compatibility graphs with a given number of vertices

DOI10.1016/j.dam.2020.08.016zbMath1472.05068OpenAlexW3081670308MaRDI QIDQ1983131

Hiroshi Nagamochi, Naveed Ahmed Azam, Aleksandar Shurbevski

Publication date: 15 September 2021

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

Full work available at URL: https://doi.org/10.1016/j.dam.2020.08.016

zbMATH Keywords

branch-and-bound algorithmlinear programminggraph isomorphismpairwise compatibility graphGale's theorem

Mathematics Subject Classification ID

Linear programming (90C05) Enumeration in graph theory (05C30) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (3)

New results on pairwise compatibility graphs ⋮ On the enumeration of minimal non-pairwise compatibility graphs ⋮ On the enumeration of minimal non-pairwise compatibility graphs

Uses Software

• nauty
• Traces

Cites Work

• Pairwise compatibility graphs
• Exploring pairwise compatibility graphs
• Some classes of graphs that are not PCGs
• Some reduction operations to pairwise compatibility graphs
• Practical graph isomorphism. II.
• On graphs that are not PCGs
• Pairwise Compatibility Graphs: A Survey
• Unnamed Item

This page was built for publication: A method for enumerating pairwise compatibility graphs with a given number of vertices