Triangle-Free Outerplanar 3-Graphs are Pairwise Compatibility Graphs
Sammi Abida Salma, Md. Saidur Rahman, Md. Iqbal Hossain · 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.