A graph G 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,w (lu, lv) ≤ dmax, where dT,w (lu, lv) is the sum of the weights of the edges on the unique path from lu to lv in T. In this note, we show that all the graphs with at most seven vertices are PCGs. In particular, all these graphs except for the wheel on seven vertices W 7 are PCGs of a particular structure of a tree: a centipede. © 2012 The Author 2012. Published by Oxford University Press on behalf of The British Computer Society. All rights reserved.

All graphs with at most seven vertices are Pairwise compatibility graphs / Calamoneri, Tiziana; D., Frascaria; Sinaimeri, Blerina. - In: COMPUTER JOURNAL. - ISSN 0010-4620. - 56:7(2013), pp. 882-886. [10.1093/comjnl/bxs087]

All graphs with at most seven vertices are Pairwise compatibility graphs

Abstract

A graph G 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,w (lu, lv) ≤ dmax, where dT,w (lu, lv) is the sum of the weights of the edges on the unique path from lu to lv in T. In this note, we show that all the graphs with at most seven vertices are PCGs. In particular, all these graphs except for the wheel on seven vertices W 7 are PCGs of a particular structure of a tree: a centipede. © 2012 The Author 2012. Published by Oxford University Press on behalf of The British Computer Society. All rights reserved.
Scheda breve Scheda completa Scheda completa (DC)
2013
caterpillar; centipede; pairwise compatibility graphs; wheel
All graphs with at most seven vertices are Pairwise compatibility graphs / Calamoneri, Tiziana; D., Frascaria; Sinaimeri, Blerina. - In: COMPUTER JOURNAL. - ISSN 0010-4620. - 56:7(2013), pp. 882-886. [10.1093/comjnl/bxs087]
File in questo prodotto:
File
The Computer Journal-2012-Calamoneri-comjnl_bxs087.pdf

Solo gestori archivio

Tipologia: Versione dell'editore
Licenza: DRM (Digital rights management) non definiti
Dimensione 320.47 kB
Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11385/202535`