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 166
- Downloads 0
An application of the theory of scale of Banach spaces
The abstract Cauchy problem on scales of Banach space was considered by many authors. The goal of this paper is to show that the choice of the space on scale is significant. We prove a theorem that the selection of the s...
Fixed point results satisfying rational type contractive conditions in complex valued metric spaces – revisited
In our previous work titled “Fixed Point Results Satisfying Rational type Contractive Conditions in Complex Valued Metric Spaces” [Ann. Math. Sil. 30 (2016), 89–110], some errors has been made in the main results (Theore...
A general fixed point theorem for implicit cyclic multi-valued contraction mappings
In this paper, a general fixed point theorem for cyclic multi-valued mappings satisfying an implicit relation from [19] different from implicit relations used in [13] and [23], generalizing some results from [22], [15],...
Stability of functional equations in dislocated quasi-metric spaces
We present a result on the generalized Hyers–Ulam stability of a functional equation in a single variable for functions that have values in a complete dislocated quasi-metric space. Next, we show how to apply it to prove...
On computer-assisted proving the existence of periodic and bounded orbits
We announce a new result on determining the Conley index of the Poincaré map for a time-periodic non-autonomous ordinary differential equation. The index is computed using some singular cycles related to an index pair of...