𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Spanners of underlying graphs of iterated line digraphs

✍ Scribed by Rabah Harbane; Carles Padró

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
770 KB
Volume
62
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

✦ Synopsis

Given a simple undirected graph G, a spanning subgraph S is a t-spanner of G if every pair of vertices that are adjacent in G are at distance at most I in S. The factor t is called the dilution of the spanner. If S has the smallest possible number of edges among all t-spanners of G, then S is a minimum t-spanner of G. In this paper, we study spanners with small dilation of graphs which are underlying graphs of iterated line digraphs. @

📜 SIMILAR VOLUMES

Diameter vulnerability of iterated line
Diameter vulnerability of iterated line digraphs
✍ C. Padró; P. Morillo 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 823 KB

Because of their good properties, iterated line digraphs (specially Kautz and de Bruijn digraphs) have been considered to design interconnection networks. The diameter-vulnerability of a digraph is the maximum diameter of the subdigraphs obtained by deleting a fixed number of vertices or arcs. For a

Super link-connectivity of iterated line
Super link-connectivity of iterated line digraphs
✍ Xiaoyan Cheng; Xiufeng Du; Manki Min; Hung Q. Ngo; Lu Ruan; Jianhua Sun; Weili W 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 207 KB

Many interconnection networks can be constructed with line digraph iterations. A digraph has super link-connectivity d if it has link-connectivity d and every link-cut of cardinality d consists of either all out-links coming from a node, or all in-links ending at a node, excluding loop. In this pape

Convergent sequences of iterated H-line
Convergent sequences of iterated H-line graphs
✍ Gary Chartrand; Heather Gavlas; Michelle Schultz 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 629 KB

For a connected graph H of order at least 3, the H-line graph HL(G) of a graph G is defined as that graph whose vertices are the edges of G and where two vertices of HL(G) are adjacent if and only if the corresponding edges of G are adjacent and belong to a common copy of H. For k >~ 2, the kth ite

Convergence of sequences of iterated tri
Convergence of sequences of iterated triangular line graphs
✍ David Dorrough 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 333 KB

The triangular line graph T(G) of a graph G is the graph with vertex set E(G), with two distinct vertices e and f of T(G) adjacent if and only if the edges e and f belong to a common copy ofK 3 in G. For n/> 1, the nth iterated triangular line graph T"(G) of a graph G is defined as T(T n-I(G)), wher