Index of parameters of iterated line graphs

Abstract

Let G be a prolific graph, by which we mean a finite connected simple graph which is not isomorphic to a cycle nor a path nor the star graph K1,3. The line-graph of G, denoted by L(G), is defined by having its vertex-set equal to the edge-set of G and two vertices of L(G) are adjacent if the corresponding edges are adjacent in G. For a positive integer k, the iterated line-graph Lk(G) is defined recursively by Lk(G) = L(Lk−1(G)). In this paper we shall consider fifteen well-known graph parameters and study their behaviour when the operation of taking the line-graph is iterated. We shall first show that all of these parameters are unbounded, that is, if P = P(G) is such a parameter defined on any prolific graph G, then P(Lk(G)) → ∞ when k → ∞. This idea of unboundedness is motivated by a well-known old result of van Rooij and Wilf that says that the number of vertices is unbounded if and only if the graph is prolific. Following this preliminary result, the main thrust of the paper will be the study of the value of k(P,F), which is the index of a family of prolific graphs with regards to a given graph parameter P(G). For a given parameter P(G), the index of G is denoted by ind(P, G) = min{r : P(G) < P(Lr(G)}. Now for a family F of prolific graphs, the index of the family is k(P,F) = max{ind(P, G) : G ∈ F}, that is k(P, F ) is the smallest integer k such that for every prolific graphs G ∈ F, ind(P, G) ≤ k(P,F). The problem of determining the index of a parameter over the family of prolific graphs is motivated by a classical result of Chartrand who showed that it could require k = |V (G)| − 3 iterations to guarantee that Lk(G) has a hamiltonian cycle. For twelve of the fifteen parameters considered, we exactly determine k(P,F) where F is the family of all prolific graphs, and for some parameters we also characterize the class of prolific graphs realizing the extremal value k(P,F). For example, for the matching number μ, we show that the index of every prolific graph is at most 4 which is sharp, namely k(μ,F) = 4 and we further characterize those graphs for which ind(μ, G) = 4. Interesting open problems remain, in particular completing the determination of k(P,F) for the three parameters: the independence number, independent domination number and domination number, where we obtain partial results.