✦ LIBER ✦

Completely Transitive Codes in Hamming Graphs

✍ Scribed by Michael Giudici; Cheryl E. Praeger

Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 169 KB
Volume: 20
Category: Article
ISSN: 0195-6698
DOI: 10.1006/eujc.1999.0313

No coin nor oath required. For personal study only.

✦ Synopsis

A code in a graph is a non-empty subset C of the vertex set V of . Given C, the partition of V according to the distance of the vertices away from C is called the distance partition of C. A completely regular code is a code whose distance partition has a certain regularity property. A special class of completely regular codes are the completely transitive codes. These are completely regular codes such that the cells of the distance partition are orbits of some group of automorphisms of the graph. This paper looks at these codes in the Hamming Graphs and provides a structure theorem which shows that completely transitive codes are made up of either transitive or nearly complete, completely transitive codes. The results of this paper suggest that particular attention should be paid to those completely transitive codes of transitive type.

📜 SIMILAR VOLUMES

Completely regular codes and completely

Completely regular codes and completely transitive codes

✍ Patrick Solé 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 511 KB

A binary code C is said to be completely regular if the weight distribution of any translate x + C depends only on the distance of x to C. Such codes are related to designs and distance regular graphs. Their covering radius is equal to their external distance. All perfect and uniformly packed codes

On Identifying Codes in Binary Hamming S

On Identifying Codes in Binary Hamming Spaces

✍ Iiro Honkala; Antoine Lobstein 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 138 KB

A binary code C f0; 1g n is called r-identifying, if the sets B r ðxÞ \ C; where B r ðxÞ is the set of all vectors within the Hamming distance r from x; are all nonempty and no two are the same. Denote by M r ðnÞ the minimum possible cardinality of a binary r-identifying code in f0; 1g n : We prove

Geodesics in Transitive Graphs

✍ C.Paul Bonnington; Wilfried Imrich; Norbert Seifter 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 541 KB

Let P be a double ray in an infinite graph X, and let d and d P denote the distance functions in X and in P respectively. One calls P a geodesic if d(x, y)=d P (x, y), for all vertices x and y in P. We give situations when every edge of a graph belongs to a geodesic or a half-geodesic. Furthermore,

Invariant Hamming graphs in infinite qua

Invariant Hamming graphs in infinite quasi-median graphs

✍ Marc Chastand; Norbert Polat 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 593 KB

It is shown that a quasi-median graph G without isometric infinite paths contains a Hamming graph (i.e., a cartesian product of complete graphs) which is invariant under any automorphism of G, and moreover if G has no infinite path, then any contraction of G into itself stabilizes a finite Hamming g

Finding Optimal Routings in Hamming Grap

Finding Optimal Routings in Hamming Graphs

✍ Tian Khoon Lim; Cheryl E. Praeger 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 191 KB

A routing R in a graph consists of a simple path p uv from u to v for each ordered pair of distinct vertices (u, v). We will call R optimal if all the paths p uv are shortest paths and if edges of the graph occur equally often in the paths of R. In 1994, Solé gave a sufficient condition involving th

Long cycles in vertex-transitive graphs

✍ László Babai 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 192 KB

## Abstract We prove that every connected vertex‐transitive graph on __n__ ≥ 4 vertices has a cycle longer than (3__n__)^1/2^. The correct order of magnitude of the longest cycle seems to be a very hard question.