Competition Numbers and Phytogeny Numbers of Connected Graphs and Hypergraphs
Competition Numbers and Phytogeny Numbers of
Connected Graphs and Hypergraphs
Yanzhen Xiong; Soesoe Zaw; Yinfeng Zhu
【期刊名称】《代数集刊：英文版》 【年(卷),期】2020(027)001
【摘要】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.
【总页数】8页(P.79-86)
【关键词】quotient digraph; competition graph; phylogeny graph 【作者】Yanzhen Xiong; Soesoe Zaw; Yinfeng Zhu
【作者单位】School of Mathematical Sciences Shanghai Jiao Tong University Shanghai 200240 China 【正文语种】中文
Competition Numbers and Phytogeny Numbers of Connected Graphs and Hypergraphs
