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 phyloge...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.展开更多
文摘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.
