Abstract. In the Watts-Strogatz model a small world network has the following properties:

(A1) The graph G is sparse, that is, |E(G)|/|V(G)| is in O(ln|V(G)|).
(A2) Its diameter is small, that is, diam(G) is in O(ln|V(G)|).
(A3) its clustering coefficient is large, that is, CC(G)≥c for a positive constant c.

Since the line graph operator causes that the neighbourhood of every vertex consists of (at most) two cliques, while the diameter increases at most by 1, it seems to be a suitable operator to model small world networks. In this paper we study graphs G such that L(G) satisfies (A1)-(A3). Using our results we present plenty of small world networks L(G) based on models G of parallel computers.