An introduction to set-sized packing

Document Type


Publication Date



© Copyright 2018, Charles Babbage Research Centre. All rights reserved. For a graph G, a packing is a subset of vertices 5 ⊆ V(G) such that |N[v]≤ 1 for all v ∈ V(G). That is, the closed neighborhood of any single vertex in V(G) is restricted in its intersection with S. A set-sized packing extends this notion beyond single vertices. Given the restriction sequence x(c1,c2,⋯), S ⊆ V(G) is a x(c1,c2,⋯) setsized packing if, for all i, X ⊆V with |X| = i implies |N[v]≤ ci. The set-sized packing number ρx(c1,c2,⋯,ct,⋯)(G) is the maximum cardinality of a x(c1 c1,⋯) set-sized packing. This work introduces set-sized packings, proper restriction sequences for set-sized packings, and the set-sized packing dimension of a graph. Particular attention is given to path, cycles, and graphs of set-sized packing dimension 1.

Publication Title

Journal of Combinatorial Mathematics and Combinatorial Computing

This document is currently not available here.