✦ LIBER ✦

Expanding and forwarding parameters of product graphs

✍ Scribed by Jianguo Qian; Fuji Zhang

Publisher: Elsevier Science
Year: 2004
Tongue: English
Weight: 299 KB
Volume: 136
Category: Article
ISSN: 0166-218X
DOI: 10.1016/s0166-218x(03)00199-9

No coin nor oath required. For personal study only.

✦ Synopsis

Expanding and forwarding are two graphic parameters related to the connectivity and the capacity of the network-the undirected graph with a given routing. Many large networks are composed from some existing smaller networks by using, in terms of graph theory, Cartesian product. The expanding and forwarding parameters of such large networks are associated strongly with that of the corresponding smaller ones. This association also provides a convenient way to determine the two parameters for some known networks such as the hypercube, generalized cube and the mesh, etc. As the generalization of the forwarding index, t-forwarding index is introduced and studied. The study shows that the t-forwarding parameters of a given graph are convergent (refers to the limit t → ∞), which reveals some further properties concerning the forwarding parameters of the product graphs.

📜 SIMILAR VOLUMES

Edge-forwarding index of star graphs and

Edge-forwarding index of star graphs and other Cayley graphs

✍ Ginette Gauyacq 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 686 KB

We present a technique for building, in some Cayley graphs, a routing for which the load of every edge is almost the same. This technique enables us to find the edge-forwarding index of star graphs and complete-transposition graphs.

Least-Distortion Euclidean Embeddings of

Least-Distortion Euclidean Embeddings of Graphs: Products of Cycles and Expanders

✍ Nathan Linial; Avner Magen 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 139 KB

Embeddings of finite metric spaces into Euclidean space have been studied in several contexts: The local theory of Banach spaces, the design of approximation algorithms, and graph theory. The emphasis is usually on embeddings with the least possible distortion. That is, one seeks an embedding that m

Classes of interval graphs under expandi

Classes of interval graphs under expanding length restrictions

✍ P. C. Fishburn; R. L. Graham 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 630 KB

Let C(a) denote the finite interval graphs representable as intersection graphs of closed real intervals with lengths in (1, a]. The points of increase for C are the rational a > 1. The set D(a) = [n,,,C(p)l\C(a) of graphs that appear as soon as we go past a is characterized up to isomorphism on the

Containment Properties of Product and Po

Containment Properties of Product and Power Graphs

✍ Antonio Fernéndez; Tom Leighton; Jose Luis Lopez-Presa 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 261 KB

Numerical invariants and the strong prod

Numerical invariants and the strong product of graphs

✍ R.S Hales 📂 Article 📅 1973 🏛 Elsevier Science 🌐 English ⚖ 420 KB

Some parameters of graph and its complem

Some parameters of graph and its complement

✍ Shao-ji Xu 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 627 KB

In this paper, we have discussed the Nordhaus-Gaddum problems for diameter d, girth g, circumference c and edge covering number ill-We have both got the following results. If both G and G are connected, then 4<~d+a~~ 6, then p+2<.c+~<.2p, 3(p-1)<~c.~<.p 2. If both G and G have no isolated vertex, th