# ISIPhyNC - Class: binary 1-reticulated

## Definition

A phylogenetic network is binary 1-reticulated if it is binary and it is 1-reticulated. [reference]

## Problems

### Positive results proved for this class

No positive result found

### Positive results deduced from superclasses

• Phylogenetic Network Isomorphism, positive result on binary: The phylogenetic network isomorphism problem can be solved in O(n4) time on binary networks. Simulations show that the algorithm is practical, with instances of 500 vertices solved in less than one tenth of a second. [reference]

### Negative results proved for this class

No negative result found

### Negative results deduced from subclasses

No negative result could be deduced from subclasses.

## Properties

### Properties proved for this class

No property found

### Properties deduced from superclasses

No property could be deduced from superclasses.

### Properties deduced from subclasses

• Unbounded number of vertices, property of binary nested: By subdividing the arc below the root of a blob on a side which contains a leaf, subdividing the arc above the reticulation arc of the same blob on the same s, and adding an arc from the vertex created by the first subdivision to the vertex created by the second subdivision, we increase the number of arcs and vertices of the network without increasing the number of leaves, and the network remains nested.

## Examples of networks

### In this class

proved directly:
network #1 : Each tree vertex can reach at most one reticulation vertex by 2 internally vertex-disjoint paths: r can reach c, g can reach b and f can reach a.
network #2 : Each tree vertex can reach at most one reticulation vertex by 2 internally vertex-disjoint paths: r can reach i, a can reach h and b can reach g.

Deduced from class inclusions: network #20 (deduced from the inclusion of "binary nested" in this class), network #5 (deduced from the inclusion of "binary unicyclic" in this class), network #6 (deduced from the inclusion of "binary galled tree" in this class), network #10 (deduced from the inclusion of "binary 2-nested" in this class), network #19 (deduced from the inclusion of "binary 3-nested" in this class), network #3 (deduced from the inclusion of "binary 2-nested" in this class), network #16 (deduced from the inclusion of "binary 2-nested" in this class)

### Not in this class

Proved directly:
network #14 : There are 2 vertices which can be reached by at least two directed internally vertex-disjoint paths from r: b and c.
network #9 : Both vertices c and d can be reached by 2 internally-vertex-disjoint paths from r (one containing a and the other one containing e).
network #8 : Tree vertex r can reach 2 reticulation vertices by 2 directed internally vertex-disjoint paths: f and g.
network #4 : Tree vertex b can reach 2 reticulation vertices by 2 directed internally vertex-disjoint paths: d and e.

Deduced from class inclusions: network #7 (deduced from the inclusion of this class in "binary 2-reticulated")

This website was programmed and is maintained by Philippe Gambette. It was started during the internship of Maxime Morgado at LIGM, in June-July 2015, and also contains contributions made from Narges Tavassoli from November 2016 to January 2017.