𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Iterated line graphs are maximally ordered

✍ Scribed by Martin Knor; L'udovít Niepel

Publisher
John Wiley and Sons
Year
2006
Tongue
English
Weight
110 KB
Volume
52
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A graph G is k‐ordered if for every ordered sequence of k vertices, there is a cycle in G that encounters the vertices of the sequence in the given order. We prove that if G is a connected graph distinct from a path, then there is a number t~G~ such that for every t ≥ t~G~ the t‐iterated line graph of G, L^t^ (G), is (δ(L^t^ (G)) + 1)‐ordered. Since there is no graph H which is (δ(H)+2)‐ordered, the result is best possible. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 171–180, 2006

📜 SIMILAR VOLUMES

Which line-graphs are perfectly orderabl
Which line-graphs are perfectly orderable?
✍ V. Chvátal 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 193 KB

## Abstract We characterize (by forbidden induced subgraphs) those line‐graphs that are perfectly orderable. Implicit in our presentation is a polynomial, time algorithm for recognizing these graphs.

3-Connected line graphs of triangular gr
3-Connected line graphs of triangular graphs are panconnected and 1-hamiltonian
✍ H. J. Broersma; H. J. Veldman 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 368 KB 👁 1 views

A graph is k-triangular if each edge is in at least k triangles. Triangular is a synonym for l-triangular. It is shown that the line graph of a triangular graph of order at least 4 is panconnected if and only if it is 3-connected. Furthermore, the line graph of a k-triangular graph is k-harniltonian

All Unit-Distance Graphs of Order 6197 A
All Unit-Distance Graphs of Order 6197 Are 6-Colorable
✍ Dan Pritikin 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 312 KB

Consider any 6197 or fewer points in the plane, and create a graph with this vertex set by considering a pair of those points to be adjacent if and only if their distance is exactly 1. It is shown that the vertices of the resulting graph can be properly 6-colored. 1998 Academic Press Consider R 2 =