Independent Domination under Iterated Line Graphs: The Regular Case

Abstract

Version 1.0.0. For a graph parameter P and a prolific graph G, Caro, Lauri and Zarb defined the index ind(P,G) as the first iterated line graph on which P exceeds its value on G. This preprint determines the independent-domination index on the class of connected regular graphs of degree at least three. If G is a connected k-regular graph with k at least 3, then ind(i,G) is at most 2 unless G is isomorphic to K3,3, while ind(i,K3,3)=3. Consequently, the independent-domination index of the regular family is exactly 3, and K3,3 is the unique extremal graph. The proof uses the identity between independent domination in a line graph and the minimum cardinality of a maximal matching, a counting lower bound for minimum maximal matchings in regular graphs, and the sharp upper bound of Cho, Choi and Park for independent domination in regular graphs. The full index problem over all prolific graphs remains open. The deposit contains the manuscript PDF, source materials, a minimal arXiv source package, and SHA-256 checksums.