On relaxing the constraints in pairwise compatibility graphs

DOI10.1007/978-3-642-28076-4_14zbMATH Open1351.05190arXiv1105.2171OpenAlexW1962996173MaRDI QIDQ2889906FDOQ2889906

Authors: Rossella Petreschi, Blerina Sinaimeri, Tiziana Calamoneri 

Publication date: 8 June 2012

Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)

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 $d_{min}$ and $d_{max}$ such that each leaf $l_u$ of $T$ corresponds to a vertex $uinV$ and there is an edge $(u,v)inE$ if and only if $d_{min}leq{d}_T(l_u,l_v)leq{d}_{max}$ where $d_T(l_u,l_v)$ is the sum of the weights of the edges on the unique path from $l_u$ to $l_v$ in $T$. In this paper we analyze the class of PCG in relation with two particular subclasses resulting from the the cases where $dmin=0$ (LPG) and $dmax=+infty$ (mLPG). In particular, we show that the union of LPG and mLPG does not coincide with the whole class PCG, their intersection is not empty, and that neither of the classes LPG and mLPG is contained in the other. Finally, as the graphs we deal with belong to the more general class of split matrogenic graphs, we focus on this class of graphs for which we try to establish the membership to the PCG class.

Full work available at URL: https://arxiv.org/abs/1105.2171

Recommendations

• Exploring pairwise compatibility graphs
• Pairwise compatibility graphs: a survey
• Pairwise compatibility graphs
• Pairwise Compatibility Graphs
• Some reduction operations to pairwise compatibility graphs

zbMATH Keywords

threshold graphsPCGmatrogenic graphsleaf power graph

Mathematics Subject Classification ID

Distance in graphs (05C12) Signed and weighted graphs (05C22) Structural characterization of families of graphs (05C75)

Cited In (14)

• On pairwise compatibility graphs having Dilworth number \(k\)
• Some reduction operations to pairwise compatibility graphs
• A survey on pairwise compatibility graphs
• On graphs that are not PCGs
• Title not available (Why is that?)
• On pairwise compatibility graphs having Dilworth number two
• Pairwise compatibility graphs: a survey
• Pairwise Compatibility Graphs
• On Dilworth \(k\) graphs and their pairwise compatibility
• A Necessary Condition and a Sufficient Condition for Pairwise Compatibility Graphs
• Multi-interval pairwise compatibility graphs (extended abstract)
• Corrigendum to: ``On pairwise compatibility graphs having Dilworth number two
• DISCOVERING PAIRWISE COMPATIBILITY GRAPHS
• Exploring pairwise compatibility graphs

This page was built for publication: On relaxing the constraints in pairwise compatibility graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2889906)