On Threshold Pairwise Compatibility Graphs
Pairwise Compatibility Graphs (PCGs) form a tree-metric graph class that originated in phylogeny and has since attracted sustained interest in graph theory. Several natural generalizations have been proposed in order to overcome the expressive limitations of classical PCGs, including $k$-interval-PCGs, $k$-OR-PCGs, and $k$-AND-PCGs. In this paper, we introduce $(k,t)$-threshold-PCGs, a threshold-based framework that unifies these generalized notions: adjacency is determined by whether at least $t$ among $k$ underlying PCG predicates accept the vertex pair. We investigate the expressive power…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2604.20042
curl -X POST /api/v1/records/arxiv/2604.20042/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.20042/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'