Show icon Show search tips...
Hide icon Hide search tips...

[CCICADA-announce] DIMACS/CCICADA Interdisciplinary SeminarSeries - Monday, February 13, 2012

Linda Casals lindac at
Tue Feb 7 13:40:02 EST 2012


DIMACS/CCICADA Interdisciplinary Seminar Series Presents
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


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 

More information about the Dimacs-ccicada-announce mailing list