# ISIPhyNC - Property: Upper bound on the number of vertices

## Summary

The number of vertices is bounded by the number of leaves.

## More formally

There exists a function f such that any network with n leaves has at most f(n) vertices.

## Phylogenetic network classes with this property

• binary galled network: An upper bound on the number of vertices is 6n-5 and an upper bound on the number of reticulation vertices is 2n-2. Both bounds are tight. [reference] (Theorem 4.1, Figure 3 and Table 1)
• binary nearly stable: An upper bound on the number of vertices is 26n-24. [reference] (Theorem 2 (adding the number of reticulation vertices, tree vertices, the root and the leaves))
• binary nearly stable: An upper bound on the number of vertices is 8n-7 and an upper bound on the number of reticulation vertices is 3n-3. Both bounds are tight. [reference] (Theorem 5.5 and Table 1)
• binary nearly tree-child: An upper bound on the number of vertices is 4n. [reference] (Lemma 4)
• binary normal: An upper bound on the number of vertices is n2-n+2 [reference] (Theorem 5.1(2), with a multiplication by 2 to take into account the number of vertices possibly added during the "decontraction" to obtain a binary phylogenetic network)
• binary regular: An upper bound on the number of vertices is 2n. [reference] (Theorem 5.1(3), with a multiplication by 2 to take into account the number of vertices possibly added during the "decontraction" to obtain a binary phylogenetic network)
• binary reticulation-visible: An upper bound on the number of vertices is 8n-7 and an upper bound on the number of reticulation vertices is 3n-3. Both bounds are tight. [reference] (Theorem 1.2)
• binary stable-child: An upper bound on the number of vertices is 16n-15 and an upper bound on the number of reticulation vertices is 7n-7. Both bounds are tight. [reference] (Theorem 6.4 and Table 1)
• binary tree-child: An upper bound on the number of vertices is 5n-2. [reference] (Proof of Theorem 2)

### All classes

In the inclusion diagram below, the names of classes with this property are colored.

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.