×

Trades and graphs. (English) Zbl 0979.05086

The trade spectrum \(\text{TS}(G)\) of a simple graph \(G\) is defined to be the set of all \(t\) for which it is possible to assemble together \(t\) copies of \(G\) into a simple graph \(H\), and then disassemble \(H\) into \(t\) entirely different copies of \(G\). The complement of \(\text{TS}(G)\), \(X(G)\), is called the set of forbidden trade volumes for \(G\). Trade spectra of graphs have applications to intersection problems and defining sets, which in turn have important applications in secret sharing schemes and shared security systems. In this paper the authors investigate the set \(X(G)\) for various graphs \(G\). In particular they give many families of graphs in which \(X(G) = \{1\}\) or \(X(G) = \{1,2\}\). They note that a classification of those graphs \(G\) for which \(2 \in \text{TS}(G)\) is a challenging problem. The tools developed in this paper could be used to determine \(\text{TS}(G)\) for many infinite families of graphs besides the ones explicitly mentioned in the paper.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05B05 Combinatorial aspects of block designs
05C75 Structural characterization of families of graphs
Full Text: DOI