Publications - Working papers
Please find below working papers of our group. Currently, we list 58 working papers.
In the list are only not published papers present. If you look for a preprint of an already published paper you must look in the "Published papers" section.
If you have problems accessing electronic information, please let us know:
©NOTICE: All working papers are copyrighted by the authors; If you would like to use all or a portion of any paper, please contact the author.
Exact-$2$-Relation Graphs
Yangjing Long, Peter F. Stadler
Download
[ PDF ]
Status: Submitted
Discr. Appl. Math.
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)->N_0, the non-negative integer pairwise compatibility graph nniPCG(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 nniPCG(T,\lambda,2,2) if and only if its point-determining quotient G/~ is a block graph, where two vertices are in relation ~ 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.
Keywords
Pairwise compatibility graphs, edge-labeled trees, thin graphs, block graphs, oriented graphs