Mathematics and Physics Colloquium: Symmetric Class-0 Subgraphs and Forbidden Subgraphs
October 22, 2015 @ 12:45 pm
[icon name=”map-marker” class=”” unprefixed_class=””] Place: Namm 720
[icon name=”calendar” class=”” unprefixed_class=””] Date: Thursday October 22, 2015
[icon name=”clock-o” class=”” unprefixed_class=””] Time: 12:45 p.m.
Presented by Prof. Eugene Fiorini
Faculty and students are welcome, light refreshments will be served.
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 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 forbidden subgraphs of a family of competition graphs.