Pairwise compatibility graph
In graph theory, a graph G is a pairwise compatibility graph (PCG) if there exists a weighted tree T and two non-negative real numbers d_{min} \leq d_{max} such that each node u' of G has a one-to-one mapping with a leaf node u of T such…
≈ 1 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In graph theory, a graph G is a pairwise compatibility graph (PCG) if there exists a weighted tree T and two non-negative real numbers d_{min} \leq d_{max} such that each node u' of G has a one-to-one mapping with a leaf node u of T such that two nodes u' and v' are adjacent in G if and only if the distance between u and v are in the interval [d_{min}, d_{max}] . The subclasses of PCG include graphs of at most seven vertices, cycles, forests, complete graphs, interval graphs and ladder graphs.
However, there is a graph with eight vertices that is known not to be a PCG.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1364684176 under CC BY-SA 4.0; modifications have been made.