Phylogeny numbers for graphs with two triangles (Q1570836): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 04:57, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Phylogeny numbers for graphs with two triangles |
scientific article |
Statements
Phylogeny numbers for graphs with two triangles (English)
0 references
23 January 2001
0 references
Let \(D\) be an acyclic directed graph (digraph) with vertex set \(V.\) Its phylogeny graph \(P(D)\) is an undirected graph on the same vertex set \(V\) where two vertices are adjecent if they are adjecent (in some order) in \(D\) or they have a common (outgoing) neighbour. The first result in this paper states that if \(G\) is an undirected graph then one can find an acyclic digraph \(D\) on a bigger underlying set, such that \(G\) is a subgraph of the phylogenetic graph of \(D\) where no arc is directed to \(G\) from outside of \(G.\) The directed graph \(D\) is called a phylogenetic digraph of \(G.\) The phylogenetic number of \(G\) is the possible minimal number of the ``extra'' vertices. These notions are similar to the widely studied notions of competiton graphs and competition numbers, introduced in ecological applications independently by Cohen and Roberts. This paper determines the phylogenetic numbers of undirected graphs with exactly two triangles.
0 references
competition graph
0 references
competition number
0 references
phylogenetic tree reconstruction
0 references
phylogeny graph and digraph
0 references
phylogenetic number
0 references