Which Graphs Occur as $$\gamma $$-Graphs?

Autor: Jonathan Jedwab, Samuel Simon, Matt DeVos, Adam Dyck
Rok vydání: 2020
Předmět:
Zdroj: Graphs and Combinatorics. 36:1219-1246
ISSN: 1435-5914
0911-0119
DOI: 10.1007/s00373-020-02174-9
Popis: The $$\gamma $$-graph of a graph G is the graph whose vertices are labelled by the minimum dominating sets of G, in which two vertices are adjacent when their corresponding minimum dominating sets (each of size $$\gamma (G)$$) intersect in a set of size $$\gamma (G)-1$$. We extend the notion of a $$\gamma $$-graph from distance-1-domination to distance-d-domination, and ask which graphs H occur as $$\gamma $$-graphs for a given value of $$d \ge 1$$. We show that, for all d, the answer depends only on whether the vertices of H admit a labelling consistent with the adjacency condition for a conventional $$\gamma $$-graph. This result relies on an explicit construction for a graph having an arbitrary prescribed set of minimum distance-d-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.
Databáze: OpenAIRE
Externí odkaz:
Nepřihlášeným uživatelům se plný text nezobrazuje