Title: Recent results on competition graphs and competition numbers
Speaker: Boram Park, Seoul National University and DIMACS
Date: Monday, February 13, 2012 11:00am - 12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
The notion of a competition graph was introduced by Cohen (1968) as a means of determining the smallest dimension of ecological phase space. The competition graph of an acyclic digraph D is a graph which has the same vertex set as D and has an edge between two distinct vertices u and v if and only if there exists a vertex x in D such that (u,x) and (v,x) are arcs of D. For any graph G, G plus sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number k(G) of a graph G is the smallest number of such isolated vertices.
In general, it is hard to compute the competition number k(G) for a graph G and characterizing a graph by its competition number has been one important research problem in the study of competition graphs. In this talk, we present several research problems and recent results on competition graphs and competition numbers of graphs.
DIMACS/CCICADA Interdisciplinary Series, Complete Spring Calendar 2012