Some results on the maximum length of circuits of spread k in the d-cube (Q5556887)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3272064
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Some results on the maximum length of circuits of spread k in the d-cube |
scientific article; zbMATH DE number 3272064 |
Statements
Some results on the maximum length of circuits of spread k in the d-cube (English)
0 references
1969
0 references
circuit codes
0 references
0.9161016345024108
0 references
0.8729100227355957
0 references
0.8413228392601013
0 references
0.8362840414047241
0 references
A circuit code of dimension \(d\) and spread \(k\ge 1\) is a simple circuit \(C\) in the graph \(I^d\) of the unit \(d\)-dimensional cube which satisfies the condition \(d(x,y)\ge \min(d_0(x,y),k)\) for all \(x\) and \(y\) in \(C\), where \(d(x,y)\) \([d_0(x,y)]\) is the graph-theoretic distance between \(x\) and \(y\) in \(I^d\) [in \(C\)]. Such circuits are useful as error-limiting codes. The longer the circuit, the greater is the accuracy; the greater the spread, the greater is the error-limiting capability. The author discusses the pairs \((d,k)\) for which \(K(d,k)\), the length of a longest \(d\)-circuit of spread \(k\), is known. \textit{R. C. Singleton} [Generalized snake-in-the-box codes, IEEE Trans. Electron. Comput. 15, No. 4, 596--602 (1966; \url{doi:10.1109/PGEC.1966.264382})] has shown that (1) \(K(d,k) = 2d\) if \(d< [3k/2] + 2\), stated without proof that (2) \(K([3k/2] +2,k) = 4k +4\) for \(k\) odd, and conjectured that (3) \(K([3k/2] +2,k) = 4k + 6\) for \(k\) even. The author proves (2) and (3), showing in the case of (2) that, up to an isomorphism of \(I^d\) there is only one \(d\)-circuit of spread \(k\) and length \(K(d,k)\) for \(d= [3k/2] +2\) and \(k\) odd. The author also shows that \(K([3k/2] +3,k) = 4k + 8\) for odd \(k\ge 9\).
0 references