|
Organizers |
On Randomly Packable Graphs
by
S. Arumugam
Manonmaniam Sundaranar University
Coauthors: S. Meena
A graph G is said to be packable by the graph F or F-packable if the edges of G can be partitioned into copies of F. G is called randomly F-packable if what remains after deletion of edges of a proper subgraph that is F-packable is also F-packable. A F-forbidden graph is one that is F-packable but not randomly. In this paper we prove that given any graph F conatining at least two edges, there exists a F-forbidden graph. Let c(F) and r(F) denote respectively the minimum number of copies of F and the minimum number of vertices in a minimal F-forbidden graph. We obtain bounds for these parameters and determine their exact values for several classes of graphs.
Date received: November 13, 2000
Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cafp-15.