✦ LIBER ✦

Finding Optimal Routings in Hamming Graphs

✍ Scribed by Tian Khoon Lim; Cheryl E. Praeger

Publisher: Elsevier Science
Year: 2002
Tongue: English
Weight: 191 KB
Volume: 23
Category: Article
ISSN: 0195-6698
DOI: 10.1006/eujc.2002.0617

No coin nor oath required. For personal study only.

✦ Synopsis

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 the automorphism group for a graph to have an optimal routing in this sense. Graphs which satisfy Solé's condition are called orbital regular graphs. It is often difficult to determine whether or not a given graph is orbital regular. In this paper, we give a necessary and sufficient condition for a Hamming graph to be orbital regular with respect to a certain natural subgroup of automorphisms.

📜 SIMILAR VOLUMES

Optimal fault-tolerant routings for conn

Optimal fault-tolerant routings for connected graphs

✍ Koichi Wada; Yupin Luo; Kimio Kawaguchi 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 455 KB

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

Completely Transitive Codes in Hamming G

Completely Transitive Codes in Hamming Graphs

✍ Michael Giudici; Cheryl E. Praeger 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 169 KB

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

The Diametric Theorem in Hamming Spaces—

The Diametric Theorem in Hamming Spaces—Optimal Anticodes

✍ Rudolf Ahlswede; Levon H. Khachatrian 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 222 KB

y g X X counts the number of different components, we determine the maximal cardinality of subsets with a prescribed diameter d or, in another language, anticodes with distance d. We refer to the result as the diametric theorem. In a sense anticodes are dual to codes, which have a prescribed lower

Optimal routings in communication networ

Optimal routings in communication networks with linearly bounded forwarding index

✍ Manoussakis, Yannis; Tuza, Zsolt 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 358 KB 👁 1 views

In a given graph with n vertices, a routing is defined as a set of n(n -1) routes, one route connecting each ordered pair of vertices. The load of a vertex is the number of routes going through it. The forwarding index of the graph is the minimum of the largest load taken over all routings. We const

Finding maximum cliques in circle graphs

✍ D. Rotem; J. Urrutia 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 505 KB

## Abstract A circle diagram consists of a circle __C__ and a set of __n__ chords. This diagram defines a graph with __n__ vertices where each vertex corresponds to a chord, and two vertices are adjacent if their corresponding chords intersect in __C__. A graph __G__ is called a circle graph if it