Geodesic
A Necessary Condition and a Sufficient Condition for Pairwise Compatibility Graphs
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Tenth International Workshop on Algorithms and Computation (WALCOM 2016) , Tome 21 (2017) no. 3, pp. 341-352.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

In this paper we give a necessary condition and a sufficient condition for a graph to be a pairwise compatibility graph (PCG). Let $G$ be a graph and let $G^c$ be the complement of $G$. We show that if $G^c$ has two disjoint chordless cycles then $G$ is not a PCG. On the other hand, if $G^c$ has no cycle then $G$ is a PCG. Our conditions are the first necessary condition and the first sufficient condition for pairwise compatibility graphs in general. We also show that there exist some graphs in the gap of the two conditions which are not PCGs.
DOI : 10.7155/jgaa.00419
Keywords: graph theory, pairwise compatibility graph, bipartite graph, phylogenetic tree, chordless cycle 
@article{JGAA_2017_21_3_a5,
     author = {Md. Iqbal Hossain and Sammi Abida Salma and Md. Saidur Rahman and Debajyoti Mondal},
     title = {A {Necessary} {Condition} and a {Sufficient} {Condition} for {Pairwise} {Compatibility} {Graphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {341--352},
     publisher = {mathdoc},
     volume = {21},
     number = {3},
     year = {2017},
     doi = {10.7155/jgaa.00419},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00419/}
}
TY  - JOUR
AU  - Md. Iqbal Hossain
AU  - Sammi Abida Salma
AU  - Md. Saidur Rahman
AU  - Debajyoti Mondal
TI  - A Necessary Condition and a Sufficient Condition for Pairwise Compatibility Graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2017
SP  - 341
EP  - 352
VL  - 21
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00419/
DO  - 10.7155/jgaa.00419
LA  - en
ID  - JGAA_2017_21_3_a5
ER  - 
%0 Journal Article
%A Md. Iqbal Hossain
%A Sammi Abida Salma
%A Md. Saidur Rahman
%A Debajyoti Mondal
%T A Necessary Condition and a Sufficient Condition for Pairwise Compatibility Graphs
%J Journal of Graph Algorithms and Applications
%D 2017
%P 341-352
%V 21
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00419/
%R 10.7155/jgaa.00419
%G en
%F JGAA_2017_21_3_a5
Md. Iqbal Hossain; Sammi Abida Salma; Md. Saidur Rahman; Debajyoti Mondal. A Necessary Condition and a Sufficient Condition for Pairwise Compatibility Graphs. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the Tenth International Workshop on Algorithms and Computation  (WALCOM 2016)
					, Tome 21 (2017) no. 3, pp. 341-352. doi : 10.7155/jgaa.00419. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00419/

Cité par Sources :