A family of clique divergent graphs with linear growth (Q1376063)

Let \(k(G)\) be the clique graph of a given graph \(G=(V,E)\). This is the intersection graph of the set of all cliques of \(G\). Its vertices are the cliques of \(G\). Two different vertices of \(k(G)\) are joined by an edge iff they have a non-empty intersection. The iterated clique graphs \(k^n(G)\) are defined by \(k^{n+1} (G)= k(k^n(G))\). \(G\) is called \(k\)-divergent, if the sequence \(\{p_n(G)\}= \{p_n\}= \{| V(k^n (G)|\}\), formed by the orders of these graphs, tends to infinity with \(n\). It is an interesting question whether there exist graphs with polynomial growth, that means, whether there exists a \(k\)-divergent graph \(G\) such that for some fixed polynomial \(f\) holds \(p_n\leq f(n)\) for all \(n\). In the present paper an infinite set of finite graphs \(G\) is given such that, for any graph \(G\), \(p_n(G)\) is a linear function of \(n\). Further there are given examples of graphs \(G\) such that \(p_n(G)\) is a polynomial of any given positive degree. Therefore, firstly powers \(C^s_n\) of cycles \(C_n\) are considered by the authors, and some characterizing properties of them are given. Using these graphs, the graph \(G=G(r,s)\) of order \(rs\) and size \(rs(s-1)+r\), \(r,s\geq 3\), is introduced which is obtained from \(C^{s-1}_{rs}\) by adding some \(r\) edges. The authors' first result is that this graph \(G=G (r,s)\) satisfies \(p_n(G)= r\cdot n+o(G)\) for all \(n\). This means that \(G\) is a \(k\)-divergent graph with linear growth and growth rate \(r\geq 3\). In a further paper it is also proved that the growth rate \(r=1\) and \(r=2\) can be realized. Concrete examples for this result are given here. Finally, by applying the above-mentioned first result in a certain product formula of the strong product of two special graphs the authors get the following second application by induction: For any integer \(d\geq 1\), there exists a graph \(G\) such that \(p_n(G)\) is a polynomial of degree \(d\) in \(n\).