Mathematics Colloquium
, May 22, 1996, 4:00pm
102 Bradley Hall
Professor Fred Roberts
Rutgers University
speaks on
Competition Numbers and their Applications
Abstract. If D is an acyclic digraph, its competition graph is an undirected graph with the same vertex set and an edge between vertices x and y if there is a vertex a so that (x,a) and (y,a) are both arcs of D. Competition graphs arose in connection with an application in ecology and also have applications in coding, radio transmission, and modeling of complex economic systems. If G is any graph, G together with sufficiently many isolated vertices is a competition graph, and the competition number of G is the smallest number of such isolated vertices. The problem of recognizing competition graphs is equivalent to the problem of computing the competition number, and this problem is known to be NP-complete.
This talk will explore a number of old open problems concerning competition numbers, and provide detailed recent results about two of these problems: The problem of when an elimination algorithm (motivated by a graph-theoretical approach to Gaussian elimination) can be used to compute the competition number and the problem of computing the competition numbers of graphs with a small number of triangles.
Tea. High tea will be served at 3:30pm in the Lounge.
Emmy's. Certain refreshments will be available at the Emmy's after the talk.
Host. Bob Norman will be the host. Anybody who is interested in having dinner with the speaker should contact Bob at 646-2762.