Phylogeny numbers for graphs with two triangles (Q1570836): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
(One intermediate revision by one other user not shown) | |||
Property / cites work | |||
Property / cites work: Q5515142 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Competition numbers of graphs with a small number of triangles / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3479858 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3689222 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4171826 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3898496 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3338254 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Phylogeny numbers / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/s0166-218x(99)00209-7 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2042806489 / rank | |||
Normal rank |
Latest revision as of 11:22, 30 July 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