Triangle-Free Outerplanar 3-Graphs are Pairwise Compatibility Graphs - Salma, Sammi Abida; Rahman, Md. Saidur; Hossain, Md. Iqbal (Journal of Graph Algorithms and Applications, 2013)
A graph G = (V,E) is called a pairwise compatibility graph (PCG) if there exists an edge-weighted tree T and two non-negative real numbers dmin and dmax such that each vertex u′ ∈ V corresponds to a leaf u of T and there is an edge (u′, v′) ∈ E if and only if dmin ≤ dT(u, v) ≤ dmax in T. Here, dT(u,v) denotes the distance between u and v in T, which is the sum of the weights of the edges on the path from u to v. It is known that not all graphs are PCGs. Thus it is interesting to know which classes of graphs are PCGs. In this paper we show that triangle-free outerplanar graphs with the maximum degree 3 are PCGs.