Forbidden configurations and dominating bicliques in undirected 2-quasi best match graphs
Abstract
2-quasi best match graphs (2qBMGs) are directed graphs that capture a notion of close relatedness in phylogenetics. Here, we investigate the underlying undirected graph of a 2qBMG (un2qBMG) and show that it contains neither a path P l nor a cycle C l of length l ≥ 6 as an induced subgraph. This property guarantees the existence of specific vertex decompositions with dominating bicliques that provide further insights into their structure.
Fields of Study & Subjects
Advanced Graph Theory Research
Genomics and Phylogenetic Studies
Complexity and Algorithms in Graphs
Publication details
- Journal / source
- Discrete Applied Mathematics
- Volume
- 383
- Pages
- 308–314
- Publication date
- 9 January 2026
- Language
- EN