𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Distances and diameters on iterated clique graphs

✍ Scribed by Miguel A. Pizaña

Publisher
Elsevier Science
Year
2004
Tongue
English
Weight
203 KB
Volume
141
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

If G is a graph, its clique graph, K(G), is the intersection graph of all its (maximal) cliques. Iterated clique graphs are then deÿned recursively by: K

We study the relationship between distances in G and distances in K n (G). Then we apply these results to Johnson graphs to give a shorter and simpler proof of Bornstein and Szwarcÿter's theorem: For each n there exists a graph G such that diam(K n (G)) = diam(G) + n. In the way, a new family of graphs with increasing diameters under the clique operator is shown.

📜 SIMILAR VOLUMES

On iterated clique graphs with increasin
On iterated clique graphs with increasing diameters
✍ C. Peyrat; D. F. Rall; P. J. Slater 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 210 KB 👁 1 views

We examine the problem of finding a graph G whose nth iterated clique graph has diameter equal to the diameter of G plus n.

Iterated clique graphs with increasing d
Iterated clique graphs with increasing diameters
✍ Bornstein, Claudson F.; Szwarcfiter, Jayme L. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 73 KB

A simple argument by Hedman shows that the diameter of a clique graph G differs by at most one from that of K(G), its clique graph. Hedman described examples of a graph G such that diam(K(G)) = diam(G) + 1 and asked in general about the existence of graphs such that diam(K i (G)) = diam(G) + i. Exam

Diameters of iterated clique graphs of c
Diameters of iterated clique graphs of chordal graphs
✍ Bor-Liang Chen; Ko-Wei Lih 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 272 KB

## Abstract The clique graph __K__(__G__) of a graph is the intersection graph of maximal cliques of __G.__ The iterated clique graph __K__^__n__^(__G__) is inductively defined as __K__(K^n−1^(__G__)) and __K__^1^(__G__) = __K__(__G__). Let the diameter diam(__G__) be the greatest distance between

Distance regular graphs of diameter 3 an
Distance regular graphs of diameter 3 and strongly regular graphs
✍ A.E Brouwer 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 124 KB

In [1] N.L. Biggs mentions two parameter sets for distance regular graphs that are antipodal covers of a complete graph, for which existence of a corresponding graph was unknown. Here we settle both cases by proving that one does not exist, while there are exactly two nonisomorphic solutions to the