Search

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)\to\mathbb{N}_0$, the non-negative integer pairwise compatibility graph $\textrm{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 $\textrm{nniPCG}(T,\lambda,2,2)$ if and only if its point-determining quotient $G/\!\rthin$ is a block graph, where two vertices are in relation $\rthin$ 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.

Phylogenetic networks are a generalization of phylogenetic trees allowing for the representation of non-treelike evolutionary events such as hybridization. Typically, such networks have been analyzed based on their `level', i.e. based on the complexity of their 2-edge-connected components. However, recently the question of how `treelike' a phylogenetic network is has become the center of attention in various studies. This led to the introduction of \emph{tree-based networks}, i.e. networks that can be constructed from a phylogenetic tree, called the \emph{base tree}, by adding additional edges. While the concept of tree-basedness was originally introduced for rooted phylogenetic networks, it has recently also been considered for unrooted networks. In the present study, we compare and contrast findings obtained for unrooted \emph{binary} tree-based networks to unrooted \emph{non-binary} networks. In particular, while it is known that up to level 4 all unrooted binary networks are tree-based, we show that in the case of non-binary networks, this result only holds up to level 3.

Recently, so-called treebased phylogenetic networks have gained considerable interest in the literature, where a treebased network is a network that can be constructed from a phylogenetic tree, called the base tree, by adding additional edges. The main aim of this manuscript is to provide some sufficient criteria for treebasedness by reducing phylogenetic networks to related graph structures. While it is generally known that deciding whether a network is treebased is NP-complete, one of these criteria, namely edgebasedness, can be verified in linear time. Surprisingly, the class of edgebased networks is closely related to a well-known family of graphs, namely the class of generalized series parallel graphs, and we will explore this relationship in full detail. Additionally, we introduce further classes of treebased networks and analyze their relationships., Comment: 45 pages, 26 figures

In Chapter 1 we fully characterise pairs of finite graphs which form a gap in the full homomorphism order. This leads to a simple proof of the existence of generalised duality pairs. We also discuss how such results can be carried to relational structures with unary and binary relations. In Chapter 2 we show a very simple and versatile argument based on divisibility which immediately yields the universality of the homomorphism order of directed graphs and discuss three applications. In chapter 3, we show that every interval in the homomorphism order of finite undirected graphs is either universal or a gap. Together with density and universality this "fractal" property contributes to the spectacular properties of the homomorphism order. In Chapter 4 we analyze the phylogenetic information content from a combinatorial point of view by considering the binary relation on the set of taxa defined by the existence of a single event separating two taxa. We show that the graph-representation of this relation must be a tree. Moreover, we characterize completely the relationship between the tree of such relations and the underlying phylogenetic tree., Comment: dissertation, School of Mathematical Sciences, Shanghai Jiaotong University, Sep 2017

The symmetric version of Fitch's xenology relation coincides with class of complete multipartite graph and thus cannot convey any non-trivial phylogenetic information.

Letters $x$ and $y$ alternate in a word $w$ if after deleting in $w$ all letters but the copies of $x$ and $y$ we either obtain a word $xyxy\cdots$ (of even or odd length) or a word $yxyx\cdots$ (of even or odd length). A graph $G=(V,E)$ is word-representable if and only if there exists a word $w$ over the alphabet $V$ such that letters $x$ and $y$ alternate in $w$ if and only if $xy\in E$. It is known that a graph is word-representable if and only if it admits a certain orientation called semi-transitive orientation. Word-representable graphs generalize several important classes of graphs such as $3$-colorable graphs, circle graphs, and comparability graphs. There is a long line of research in the literature dedicated to word-representable graphs. However, almost nothing is known on word-representability of split graphs, that is, graphs in which the vertices can be partitioned into a clique and an independent set. In this paper, we shed a light to this direction. In particular, we characterize in terms of forbidden subgraphs word-representable split graphs in which vertices in the independent set are of degree at most 2, or the size of the clique is 4. Moreover, we give necessary and sufficient conditions for an orientation of a split graph to be semi-transitive.

We characterise gaps in the full homomorphism order of graphs., Comment: 9 pages, extended abstract for Eurocomb 2017

In 1998, B\"{o}cker and Dress gave a 1-to-1 correspondence between symbolically dated rooted trees and symbolic ultrametrics. We consider the corresponding problem for unrooted trees. More precisely, given a tree $T$ with leaf set $X$ and a proper vertex colouring of its interior vertices, we can map every triple of three different leaves to the colour of its median vertex. We characterise all ternary maps that can be obtained in this way in terms of 4- and 5-point conditions, and we show that the corresponding tree and its colouring can be reconstructed from a ternary map that satisfies those conditions. Further, we give an additional condition that characterises whether the tree is binary, and we describe an algorithm that reconstructs general trees in a bottom-up fashion.

Rare events have played an increasing role in molecular phylogenetics as potentially homoplasy-poor characters.In this contribution we analyze the phylogenetic information content from a combinatorial point of view by consid-ering the binary relation on the set of taxa defined by the existence of a single event separating two taxa. We showthat the graph-representation of this relation must be a tree. Moreover, we characterize completely the relationshipbetween the tree of such relations and the underlying phylogenetic tree. With directed operations such as tandem-duplication-random-loss events in mind we demonstrate how non-symmetric information constrains the position ofthe root in the partially reconstructed phylogeny.

We show that every interval in the homomorphism order of finite undirected graphs is either universal or a gap. Together with density and universality this "fractal" property contributes to the spectacular properties of the homomorphism order. We first show the fractal property by using Sparse Incomparability Lemma and then by more involved elementary argument., Comment: 8 pages, 5 figures. Minor corrections and reformatting. Accepted to European Journal of Combinatorics

We consider constrained variants of graph homomorphisms such as embeddings, monomorphisms, full homomorphisms, surjective homomorpshims, and locally constrained homomorphisms. We also introduce a new variation on this theme which derives from relations between graphs and is related to multihomomorphisms. This gives a generalization of surjective homomorphisms and naturally leads to notions of R-retractions, R-cores, and R-cocores of graphs. Both R-cores and R-cocores of graphs are unique up to isomorphism and can be computed in polynomial time. The theory of the graph homomorphism order is well developed, and from it we consider analogous notions defined for orders induced by constrained homomorphisms. We identify corresponding cores, prove or disprove universality, characterize gaps and dualities. We give a new and significantly easier proof of the universality of the homomorphism order by showing that even the class of oriented cycles is universal. We provide a systematic approach to simplify the proofs of several earlier results in this area. We explore in greater detail locally injective homomorphisms on connected graphs, characterize gaps and show universality. We also prove that for every $d\geq 3$ the homomorphism order on the class of line graphs of graphs with maximum degree $d$ is universal.

We prove that for every $d\geq 3$ the homomorphism order of the class of line graphs of finite graphs with maximal degree $d$ is universal. This means that every finite or countably infinite partially ordered set may be represented by line graphs of graphs with maximal degree $d$ ordered by the existence of a homomorphism., Comment: 13 pages, 8 figures, accepted to European Journal of Combinatorics

Given two graphs G and H, we ask under which conditions there is a relation R that generates the edges of H given the structure of graph G. This construction can be seen as a form of multihomomorphism. It generalizes surjective homomorphisms of graphs and naturally leads to notions of R-retractions, R-cores, and R-cocores of graphs. Both R-cores and R-cocores of graphs are unique up to isomorphism and can be computed in polynomial time., Comment: accepted by Ars Mathematica Contemporanea