Phylogeny numbers for graphs with two triangles
type: Item
instance of: scholarly article
title: Phylogeny numbers for graphs with two triangles
zbMATH Open document ID: 0953.05027
DOI: 10.1016/S0166-218X(99)00209-7
author: Fred Roberts
author: Li Sheng
published in: Discrete Applied Mathematics
publication date: 2001-01-23T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 1474736
zbMATH Keywords: competition graph
zbMATH Keywords: competition number
zbMATH Keywords: phylogenetic tree reconstruction
zbMATH Keywords: phylogeny graph and digraph
zbMATH Keywords: phylogenetic number
reviewed by: Péter L. Erdős
MaRDI profile type: Publication
cites work: Q5515142
cites work: Competition numbers of graphs with a small number of triangles
cites work: Q3479858
cites work: Q3689222
cites work: Q4171826
cites work: Q3898496
cites work: Q3338254
cites work: Phylogeny numbers
full work available at URL: s0166-218x(99)00209-7
OpenAlex ID: W2042806489
Recommended article: Q4375745
Recommended article: Graph triangulations and the compatibility of unrooted phylogenetic trees
Recommended article: Phylogeny numbers
Recommended article: On the number of vertices of each rank in phylogenetic trees and their generalizations
Recommended article: Phylogeny numbers of generalized Hamming graphs
Recommended article: Q3143878
Recommended article: On the graph labellings arising from phylogenetics
Recommended article: On chordal phylogeny graphs
Recommended article: Q3328567
Recommended article: On the phylogeny graphs of degree-bounded digraphs
description: scientific article; zbMATH DE number 1474736