A family of clique divergent graphs with linear growth
type: Item
instance of: scholarly article
title: A family of clique divergent graphs with linear growth
zbMATH Open document ID: 0892.05041
DOI: 10.1007/BF03353003
author: F. Larrión
author: V. Neumann-Lara
published in: Graphs and Combinatorics
publication date: 1998-02-08T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 1106802
zbMATH Keywords: clique divergent graphs
zbMATH Keywords: clique graph
zbMATH Keywords: intersection graph
zbMATH Keywords: polynomial growth
zbMATH Keywords: linear growth
reviewed by: Heinz-Joachim Presia
MaRDI profile type: Publication
cites work: Über iterierte Clique-Graphen
cites work: Q5572939
cites work: Q3786501
cites work: On clique divergent graphs with linear growth
cites work: Q4200112
cites work: Q3037481
cites work: On iterated clique graphs with increasing diameters
full work available at URL: https://doi.org/10.1007/bf03353003
OpenAlex ID: W1992276678
description: scientific article; zbMATH DE number 1106802