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 155
- Downloads 0
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...
The space of real places on ℝ(x, y)
The space $M(ℝ(x, y))$ of real places on $ℝ(x, y)$ is shown to be path-connected. The possible value groups of these real places are determined and for each one it is shown that the set of real places with that value gro...
Reverse Jensen’s type trace inequalities for convex functions of selfadjoint operators in Hilbert spaces
Some reverse Jensen’s type trace inequalities for convex functions of selfadjoint operators in Hilbert spaces are provided. Applications for some convex functions of interest and reverses of Hölder and Schwarz trace ineq...
On Popoviciu-Ionescu functional equation
We study a functional equation first proposed by T. Popoviciu [15] in 1955. It was solved for the easiest case by Ionescu [9] in 1956 and, for the general case, by Ghiorcoiasiu and Roscau [7] and Radó [17] in 1962. Our s...
Report of Meeting. The Sixteenth Debrecen-Katowice Winter Seminar Hernádvécse (Hungary), January 27–30, 2016
Report of Meeting. The Sixteenth Debrecen-Katowice Winter Seminar Hernádvécse (Hungary), January 27–30, 2016