Labeled packings of graphs (Q2866609)

Let \(G_1, G_2, \ldots G_k\) are \(k\) graphs of order \(n\). Then there is a packing of \(G_1, G_2, \ldots G_k\) into \(K_n\) if there exist permutations \(\sigma_i : E(G_i) \rightarrow V(K_n)\) for \(1 \leq i \leq k\) such that \(\sigma_i^\ast(E(G_i)) \cap \sigma_i^\ast(E(G_j))=\emptyset\) for \(1 \leq i < j \leq k\) (where \(\sigma_i^\ast: E(G_i) \rightarrow E(K_n)\) is the mapping induced by \(\sigma_i\), \(1 \leq i \leq k\)). A conjecture of \textit{B. Bollobás} and \textit{S. E. Eldridge} [J. Comb. Theory, Ser. B 25, 105--124 (1978; Zbl 0387.05020)] states that if \(G_1, G_2, \ldots, G_k\) are \(k\) graphs of order \(n\) and \(|E(G_i)| \leq n-k\) for \(1 \leq i \leq k\), then \(G_1, G_2, \ldots, G_k\) are packable into \(K_n\). This conjecture is still largely open.NEWLINENEWLINE The authors of this paper introduce a variation of the notion of a packing for the case where all graphs \(G_i\) are isomorphic. Let \(p \geq 1\) be an integer and \(G_1, G_2, \ldots, G_k\) be \(k\) copies of a graph \(G=(V,E)\). Let \(f: V(G) \rightarrow \{1,2, \ldots, p\}\) be a function. Then \(f\) is called a \(p\)-labeled packing of \(k\) copies of \(G\) into \(K_n\) if there exist permutations \(\sigma_i: V(G_i) \rightarrow V(K_n)\) for \(1 \leq i \leq k\) such that (i) \(\sigma_i^\ast(E(G_i)) \cap \sigma_i^\ast(E(G_j))=\emptyset\) and (ii) for every vertex \(v\) of \(G\) we have \(f(v) =f(\sigma_1(v))=f(\sigma_2(v))= \cdots=f(\sigma_k(v))\). The largest positive integer \(p\) for which there is a \(p\)-labeled packing of \(k\) copies of \(G\) is called a \(k\)-labeled packing number of \(G\) and is denoted by \(\lambda^k(G)\). The authors determine exact values of \(\lambda^k(C_n)\) for all \(k \geq 2\) and \(n \geq 4k-3\), for which these exist.