next up previous contents
Next: Planar Graphs Up: Specific Class of Graphs Previous: Interconnection Networks   Contents

Chordal Rings

A chordal ring is an augmented ring, or a circulant graph with a chord of length 1. Formally it is defined by the pair (n,L) where n is the number of nodes of the ring, and L is the set of chords, $L \subseteq \{2,\ldots,\floor{n/2}\}$. Each chord $l \in L$ connects every pair of nodes of the ring that are at distance l in the ring. We denote by $\mbox{$\cC$}(n;l_1,\ldots,l_t)$, $l_1 \leqs \ldots \leqs l_t$, the chordal ring defined by $(n,\{l_1,\ldots,l_t\})$. The dimension of $\mbox{$\cC$}(n;l_1,\ldots,l_t)$ is t+1. Let us emphasize that the degree of chordal rings is 2t in general, except whenever there is a chord of length n/2. In this case n is even and the degree is 2t-1.


\begin{theorem}[\cite{NO97}]\mbox{}
\beginsmall{itemize}
\par\item For every $l ...
...D$\ is the diameter of $\mbox{$\cC$}(n;l)$.
\par\endsmall{itemize}
\end{theorem}

A ``natural'' labeling of the nodes for chordal rings is the cyclic labeling: Consecutive labeling of nodes around the ring. This labeling is not always the best possible one. For instance, [KL95] showed that $\mbox{$\cC$}(29;3)$ has no shortest path 1-IRS with cyclic labeling whereas it is of compactness 1. In fact it is possible to characterize graphs supporting a shortest path 1-IRS according a cyclic labeling of nodes.


\begin{theorem}
\mbox{}
\beginsmall{itemize}
\par
\item~{\bf\cite{KL95}} A chord...
...test path $1$-SIRS with
non-cyclic labeling.
\endsmall{itemize}
\end{theorem} 3

By the use of the Ádám property, [Man98] showed that $\mbox{$\cC$}(n;l)$ is isomorphic to $\mbox{$\cC$}(n;l')$ if and only if $l l' \bmod n =
1$. For instance $\mbox{$\cC$}(29;3)$, which has no shortest path 1-IRS with cyclic labeling (cf. [KL95]), is isomorphic to $\mbox{$\cC$}(29;10)$ which satisfies Theorem 26. Therefore, $\mbox{\rm SIRS}(\mbox{$\cC$}(29;3)) = 1$.


\begin{conjecture}[\cite{Mans98}]
If $\mbox{\rm SIRS}(\mbox{$\cC$}(n;l)) = 1$\ ...
...t path $1$-SIRS with cyclic labeling, with $l l' \bmod n =
1$.
\end{conjecture}


\begin{theorem}\mbox{}
\beginsmall{itemize}
\par\item~{\bf\cite{Mans98}} For eve...
...\rm SIRS}(\mbox{$\cC$}(2i^2+2i+1;2i+1)) > 1$.
\endsmall{itemize}
\end{theorem}

Let $\cC_i = \mbox{$\cC$}(2i^2+2i+1;2i+1)$. Since $\cC_i$ is of diameter i (cf. [BCH95]), it follows that 1- $\mbox{\rm stretch}(\cC_i) \geqs 1+1/i$, for every $i \geqs 2$. (Actually, $\cC_i$ is the chordal ring of degree 4 with the largest number of nodes for a given diameter). Moreover, in [NO97], it is shown that 1- $\mbox{\rm stretch}(\cC_i) \leqs 2$. Also, the smallest chordal ring known to be of compactness greater than 1 is $\mbox{$\cC$}(13,5)$, and 1- $\mbox{\rm stretch}(\mbox{$\cC$}(13,5)) \geqs 3/2$. [NO97] showed that there exists some chordal rings, $\cC_i$, where every shortest path IRS using a cyclic labeling requires $\sqrt{n/2}$ intervals, and also that $\mbox{$\cC$}(35;5)$ has no shortest path 1-IRS of stretch factor $\leqs 2$ with a cyclic labeling. Other results about directed chordal rings are mentioned in [KL95].

Open question 6    
- Is there some chordal ring of compactness $\Omega(\sqrt{n})$?
- Characterize chordal rings of compactness k with cyclic labeling, for $k \geqs 2$.

For two chords we have:


\begin{theorem}[\cite{FGS94a}]
Let $i,j$\ be two integers, and $C = \mbox{$\cC$}...
...$-$\mbox{\rm stretch}(C) \leqs (j - i + 2)/2$.
\endsmall{itemize}
\end{theorem}

And for higher dimensions,


\begin{theorem}[\cite{FGS94a}]\mbox{}
\beginsmall{itemize}
\item For every $i \g...
...\mbox{$\cC$}(r^p;
r^{l_1},\ldots,r^{l_t}))=1$. \endsmall{itemize}
\end{theorem}

The latter result can be easily generalized to $\mbox{$\cC$}(n;l_1,\ldots,l_t)$ when $l_i \bmod n = 0$, and $l_{i+1} \bmod l_i = 0$ for every i.

In [FGS94] is presented several results concerning IRS without the disjointness property of the labels assigned to the arcs, i.e., with Condition 2b of Definition 1 relaxed. See Paragraph 4.3 for a discussion of these results.

Note also that most of the results extend to circulant graphs in general, i.e., does not need to specify the chord of length 1.

Open question 7    
- Is there a general upper bound for the compactness of chordal rings of dimensions d of the form n1-O(1/d) ?


next up previous contents
Next: Planar Graphs Up: Specific Class of Graphs Previous: Interconnection Networks   Contents

2000-03-21