Phylogeny numbers for graphs with two triangles

DOI10.1016/S0166-218X(99)00209-7MaRDI QIDQ1570836zbMATH OpenOpenAlexFDO

Authors Fred Roberts, Li Sheng

Publication date 23 January 2001

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0166-218x(99)00209-7

zbMATH Keywords

competition graph competition number phylogenetic number phylogenetic tree reconstruction phylogeny graph and digraph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20)

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.

Recommendations

Cites work

Cited in

(9)

This page was built for publication: Phylogeny numbers for graphs with two triangles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1570836)