Pairwise compatibility graph

Comment: Hi! Based on the Google Scholar link, the good news is I think this topic meets notability. However, it needs to be expanded and incorporate many of the more well-cited references listed at this link. Currently, it's just a definition and one fact, which IS helpful but needs significant improvement and someone would need to commit to bringing the article to Start class. Caleb Stanford (talk) 03:27, 30 December 2021 (UTC)

A graph $G$ is a Pairwise Compatibility Graph (PCG) if there exists a tree $T$ and two non-negative real numbers $d_{min}<d_{max}$ such that each node $u'$ of $G$ has a one-to-one mapping with a leaf $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}]$ .^[1]

The subclasses of PCG include graphs of at most seven vertices, cycles, forests, complete graphs, interval graphs, etc. The computational complexity of recognizing a graph as PCG is still unknown.^[1]

References

^ ^a ^b Rahman, Md Saidur; Ahmed, Shareef (2020). "A survey on pairwise compatibility graphs". AKCE International Journal of Graphs and Combinatorics. 17 (3): 788–795. doi:10.1016/j.akcej.2019.12.011. S2CID 225708614. Retrieved December 30, 2021. This article incorporates text available under the CC BY 4.0 license.

[:0-1] Rahman, Md Saidur; Ahmed, Shareef (2020). "A survey on pairwise compatibility graphs". AKCE International Journal of Graphs and Combinatorics. 17 (3): 788–795. doi:10.1016/j.akcej.2019.12.011. S2CID 225708614. Retrieved December 30, 2021. This article incorporates text available under the CC BY 4.0 license.

[1]