Competition Graphs And Competition Numbers

The ecologist J.Cohen introduced the concept of competition graphs in 1968.Further research proved that the theory of competition graphs has applications in ecology involving digraphs,in which the vertices represent the species of an ecosystem and the arcs depict the relationship between predators and preys.Since then,there has been numerous studies related to the generalization of competition graphs.The competition graph C(D) of the corresponding digraph D of a food web is the undirected graph G that can be obtained by the association of the vertex set V(C(D)) and the edge set E(C(D)).The vertex set of the competition graph V(C(D)) has the same vertex set as digraph D and there will be an edge between two vertices x and y if there exists a common out-neighbor v such that(x,v)and(y,v) belong to A(D).Roberts observed that every graph G can be made into a competition graph by adding e isolated vertices,where e is the number of edges in G.Based on this observation,he defined the competition number?(G) of graph G as the smallest number of such additional vertices.In 1998,Roberts and Sheng presented the concepts of phylogeny graphs motivated by the similarity between the phylogenetic tree reconstruction and the competition graph.The phylogeny graph of a digraph D is an undirected graph G with the same vertex set as digraph D and two vertices of G are adjacent if they have a common out-neighbor in D or there is an arc between them in D.The phylogeny number ?(G) of a graph G is defined as the smallest nonnegative integer r such that there is a digraph D with |V(D)|-|V(G)|=r such that P(D) has G as an induced subgraph.In 1982,Opsut established that computing the competition number of graphs is NP-complete.In 1998,Roberts and Sheng verified that calculating the phylogeny number of graphs is NP-complete.In Chapter 2,we study strongly regular graphs on v vertices with pa-rameters(v,k,?,?) having the property ?-?=-1 by using two operations;strong product with an edge and the dual Seidel switching.From the combi-nation of these operations,we are able to construct the strictly Deza graphs derived from the Berlekamp-Van Lint-Seidel graph.Moreover,we deduce upper bound of the phylogeny number of Berlekamp-Van Lint-Seidel graph.The major contribution in Chapter 3 is the determination of the com-petition numbers and phylogeny numbers of several graph classes.We provide new estimates of the competition numbers and phylogeny numbers of complete multipartite graphs with uniform part sizes.We evaluate the competition number and phylogeny numbers of several graph classes,includ-ing Johnson graphs,Hamming graphs and generalized Hamming graphs,which are some most important graph classes in Algebraic combinatorics.We calculate the competition numbers and phylogeny numbers of Johnson graphs J(n,d) on n vertices with diameter d for d=2,3,4.The generalized Hamming graph,denoted by GHq₁,...,q_d,is the Cartesian product of com-plete graphs Kq₁,...,Kq_d.Note that GHq₁,...,q_dis known as the Hamming graph when q1=···=qd=q.We determine the phylogeny numbers of generalized Hamming graphs with diameter 3.In Chapter 4,we investigate the relationship between competition num-bers and phylogeny numbers of general graphs/hypergraphs.We show that the range of the function ?-?+1 is the set of all non-negative integers for graphs,connected graphs and hypergraphs.Lastly,we study variants of competition graphs in Chapter 5.A niche hypergraph of a digraph D is a generalization of niche graphs and is closely related to competition hypergraphs as well as double competition hyper-graphs.The edge set of niche hypergraph is the family of the set of vertices if they have a common out-neighbor or in-neighbor.We present niche hyper-graphs of products of digraphs D1 and D2 by using row hypergraphs.The main result in this chapter is the representation of the niche hypergraphs of products of digraphs in matrix form.