Geodesic
Triangle-Free Outerplanar 3-Graphs are Pairwise Compatibility Graphs
Journal of graph algorithms and applications, Special Issue on Selected Papers from the Sixth International Workshop on Algorithms and Computation, WALCOM 2012 , Tome 17 (2013) no. 2, pp. 81-102 Cet article a éte moissonné depuis la source Journal of Graph Algorythms and Applications website

Voir la notice de l'article

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.
DOI : 10.7155/jgaa.00286
Keywords: Outerplanar 3-Graphs, Pairwise Compatibility Graphs, PCG, edge-weighted tree 
@article{JGAA_2013_17_2_a2,
     author = {Sammi Abida Salma and Md. Saidur Rahman and Md. Iqbal Hossain},
     title = {Triangle-Free {Outerplanar} {3-Graphs} are {Pairwise} {Compatibility} {Graphs}},
     journal = {Journal of graph algorithms and applications},
     pages = {81--102},
     year = {2013},
     volume = {17},
     number = {2},
     doi = {10.7155/jgaa.00286},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00286/}
}
TY  - JOUR
AU  - Sammi Abida Salma
AU  - Md. Saidur Rahman
AU  - Md. Iqbal Hossain
TI  - Triangle-Free Outerplanar 3-Graphs are Pairwise Compatibility Graphs
JO  - Journal of graph algorithms and applications
PY  - 2013
SP  - 81
EP  - 102
VL  - 17
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00286/
DO  - 10.7155/jgaa.00286
LA  - en
ID  - JGAA_2013_17_2_a2
ER  - 
%0 Journal Article
%A Sammi Abida Salma
%A Md. Saidur Rahman
%A Md. Iqbal Hossain
%T Triangle-Free Outerplanar 3-Graphs are Pairwise Compatibility Graphs
%J Journal of graph algorithms and applications
%D 2013
%P 81-102
%V 17
%N 2
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00286/
%R 10.7155/jgaa.00286
%G en
%F JGAA_2013_17_2_a2
Sammi Abida Salma; Md. Saidur Rahman; Md. Iqbal Hossain. Triangle-Free Outerplanar 3-Graphs are Pairwise Compatibility Graphs. Journal of graph algorithms and applications, 
							Special Issue on Selected Papers from the Sixth International Workshop on Algorithms and Computation, WALCOM 2012
					, Tome 17 (2013) no. 2, pp. 81-102. doi: 10.7155/jgaa.00286

Cité par Sources :