zbMATH — the first resource for mathematics

A family of clique divergent graphs with linear growth. (English) Zbl 0892.05041
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\).

05C75 Structural characterization of families of graphs
Full Text: DOI
[1] Escalante, F, Über iterierte clique-graphen, Abh. Math. Sem. Univ. Hamburg, 39, 58-68, (1973) · Zbl 0266.05116
[2] Harary, F.: Graph Theory. Addison Wesley Publ. Corp. 1969 · Zbl 0182.57702
[3] Hedman, B, Diameters of iterated clique graphs, Hadronic Journal, 9, 273-276, (1986) · Zbl 0644.05032
[4] Larrión, F., Neumann-Lara, V.: On k-divergent graphs with linear growth. (In preparation) · Zbl 0266.05116
[5] Neumann-Lara, V, On clique-divergent graphs. in problèmes combinatories et théorie des graphes (orsay, 1976), Colloques Internationaux C.N.R.S, 260, 313-315, (1978)
[6] NeÜmann-Lara, V, Clique divergence in graphs. in algebraic methods in graph theory. (Szeged, 1978), Colloquia Mathematica Societatis Jânos Bolyai, 25, 563-569, (1981)
[7] Neumann-Lara, V, Clique divergence in graphs. some variations, Publ. Prelim. Inst. Mat. U.N.A.M, 224, 1-14, (1991)
[8] Peyrat, C; Rail, DF; Slater, PJ, On iterated clique graphs with increasing diameters, J. of Graph Theory, 10, 167-171, (1986) · Zbl 0596.05036
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.