The elimination procedure for the competition number is not optimal (Q2499585): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.dam.2005.11.009 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2169318390 / rank | |||
Normal rank |
Revision as of 02:00, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The elimination procedure for the competition number is not optimal |
scientific article |
Statements
The elimination procedure for the competition number is not optimal (English)
0 references
14 August 2006
0 references
A graph \(G=(V,E)\) is the competition graph of an acyclic digraph \(D=(V,A)\) (called food web) if \(E = \{\{x,y\} \mid \exists z \in V ((x,z) \in A \wedge (y,z) \in A)\}\). The competition number of \(G\) is the minimum \(r\) such that \(G+rK_1\) is a competition graph, see \textit{R. J. Opsut} [SIAM J.\ Algebraic Discrete Methods 3, 420--428 (1982; Zbl 0512.05032)]. As the title states, the elimination procedure introduced by \textit{S.-R. Kim} and \textit{F. S. Roberts} [Ars Comb.\ 50, 97--113 (1998; Zbl 0963.05071)] provides only an upper bound on the competition number.
0 references
competition graph
0 references
phylogeny graph
0 references
phylogeny number
0 references