Subscribe to Syndicate

Marc Hellmuth

Spiders are arthropods that can be distinguished from their closest relatives, the insects, by counting their legs. Spiders have eight, insects just six. Spider graphs are a very restricted class of graphs that naturally appear in the context of cograph editing. The vertex set of a spider (or its complement) is naturally partitioned into a clique (the body), an independent set (the legs), and a rest (serving as the head). Here we show that spiders can be recognized directly from their degree sequences through the number of their legs (vertices with degree 1).
Phylogenomics heavily relies on well-curated sequence data sets that comprise, for each gene, exclusively 1:1 orthologos. Paralogs are treated as a dangerous nuisance that has to be detected and removed. We show here that this severe restriction of the data sets is not necessary. Building upon recent advances in mathematical phylogenetics, we demonstrate that gene duplications convey meaningful phylogenetic information and allow the inference of plausible phylogenetic trees, provided orthologs and paralogs can be distinguished with a degree of certainty.
This paper is concerned with the fast computation of a relationon the edge set of connected graphs that plays a decisive role in the recognition of approximate Cartesian products, the weak reconstruction of Cartesian products, and the recognition of Cartesian graph bundles with a triangle free basis. A special case ofis the relation, whose convex closure yields the product relation that induces the prime factor decomposition of connected graphs with respect to the Cartesian product. For the construction of so-called Partial Star Products are of particular interest.

Pages