Trades and graphs (Q5936090)
From MaRDI portal
scientific article; zbMATH DE number 1612984
Language | Label | Description | Also known as |
---|---|---|---|
English | Trades and graphs |
scientific article; zbMATH DE number 1612984 |
Statements
Trades and graphs (English)
0 references
17 February 2002
0 references
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.
0 references
\(G\)-trade
0 references
\(G\)-design
0 references
defining set
0 references
trade spectrum
0 references
forbidden trade volumes
0 references