Clique graphs of time graphs

AbstractA simple, finite graph G is called a time graph (equivalently, an indifference graph) if there is an injective real function f on the vertices v(G) such that vivj ∈ e(G) for vi ≠ vj if and only if |f(vi) − f(vj)| ≤ 1. A clique of a graph G is a maximal complete subgraph of G. The clique graph K(G) of a graph G is the intersection graph of the cliques of G. It will be shown that the clique graph of a time graph is a time graph, and that every time graph is the clique graph of some time graph. Denote the clique graph of a clique graph of G by K2(G), and inductively, denote K(Km−1(G)) by Km(G). Define the index indx(G) of a connected time graph G as the smallest integer n such that Kn(G) is the trivial graph. It will be shown that the index of a time graph is equal to its diameter. Finally, bounds on the diameter of a time graph will be derived