The -graph of a graph is the graph whose vertices are labelled by the minimum dominating sets of , in which two vertices are adjacent when their corresponding minimum dominating sets (each of size ) intersect in a set of size . We extend the notion of a -graph from distance-1-domination to distance--domination, and ask which graphs occur as -graphs for a given value of~. We show that, for all , the answer depends only on whether the vertices of admit a labelling consistent with the adjacency condition for a conventional -graph. This result relies on an explicit construction for a graph having an arbitrary prescribed set of minimum distance--dominating sets. We then completely determine the graphs that admit such a labelling among the wheel graphs, the fan graphs, and the graphs on at most six vertices. We connect the question of whether a graph admits such a labelling with previous work on induced subgraphs of Johnson graphs.

生成讲解博客的中文版本

生成AI智能校验的中文版本