Gamma graphs of some special classes of trees
Journal Title: Annales Mathematicae Silesianae - Year 2015, Vol 29, Issue
Abstract
A set $S \subset V$ is a dominating set of a graph $G = (V,E)$ if every vertex $v \in V$ which does not belong to $S$ has a neighbour in $S$. The domination number $\gamma (G)$ of the graph $G$ is the minimum cardinality of a dominating set in $G$. A dominating set $S$ is a $\gamma$-set in $G$ if $jSj = \gamma (G)$. Some graphs have exponentially many $\gamma$-sets, hence it is worth to ask a question if a $\gamma$-set can be obtained by some transformations from another $\gamma$-set. The study of gamma graphs is an answer to this reconfiguration problem. We give a partial answer to the question which graphs are gamma graphs of trees. In the second section gamma graphs $\gamma.T$ of trees with diameter not greater than five will be presented. It will be shown that hypercubes $Q_k$ are among $\gamma.T$ graphs. In the third section $\gamma.T$ graphs of certain trees with three pendant vertices will be analysed. Additionally, some observations on the diameter of gamma graphs will be presented, in response to an open question, published by Fricke et al., if diam$(T(\gamma)) = O(n)$?
Authors and Affiliations
Anna Bień
Keywords
Related Articles
- EP ID EP230395
- DOI 10.1515/amsil-2015-0003
- Views 158
- Downloads 0
Infinite towers of Galois defect extensions of Kaplansky fields
We give conditions for Kaplansky fields to admit infinite towers of Galois defect extensions of prime degree. As proofs of the presented facts are constructive, this provides examples of constructions of infinite towers...
Universally Kuratowski–Ulam spaces and open-open games
We examine the class of spaces in which the second player has a winning strategy in the open-open game. We show that this spaces are not universally Kuratowski–Ulam. We also show that the games $G$ and $G_7$ introduced b...
An extension of a Ger’s result
The aim of this paper is to extend a result presented by Roman Ger during the 15th International Conference on Functional Equations and Inequalities. First, we present some necessary and sufficient conditions for a conti...
The motivic Igusa zeta series of some hypersurfaces non-degenerated with respect to their Newton polyhedron
We describe some algorithms, without using resolution of singularities, that establish the rationality of the motivic Igusa zeta series of certain hypersurfaces that are non-degenerated with respect to their Newton polyh...
Communication complexity and linearly ordered sets
The paper is devoted to the communication complexity of lattice operations in linearly ordered finite sets. All well known techniques ([4, Chapter 1]) to determine the communication complexity of the infimum function in...