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

SINAIMERI, BLERINA
2013

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.
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 Dimensione Formato  
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
Formato Adobe PDF
320.47 kB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11385/202535
Citazioni
  • Scopus 29
  • ???jsp.display-item.citation.isi??? 19
social impact