Exact-2-relation graphs

DOI10.1016/J.DAM.2020.05.015MaRDI QIDQ2197422zbMATH OpenOpenAlexFDO

Authors Yangjing Long, Peter F. Stadler

Publication date 31 August 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

block graphsedge-labeled treesoriented graphspairwise compatibility graphsthin graphs

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12) Directed graphs (digraphs), tournaments (05C20) Applications of graph theory (05C90) Genetics and epigenetics (92D10)

Abstract: Pairwise compatibility graphs (PCGs) with non-negative integer edge weights recently have been used to describe rare evolutionary events and scenarios with horizontal gene transfer. Here we consider the case that vertices are separated by exactly two discrete events: Given a tree $T$ with leaf set $L$ and edge-weights $lambda:E(T)omathbb{N}_0$, the non-negative integer pairwise compatibility graph $extrmnniPCG(T,lambda,2,2)$ has vertex set $L$ and $xy$ is an edge whenever the sum of the non-negative integer weights along the unique path from $x$ to $y$ in $T$ equals $2$. A graph $G$ has a representation as $extrmnniPCG(T,lambda,2,2)$ if and only if its point-determining quotient $G/!thin$ is a block graph, where two vertices are in relation $thin$ if they have the same neighborhood in $G$. If $G$ is of this type, a labeled tree $(T,lambda)$ explaining $G$ can be constructed efficiently. In addition, we consider an oriented version of this class of graphs.

Recommendations

• A survey on pairwise compatibility graphs
• Pairwise compatibility graphs
• Pairwise compatibility graphs: a survey
• Pairwise Compatibility Graphs
• Exploring pairwise compatibility graphs

Cites work

• A Characterization of Block-Graphs
• A necessary condition and a sufficient condition for pairwise compatibility graphs
• A note on the tree realizability of a distance matrix
• A short note on undirected Fitch graphs
• Basic phylogenetic combinatorics.
• Cardinal multiplication of structures with a reflexive relation
• Cluster graph modification problems
• Distance-hereditary graphs
• Enumeration of point-determining graphs
• Enumeration of unlabelled mating graphs
• Exact leaf powers
• Exploring pairwise compatibility graphs
• Factoring cardinal product graphs in polynomial time
• Fully dynamic recognition algorithm and certificate for directed cographs
• Graph modification problem for some classes of graphs
• Graphs that are not pairwise compatible: a new proof technique (extended abstract)
• Handbook of product graphs
• scientific article; zbMATH DE number 1865935 (Why is no real title available?)
• Inferring phylogenetic trees from the knowledge of rare evolutionary events
• Multi-interval pairwise compatibility graphs (extended abstract)
• NP-completeness results for edge modification problems
• On graph powers for leaf-labeled trees
• On the tandem duplication-random loss model of genome rearrangement
• Orthology relations, symbolic ultrametrics, and cographs
• Pairwise compatibility graphs
• Pairwise compatibility graphs: a survey
• Point determination in graphs
• Ptolemaic Graphs and Interval Graphs Are Leaf Powers
• Reconstructing gene trees from Fitch's xenology relation
• Some classes of graphs that are not PCGs
• Triangle-free outerplanar 3-graphs are pairwise compatibility graphs

Cited in

(5)

• New results on pairwise compatibility graphs
• On star-multi-interval pairwise compatibility graphs
• On generalizations of pairwise compatibility graphs
• On star-k-PCGs: exploring class boundaries for small k values
• k-leaf powers cannot be characterized by a finite set of forbidden induced subgraphs for k 5

This page was built for publication: Exact-2-relation graphs

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