On graphs that are not PCGs

DOI10.1016/j.tcs.2015.01.011zbMath1306.05085MaRDI QIDQ2512661

Debajyoti Mondal, Md. Saidur Rahman, Stephane Durocher

Publication date: 30 January 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.01.011

zbMATH Keywords

leaf powers; pairwise compatibility graph; tree-based distance metric

Mathematics Subject Classification ID

05C12: Distance in graphs

05C22: Signed and weighted graphs

Related Items

A survey on pairwise compatibility graphs, Characterizing star-PCGs, A Necessary Condition and a Sufficient Condition for Pairwise Compatibility Graphs, On the enumeration of minimal non-pairwise compatibility graphs, On the enumeration of minimal non-pairwise compatibility graphs, A method for enumerating pairwise compatibility graphs with a given number of vertices, New results on pairwise compatibility graphs, Some classes of graphs that are not PCGs, Some reduction operations to pairwise compatibility graphs, Pairwise compatibility graphs: complete characterization for wheels, Multi-interval Pairwise Compatibility Graphs, Pairwise Compatibility Graphs: A Survey

Cites Work

• Strictly chordal graphs are leaf powers
• Rooted directed path graphs are leaf powers
• Characterising \((k,\ell )\)-leaf powers
• Exact leaf powers
• Pairwise compatibility graphs
• On pairwise compatibility graphs having Dilworth number \(k\)
• On pairwise compatibility graphs having Dilworth number two
• On Graph Powers for Leaf-Labeled Trees
• On Relaxing the Constraints in Pairwise Compatibility Graphs
• DISCOVERING PAIRWISE COMPATIBILITY GRAPHS
• Leaf Powers and Their Properties: Using the Trees
• Triangle-Free Outerplanar 3-Graphs are Pairwise Compatibility Graphs
• On Graphs That Are Not PCGs
• The complexity of satisfiability problems
• On Dilworth k Graphs and Their Pairwise Compatibility