On the enumeration of minimal non-pairwise compatibility graphs

DOI10.1007/S10878-021-00799-XMaRDI QIDQ5918527zbMATH OpenOpenAlexFDO

Authors Naveed Ahmed Azam, Aleksandar Shurbevski, Hiroshi Nagamochi

Publication date 18 October 2022

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-021-00799-x

zbMATH Keywords

branch-and-bound algorithmlinear programmingpairwise compatibility graph

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• On the enumeration of minimal non-pairwise compatibility graphs
• A method for enumerating pairwise compatibility graphs with a given number of vertices
• On the graph complement conjecture for minimum rank
• Minimal comparability completions of arbitrary graphs
• Graphs that are not pairwise compatible: a new proof technique (extended abstract)
• The minimum number of subgraphs in a graph and its complement
• On Dilworth \(k\) graphs and their pairwise compatibility
• Minimal dominating sets in graph classes: combinatorial bounds and enumeration
• Minimal dominating sets in graph classes: combinatorial bounds and enumeration
• On pairwise compatibility graphs having Dilworth number \(k\)

Cites work

• scientific article; zbMATH DE number 3185418 (Why is no real title available?)
• A method for enumerating pairwise compatibility graphs with a given number of vertices
• DISCOVERING PAIRWISE COMPATIBILITY GRAPHS
• Exploring pairwise compatibility graphs
• On graphs that are not PCGs
• On the enumeration of minimal non-pairwise compatibility graphs
• Pairwise compatibility graphs: a survey
• Practical graph isomorphism. II.
• Some classes of graphs that are not PCGs
• Some reduction operations to pairwise compatibility graphs

Cited in

(3)

• A method for enumerating pairwise compatibility graphs with a given number of vertices
• Minimal comparability completions of arbitrary graphs
• Combinatorial relaxation algorithm for the entire sequence of the maximum degree of minors

Describes a project that uses

Uses Software

• Traces
• nauty

This page was built for publication: On the enumeration of minimal non-pairwise compatibility graphs

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