DIMACS TR: 2011-01

Symmetric Class-0 Subgraphs of Complete Graphs

Authors: Eugene Fiorini, Vin de Silva, and Channing Verbeck, Jr.


In graph pebbling, a connected graph is called Class-0 if it has a pebbling number equal to its number of vertices. This paper addresses the question of when it is possible to edge-partition a complete graph into k complementary class-0 subgraphs. We define the notion of k-class-0 graphs: a graph G is k-class-0 if it contains k edge-disjoint subgraphs, where each subgraph is class-0. We next present a family of k-class-0 subgraphs for k = 2, showing that for n > 8, Kn is 2-class-0. We finally provide a probabilistic argument to prove that for all natural numbers k, there exists a natural number n such that Kn can be edge-partitioned into k cycliclly symmetric subgraphs of diameter 2 and connectivity 3: that is Kn is k-class-0.

Paper Available at: http://dimacs.rutgers.edu/TechnicalReports/TechReports/2011/2011-01.pdf
DIMACS Home Page