2017/11/12 by Saeid Alikhani, Alikhani, Saeid, Davood Fatehi +2
Computer Science · Engineering · #05C69 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1711.04363
openalex publication_date 2017/11/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For a graph G, the k-total dominating graph Dkt(G) is the graph whose vertices correspond to the total dominating sets of G that have cardinality at most k; two vertices of Dkt(G) are adjacent if and only if the corresponding total dominating sets of G differ by either adding or deleting a single vertex. The graph Dkt(G) is used to study the reconfiguration problem for total dominating sets: a total dominating set can be reconfigured to another by a sequence of single vertex additions and deletions, such that the intermediate sets of vertices at each step are total dominating sets, if and only if they are in the same component of Dkt(G). Let d0(G) be the smallest integer r such that Dkt(G) is connected for all k greater than or equal to r. We investigate the realizability of graphs as total dominating graphs. For k the upper total domination number Γt(G), we show that any graph without isolated vertices is an induced subgraph of a graph G such that Dkt(G) is connected. We show that d0(G) lies between Γt(G) and n (inclusive) for any connected graph G of order n at least 3, characterize the graphs for which either bound is realized, and determine d0(Cn) and d0(Pn).