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 141
- Downloads 0
On stability of the Cauchy functional equation in groupoids
We give some stability results for the functional equation $a(xy)=a(x)+a(y)$, where $a:G→E$, $G$ being a groupoid and $E$ a Banach space.
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
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...
Fixed point results satisfying rational type contractive conditions in complex valued metric spaces
The aim of this manuscript is to establish fixed point results satisfying contractive conditions of rational type in the setting of complex valued metric spaces. The derived results generalize and extend some well known...
Linear dependence of powers of linear forms
The main goal of the paper is to examine the dimension of the vector space spanned by powers of linear forms. We also find a lower bound for the number of summands in the presentation of zero form as a sum of d-th powers...