×

Phylogeny numbers for graphs with two triangles. (English) Zbl 0953.05027

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.

MSC:

05C20 Directed graphs (digraphs), tournaments
Full Text: DOI

References:

[1] J.E. Cohen, Interval graphs and food webs: a finding and a problem, Rand Corporation Document 17696-PR, Santa Monica, CA, 1968.; J.E. Cohen, Interval graphs and food webs: a finding and a problem, Rand Corporation Document 17696-PR, Santa Monica, CA, 1968.
[2] J.E. Cohen, F. Webs and N. Space, Princeton Univ. Press, Princeton, NJ, 1978.; J.E. Cohen, F. Webs and N. Space, Princeton Univ. Press, Princeton, NJ, 1978.
[3] F. Harary, R.Z. Norman, D. Cartwright, Structural Models: An Introduction to the Theory of Directed Graphs, Wiley, New York, 1965.; F. Harary, R.Z. Norman, D. Cartwright, Structural Models: An Introduction to the Theory of Directed Graphs, Wiley, New York, 1965. · Zbl 0139.41503
[4] Kim, S. R.; Roberts, F. S., Competition numbers of graphs with a small number of triangles, Discrete Appl. Math., 78, 153-162 (1997) · Zbl 0889.05057
[5] J.R. Lundgren, Food webs, competition graphs, competition-common enemy graphs, and niche graphs, in: F.S. Roberts (Ed.), Applications of Combinatorics and Graph Theory to the Biological and Social Sciences, IMA Volumes in Mathematics and its Applications, Vol. 17, Springer, New York, 1989, pp. 221-243.; J.R. Lundgren, Food webs, competition graphs, competition-common enemy graphs, and niche graphs, in: F.S. Roberts (Ed.), Applications of Combinatorics and Graph Theory to the Biological and Social Sciences, IMA Volumes in Mathematics and its Applications, Vol. 17, Springer, New York, 1989, pp. 221-243. · Zbl 0701.92023
[6] A. Raychaudhuri, F.S. Roberts, Generalized competition graphs and their applications, in: P. Brucker, R. Pauly (Eds.), Methods of Operations Research, Anton Hain, Konigstein, West Germany, 1985, pp. 295-311.; A. Raychaudhuri, F.S. Roberts, Generalized competition graphs and their applications, in: P. Brucker, R. Pauly (Eds.), Methods of Operations Research, Anton Hain, Konigstein, West Germany, 1985, pp. 295-311. · Zbl 0572.05050
[7] F.S. Roberts, Food webs, competition graphs, and the boxicity of ecological phase space, in: Y. Alavi, D. Lick (Eds.), Theory and Applications of Graphs, Springer, New York, 1978, pp. 477-490.; F.S. Roberts, Food webs, competition graphs, and the boxicity of ecological phase space, in: Y. Alavi, D. Lick (Eds.), Theory and Applications of Graphs, Springer, New York, 1978, pp. 477-490. · Zbl 0389.90036
[8] F.S. Roberts, Graph Theory and its Applications to Problems of Society, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1978.; F.S. Roberts, Graph Theory and its Applications to Problems of Society, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1978. · Zbl 0452.05001
[9] F.S. Roberts, Applied Combinatorics, Prentice-Hall, Englewood Cliffs, NJ, 1984.; F.S. Roberts, Applied Combinatorics, Prentice-Hall, Englewood Cliffs, NJ, 1984. · Zbl 0547.05001
[10] Roberts, F. S.; Sheng, L., Phylogeny numbers, Discrete Appl. Math., 87, 213-228 (1998) · Zbl 0907.05024
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.