Silver Cubes

详细信息    查看全文

• 作者：Mohammad Ghebleh ; Luis A. Goddyn ; Ebadollah S. Mahmoodian and Maryam Verdian-Rizi
• 关键词：Silver matrix ; Graph colouring ; Coding theory ; Domination in graphs ; Finite projective geometry
• 刊名：Graphs and Combinatorics
• 出版年：2008
• 出版时间：October, 2008
• 年：2008
• 卷：24
• 期：5
• 页码：429-442
• 全文大小：476.1 KB

文摘

An n ¡Á n matrix A is said to be silver if, for i = 1,2,...,n, each symbol in {1,2,...,2n − 1} appears either in the ith row or the ith column of A. The 38th International Mathematical Olympiad asked whether a silver matrix exists with n = 1997. More generally, a silver cube is a triple (K _n d , I, c) where I is a maximum independent set in a Cartesian power of the complete graph K _n , and c:V(K_nd)? {1,2,...,d(n-1)+1}c:V(K_n^d)\rightarrow \{1,2,\dots,d(n-1)+1\} is a vertex colouring where, for v ∈ I, the closed neighbourhood N[v] sees every colour. Silver cubes are related to codes, dominating sets, and those with n a prime power are also related to finite geometry. We present here algebraic constructions, small examples, and a product construction. The nonexistence of silver cubes for d = 2 and some values of n, is proved using bounds from coding theory.