The edge-forwarding index or orbital regular graphs

DOI10.1016/0012-365X(92)00528-YMaRDI QIDQ1331968zbMATH OpenOpenAlexFDO

Authors Patrick Solé

Publication date 29 August 1994

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(92)00528-y

zbMATH Keywords

automorphism groupCayley graphedge-forwarding indexmerit factororbital regular graphsorbitsPaley graphpathsroutingWaring problem

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Paths and cycles (05C38) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71)

Review text

Let \(\Gamma\) denote a finite simple undirected graph on \(n\) vertices. A routing \(R\) is a set of \(n(n-1)\) paths in \(\Gamma\) such that each of the ordered pairs of distinct vertices is joined by one of them. The edge- forwarding index \(\Pi(\Gamma)\) is the minimum over all routings \(R\) of the maximum over all edges \(e\) of the number of paths in \(R\) that traverse \(e\). The so-called merit factor is defined to be \[ f(\Gamma)= {\Pi(\Gamma) \Delta\ln(\Delta-1)\over n\ln n}, \] where \(\Delta\) denotes the maximum valence of \(\Gamma\). The graph \(\Gamma\) is said to be orbital regular if some subgroup of its automorphism group acts reguarly on each of the orbits of unordered pairs of distinct vertices of \(\Gamma\), the edge-set \(E\) of \(\Gamma\) being one of these orbits. For such graphs it is shown that \(\Pi(\Gamma)= (1/| E|)\sum d(u,v)\), where the summation is over all \((u,v)\in V\times V\) and \(d\) is the usual distance function. Consider in particular the Cayley graph \(\Gamma_{t,q}\) of the addition group of the field on \(q\) elements with respect to the generating set of (nonzero) \(t\)-adic residues. When \(t= 2\), the Paley graph \(P_ q\) is obtained and \(\Pi(P_ q)= 6\). More generally, \(f(\Gamma_{t,q})\leq 9/2+ o(1)\).

Recommendations

• Edge-foreward index of star graphs and other Cayley graphs
• On the edge-forwarding indices of Frobenius graphs
• On the edge forwarding index problem for small graphs
• On edge-forwarding index of graphs with degree restriction

Cites work

• A note on Waring's problem in GF (p)
• Homogeneous additive congruences
• scientific article; zbMATH DE number 3884178 (Why is no real title available?)
• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• scientific article; zbMATH DE number 3970678 (Why is no real title available?)
• scientific article; zbMATH DE number 3577144 (Why is no real title available?)
• scientific article; zbMATH DE number 3445271 (Why is no real title available?)
• On forwarding indices of networks
• On the covering radius of cyclic linear codes and arithmetic codes

Cited in

(19)

• On orbital regular graphs and Frobenius graphs
• Edge-foreward index of star graphs and other Cayley graphs
• On the dual distance and the gap of a binary code
• Cyclotomic graphs and perfect codes
• Finding optimal routings in Hamming graphs
• Distance eigenvalues and forwarding indices of circulants
• Cube-connected circulants: bisection width, Wiener and forwarding indices
• Frobenius circulant graphs of valency six, Eisenstein-Jacobi networks, and hexagonal meshes
• Gossiping and routing in undirected triple-loop networks
• Optical Routing of Uniform Instances in Cayley Graphs
• Gossiping and routing in second-kind Frobenius graphs
• Lower bounds of forwarding indices of graph products
• Recursive cubes of rings as models for interconnection networks
• FROBENIUS CIRCULANT GRAPHS OF VALENCY FOUR
• On the orbital regular graph of finite solvable groups
• Rotational circulant graphs
• The forwarding indices of augmented cubes
• On the edge-forwarding indices of Frobenius graphs
• Forwarding and optical indices of 4-regular circulant networks

This page was built for publication: The edge-forwarding index or orbital regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1331968)