Scholarlink

A graph is called a pairwise compatibility graph (PCG) if there exists an edge-weighted tree where each leaf corresponds to a vertex of the graph, and an edge \({u,v}\) exists in the graph if and only if the weight of the path connecting the leaves u and v in the tree falls within a specified interval. PCGs have been extensively studied, and numerous subclasses and generalizations have been introduced, expanding their applicability and theoretical interest. In this survey, we briefly review the existing results on these variants of PCGs and highlight several intriguing open problems, focusing on the main challenges and potential directions for future research.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

On Variants of PCGs: A Survey of Current Results and Open Problems

  • 章节

  • 发表日期：

    2025年

查看全文
  • Tiziana Calamoneri,
  • Angelo Monti,
  • Blerina Sinaimeri

摘要

A graph is called a pairwise compatibility graph (PCG) if there exists an edge-weighted tree where each leaf corresponds to a vertex of the graph, and an edge \({u,v}\) exists in the graph if and only if the weight of the path connecting the leaves u and v in the tree falls within a specified interval. PCGs have been extensively studied, and numerous subclasses and generalizations have been introduced, expanding their applicability and theoretical interest. In this survey, we briefly review the existing results on these variants of PCGs and highlight several intriguing open problems, focusing on the main challenges and potential directions for future research.