A characterization of graphs with regular distance-2 graphs

For non-negative integers k, we consider graphs in which every vertex has exactly k vertices at distance 2, i.e., graphs whose distance-2 graphs are k-regular. We call such graphs k-metamour-regular motivated by the terminology in polyamory. While constructing k-metamour-regular graphs is relatively easy - we provide a generic construction for arbitrary k - finding all such graphs is much more challenging. We show that only k-metamour-regular graphs with a certain property cannot be built with this construction. Moreover, we derive a complete characterization of k-metamourregular graphs for each k = 0, k = 1 and k = 2. In particular, a connected graph with n vertices is 2-metamour-regular if and only if n >= 5 and the graph is center dot a join of complements of cycles (equivalently every vertex has degree n - 3), center dot a cycle, or center dot one of 17 exceptional graphs with n <= 8. Moreover, a characterization of graphs in which every vertex has at most one metamour is acquired. Each characterization is accompanied by an investigation of the corresponding counting sequence of unlabeled graphs. (c) 2022 The Author(s). Published by Elsevier B.V.