Home  Issues  Aims and Scope  Instructions for Authors 
Special Issue on Selected Papers from the Sixth International Workshop on Algorithms and Computation, WALCOM 2012
DOI: 10.7155/jgaa.00286
TriangleFree Outerplanar 3Graphs are Pairwise Compatibility Graphs
Vol. 17, no. 2, pp. 81102, 2013. Regular paper.
Abstract A graph G = (V,E) is called a pairwise compatibility graph (PCG) if there exists an edgeweighted tree T and two nonnegative real numbers d_{min} and d_{max} 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 d_{min} ≤ d_{T}(u, v) ≤ d_{max} in T. Here, d_{T}(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 trianglefree outerplanar graphs with the maximum degree 3 are PCGs.

Submitted: April 2012.
Reviewed: July 2012.
Revised: December 2012.
Accepted: December 2012.
Final: December 2012.
Published: January 2013.
Communicated by
Shinichi Nakano
