TY - GEN
T1 - Pairwise compatibility graphs revisited
AU - Mehnaz, Shagufta
AU - Rahman, Md Sohel
PY - 2013
Y1 - 2013
N2 - 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 leaf lu of T corresponds to a vertex u V and there is an edge (u, v) E if and only if dmin ≤ dT(lu, lv) ≤ dmax where d T(lu, lv) is the sum of weights of the edges on the unique path from lu to lv in T. In this note, firstly, we show a class of bipartite graphs not to be PCG, that is, it is not possible to draw a pairwise compatibility tree for these graphs. Further we construct a class of more general non-PCGs each member of which contains a bipartite graph belonging to the class of graphs mentioned above as a subgraph. Secondly, we show by computational means that all the bipartite graphs with at most eight vertices are PCGs. In particular all these graphs are PCGs of a particular structure of tree called centipede.
AB - 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 leaf lu of T corresponds to a vertex u V and there is an edge (u, v) E if and only if dmin ≤ dT(lu, lv) ≤ dmax where d T(lu, lv) is the sum of weights of the edges on the unique path from lu to lv in T. In this note, firstly, we show a class of bipartite graphs not to be PCG, that is, it is not possible to draw a pairwise compatibility tree for these graphs. Further we construct a class of more general non-PCGs each member of which contains a bipartite graph belonging to the class of graphs mentioned above as a subgraph. Secondly, we show by computational means that all the bipartite graphs with at most eight vertices are PCGs. In particular all these graphs are PCGs of a particular structure of tree called centipede.
UR - http://www.scopus.com/inward/record.url?scp=84883331167&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84883331167&partnerID=8YFLogxK
U2 - 10.1109/ICIEV.2013.6572681
DO - 10.1109/ICIEV.2013.6572681
M3 - Conference contribution
AN - SCOPUS:84883331167
SN - 9781479903979
T3 - 2013 International Conference on Informatics, Electronics and Vision, ICIEV 2013
BT - 2013 International Conference on Informatics, Electronics and Vision, ICIEV 2013
T2 - 2013 2nd International Conference on Informatics, Electronics and Vision, ICIEV 2013
Y2 - 17 May 2013 through 18 May 2013
ER -