DIMACS TR: 2011-01
Symmetric Class-0 Subgraphs of Complete Graphs
Authors: Eugene Fiorini, Vin de Silva, and Channing Verbeck, Jr.
ABSTRACT
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