(\gamma\)-Graphs of Trees

For a graph \(G = (V, E)\), the \(\gamma\)-graph of \(G\), denoted \(G(\gamma) = (V(\gamma), E(\gamma))\), is the graph whose vertex set is the collection of minimum dominating sets, or \(\gamma\)-sets of \(G\), and two \(\gamma\)-sets are adjacent in \(G(\gamma)\) if they differ by a single vertex...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2019-07
Main Authors: Finbow, Stephen, van Bommel, Christopher M
Format: Article
Language:English
Subjects:
Algorithms
Apexes
Graphs
Trees (mathematics)
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:For a graph \(G = (V, E)\), the \(\gamma\)-graph of \(G\), denoted \(G(\gamma) = (V(\gamma), E(\gamma))\), is the graph whose vertex set is the collection of minimum dominating sets, or \(\gamma\)-sets of \(G\), and two \(\gamma\)-sets are adjacent in \(G(\gamma)\) if they differ by a single vertex and the two different vertices are adjacent in \(G\). In this paper, we consider \(\gamma\)-graphs of trees. We develop an algorithm for determining the \(\gamma\)-graph of a tree, characterize which trees are \(\gamma\)-graphs of trees, and further comment on the structure of \(\gamma\)-graphs of trees and its connections with Cartesian product graphs, the set of graphs which can be obtained from the Cartesian product of graphs of order at least two.
ISSN:2331-8422
DOI:10.48550/arxiv.1907.03158