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 in V and there is an edge (u, v) in 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 paper, we focus our attention on PCGs for which the witness tree is a caterpillar. We first give some properties of graphs that are PCGs of a caterpillar. We formulate this problem as an integer linear programming problem and we exploit this formulation to show that for the wheels on n vertices Wn, n = 7, ... , 11, the witness tree cannot be a caterpillar. Related to this result, we conjecture that no wheel is PCG of a caterpillar. Finally, we state a more general result proving that any pairwise compatibility graph admits a full binary tree as witness tree T.

Pairwise Compatibility Graphs of Caterpillars

FRANGIONI, ANTONIO;
2014

Abstract

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 in V and there is an edge (u, v) in 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 paper, we focus our attention on PCGs for which the witness tree is a caterpillar. We first give some properties of graphs that are PCGs of a caterpillar. We formulate this problem as an integer linear programming problem and we exploit this formulation to show that for the wheels on n vertices Wn, n = 7, ... , 11, the witness tree cannot be a caterpillar. Related to this result, we conjecture that no wheel is PCG of a caterpillar. Finally, we state a more general result proving that any pairwise compatibility graph admits a full binary tree as witness tree T.
T., Calamoneri; Frangioni, Antonio; B., Sinamieri
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/11568/209129
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 13
  • ???jsp.display-item.citation.isi??? 13
social impact