Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)
Title: Symmetric Class-0 Subgraphs and Forbidden Subgraphs
Speaker: Eugene Fiorini, Muhlenberg College
Date: Thursday, March 10, 2016 5:00pm
Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Competition graphs and graph pebbling are two examples of graph theoretical-type games played on a graph under well-defined conditions. In the case of graph pebbling, the pebbling number pi(G) of a graph G is the minimum number of pebbles necessary to guarantee that, regardless of distribution of of pebbles and regardless of the target vertex, there exists a sequence of pebbling moves that results in placing a pebble on the target vertex. A class-0 graph is one in which the pebbling number is the order of the graph, pi(G)=|V(G)|. This talk will consider under what conditions the edge set of a graph G can be partitioned into k class-0 subgraphs, k a positive integer. Furthermore, suppose D is a simple digraph with vetex set V(D) and edge set E(D). The competition graph G(V(G),E(G)) of D is defined as a graph with vertex set V(G)=V(D) and edge vw in E(G) if and only if for some vertex u in V, there exist directed edges (u,v) and (u,w) in E(D). This talk will present some recent results on foodwebs and forbidden subgraphs of a family of competition graphs.