Home Issues About JGAA Instructions for Authors
 
 
Special Issue on Selected Papers from the Sixth International Workshop on Algorithms and Computation, WALCOM 2012
DOI: 10.7155/jgaa.00286
Triangle-Free Outerplanar 3-Graphs are Pairwise Compatibility Graphs
Vol. 17, no. 2, pp. 81-102, 2013. Regular paper.
Abstract 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.
Submitted: April 2012.
Reviewed: July 2012.
Revised: December 2012.
Accepted: December 2012.
Final: December 2012.
Published: January 2013.
Communicated by Shin-ichi Nakano
article (PDF)
BibTeX