{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T16:32:17Z","timestamp":1762101137746},"reference-count":5,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2010,12]]},"abstract":"<jats:p> Let T be an edge weighted tree, let d<jats:sub>T<\/jats:sub>(u, v) be the sum of the weights of the edges on the path from u to v in T, and let d<jats:sub> min <\/jats:sub> and d<jats:sub> max <\/jats:sub> be two non-negative real numbers such that d<jats:sub> min <\/jats:sub> \u2264 d<jats:sub> max <\/jats:sub>. Then a pairwise compatibility graph of T for d<jats:sub> min <\/jats:sub> and d<jats:sub> max <\/jats:sub> is a graph G = (V, E), where each vertex u' \u2208 V corresponds to a leaf u of T and there is an edge (u', v') \u2208 E if and only if d<jats:sub> min <\/jats:sub> \u2264 d<jats:sub>T<\/jats:sub>(u, v) \u2264 d<jats:sub> max <\/jats:sub>. A graph G is called a pairwise compatibility graph (PCG) if there exists an edge weighted tree T and two non-negative real numbers d<jats:sub> min <\/jats:sub> and d<jats:sub> max <\/jats:sub> such that G is a pairwise compatibility graph of T for d<jats:sub> min <\/jats:sub> and d<jats:sub> max <\/jats:sub>. Kearney et al. conjectured that every graph is a PCG [3]. In this paper, we refute the conjecture by showing that not all graphs are PCG s . Moreover, we recognize several classes of graphs as pairwise compatibility graphs. We identify two restricted classes of bipartite graphs as PCG. We also show that the well known tree power graphs and some of their extensions are PCGs. <\/jats:p>","DOI":"10.1142\/s1793830910000917","type":"journal-article","created":{"date-parts":[[2011,1,17]],"date-time":"2011-01-17T03:21:26Z","timestamp":1295234486000},"page":"607-623","source":"Crossref","is-referenced-by-count":27,"title":["DISCOVERING PAIRWISE COMPATIBILITY GRAPHS"],"prefix":"10.1142","volume":"02","author":[{"given":"MUHAMMAD NUR","family":"YANHAONA","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, Bangladesh University of Engineering and Technology, Dhaka-1000, Bangladesh"}]},{"given":"MD. SHAMSUZZOHA","family":"BAYZID","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, Bangladesh University of Engineering and Technology, Dhaka-1000, Bangladesh"}]},{"given":"MD. SAIDUR","family":"RAHMAN","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, Bangladesh University of Engineering and Technology, Dhaka-1000, Bangladesh"}]}],"member":"219","published-online":{"date-parts":[[2012,5]]},"reference":[{"key":"rf1","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"2001"},{"key":"rf2","volume-title":"An Introduction to Bioinformatics Algorithms","author":"Jones N. C.","year":"2004"},{"key":"rf4","volume-title":"Introduction to Bioinformatics","author":"Lesk A. M.","year":"2002"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1007\/BF01098364"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1007\/s12190-008-0204-7"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830910000917","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T13:16:08Z","timestamp":1565097368000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830910000917"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,12]]},"references-count":5,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2012,4,6]]},"published-print":{"date-parts":[[2010,12]]}},"alternative-id":["10.1142\/S1793830910000917"],"URL":"https:\/\/doi.org\/10.1142\/s1793830910000917","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,12]]}}}