Abstract | ||
---|---|---|
A graph G is packable by the graph F if its edges can be partitioned into copies of F. If deleting the edges of any F-packable subgraph from G leaves an F-packable graph, then G is randomly F-packable. If G is F-packable but not randomly F-packable then G is F-forbidden. The minimal F-forbidden graphs provide a characterization of randomly F-packable graphs. We show that for each rho-connected rho-regular graph F with rho > 1, there is a set R(F) of minimal F-forbidden graphs of a simple form, such that any other minimal F-forbidden graph can be obtained from a graph in R(F) by a process of identifying vertices and removing copies of F. When F is a connected strongly edge-transitive graph having more than one edge (such as a cycle or hypercube), there is only one graph in R(F). |
Year | DOI | Venue |
---|---|---|
1996 | 10.1016/0012-365X(95)00147-O | Discrete Mathematics |
Keywords | DocType | Volume |
random packing,regular graph | Journal | 160 |
Issue | ISSN | Citations |
1-3 | 0012-365X | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Lowell W. Beineke | 1 | 204 | 86.82 |
Peter Hamburger | 2 | 54 | 14.61 |
William D. Weakley | 3 | 56 | 10.40 |