| 1. |
- Hellmuth, Marc, et al.
(författare)
-
Generalized Fitch Graphs III : Symmetrized Fitch maps and Sets of Symmetric Binary Relations that are explained by Unrooted Edge-labeled Trees
- 2021
-
Ingår i: Discrete Mathematics & Theoretical Computer Science. - : Centre pour la Communication Scientifique Directe (CCSD). - 1462-7264 .- 1365-8050. ; 23:1
-
Tidskriftsartikel (refereegranskat)abstract
- Binary relations derived from labeled rooted trees play an import role in mathematical biology as formal models of evolutionary relationships. The (symmetrized) Fitch relation formalizes xenology as the pairs of genes separated by at least one horizontal transfer event. As a natural generalization, we consider symmetrized Fitch maps, that is, symmetric maps epsilon that assign a subset of colors to each pair of vertices in X and that can be explained by a tree T with edges that are labeled with subsets of colors in the sense that the color m appears in epsilon(x, y) if and only if m appears in a label along the unique path between x and y in T. We first give an alternative characterization of the monochromatic case and then give a characterization of symmetrized Fitch maps in terms of compatibility of a certain set of quartets. We show that recognition of symmetrized Fitch maps is NP-complete. In the restricted case where vertical bar epsilon(x, y)vertical bar <= 1 the problem becomes polynomial, since such maps coincide with class of monochromatic Fitch maps whose graph-representations form precisely the class of complete multi-partite graphs.
|
|
| 2. |
- Seemann, Carsten R., et al.
(författare)
-
Planar median graphs and cubesquare-graphs
- 2023
-
Ingår i: Discrete Applied Mathematics. - : Elsevier BV. - 0166-218X .- 1872-6771. ; 331, s. 38-58
-
Tidskriftsartikel (refereegranskat)abstract
- Median graphs are connected graphs in which for all three vertices there is a unique vertex that belongs to shortest paths between each pair of these three vertices. In this paper we provide several novel characterizations of planar median graphs. More specifically, we characterize when a planar graph G is a median graph in terms of forbidden subgraphs and the structure of isometric cycles in G, and also in terms of subgraphs of G that are contained inside and outside of 4-cycles with respect to an arbitrary planar embedding of G. These results lead us to a new characterization of planar median graphs in terms of cubesquare-graphs that is, graphs that can be obtained by starting with cubes and square-graphs, and iteratively replacing 4-cycle boundaries (relative to some embedding) by cubes or square-graphs. As a corollary we also show that a graph is planar median if and only if it can be obtained from cubes and square -graphs by a sequence of square-boundaryamalgamations. These considerations also lead to an O(n log n)-time recognition algorithm to compute a decomposition of a planar median graph with n vertices into cubes and square-graphs.
|
|
