Journal article
Phylogeny numbers for graphs with two triangles
Discrete Applied Mathematics, v 103(1), pp 191-207
2000
Featured in Collection : UN Sustainable Development Goals @ Drexel
Abstract
Motivated by problems of phylogenetic tree reconstruction, Roberts and Sheng introduced notions of phylogeny graph and phylogeny number. These notions are analogous to and can be considered as natural generalizations of notions of competition graph and competition number that arise from problems of ecology. Given an acyclic digraph
D=(
V,
A), define its
phylogeny graph
G=
P(
D) by taking the same vertex set as
D and, for
x≠
y, letting
xy∈
E(
G) if and only if (
x,
y)∈
A or (
y,
x)∈
A or (
x,
a),(
y,
a)∈
A for some vertex
a∈
V. Given a graph
G=(
V,
E), we shall call the acyclic digraph
D a
phylogeny digraph for
G if
G is an induced subgraph of
P(
D) and
D has no arcs from vertices outside of
G to vertices in
G. The
phylogeny number
p(
G) is defined to be the smallest
r such that
G has a phylogeny digraph
D with |
V(
D)|−|
V(
G)|=
r. In this paper, we obtain results about phylogeny number for graphs with exactly two triangles analogous to those for competition number.
Metrics
Details
- Title
- Phylogeny numbers for graphs with two triangles
- Creators
- Fred S. Roberts - Rutgers, The State University of New JerseyLi Sheng - Drexel University
- Publication Details
- Discrete Applied Mathematics, v 103(1), pp 191-207
- Publisher
- Elsevier
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- Mathematics
- Web of Science ID
- WOS:000087473600013
- Scopus ID
- 2-s2.0-0347304286
- Other Identifier
- 991019169262904721
UN Sustainable Development Goals (SDGs)
This publication has contributed to the advancement of the following goals:
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Collaboration types
- Domestic collaboration
- Web of Science research areas
- Mathematics, Applied