Some classes of graphs that are not PCGs

DOI10.1016/J.TCS.2019.05.017MaRDI QIDQ2272401zbMATH OpenOpenAlexWikidataFDO

Authors Pierluigi Baiocchi, Tiziana Calamoneri, Angelo Monti, Rossella Petreschi

Publication date 10 September 2019

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

Full work available at URL https://arxiv.org/abs/1707.07436

zbMATH Keywords

pairwise compatibility graphs (PCGs)PCG recognition problemphylogenetic tree reconstruction problemsmallest planar not PCGwheel

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Graph theory (05C99)

Abstract: A graph $G=(V,E)$ is a pairwise compatibility graph (PCG) if there exists an edge-weighted tree $T$ and two non-negative real numbers $d_{min}$ and $d_{max}$, $d_{min}leq{d}_{max}$, such that each node $uinV$ is uniquely associated to a leaf of $T$ and there is an edge $(u,v)inE$ if and only if $d_{min}leq{d}_T(u,v)leq{d}_{max}$, where $d_T(u,v)$ is the sum of the weights of the edges on the unique path $P_T(u,v)$ from $u$ to $v$ in $T$. Understanding which graph classes lie inside and which ones outside the PCG class is an important issue. In this paper we propose a new proof technique that allows us to show that some interesting classes of graphs have empty intersection with PCG. As an example, we use this technique to show that wheels and graphs obtained as strong product between a cycle and $P_2$ are not PCGs.

Recommendations

• On graphs that are not PCGs
• On graphs that are not PCGs
• Graphs that are not pairwise compatible: a new proof technique (extended abstract)
• Pairwise compatibility graphs: a survey
• Exploring pairwise compatibility graphs

Cites work

• A necessary condition and a sufficient condition for pairwise compatibility graphs
• DISCOVERING PAIRWISE COMPATIBILITY GRAPHS
• On graphs that are not PCGs
• On pairwise compatibility graphs having Dilworth number k
• On pairwise compatibility graphs having Dilworth number two
• Pairwise compatibility graphs
• Pairwise compatibility graphs: a survey
• Ptolemaic Graphs and Interval Graphs Are Leaf Powers
• Triangle-free outerplanar 3-graphs are pairwise compatibility graphs

Cited in

(12)

• Graphs that are not pairwise compatible: a new proof technique (extended abstract)
• A method for enumerating pairwise compatibility graphs with a given number of vertices
• New results on pairwise compatibility graphs
• Exact-2-relation graphs
• Some reduction operations to pairwise compatibility graphs
• On graphs that are not PCGs
• Triangle-free outerplanar 3-graphs are pairwise compatibility graphs
• On graphs that are not 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
• On generalizations of pairwise compatibility graphs

This page was built for publication: Some classes of graphs that are not PCGs

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