Competition Numbers and Phylogeny Numbers of Connected Graphs and Hypergraphs

• 来源期刊: 代数集刊（英文版）
• 关键词: quotient digraph competition graph phylogeny graph
• 年，卷（期）: 2020,（1）
• 页码范围: 79-86
• 页数: 8页
• 语种: 英文
• DOI: 10.1142/S1005386720000073

摘要

Let D be a digraph.The competition graph of D is the graph having the same vertex set with D and having an edge joining two different vertices if and only if they have at least one common out-neighbor in D.The phylogeny graph of D is the competition graph of the digraph constructed from D by adding loops at all vertices.The competition/phylogeny number of a graph is the least number of vertices to be added to make the graph a competition/phylogeny graph of an acyclic digraph.In this paper,we show that for any integer k there is a connected graph such that its phylogeny number minus its competition number is greater than k.We get similar results for hypergraphs.