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 162
- Downloads 0
Mathematical challenges in the theory of chemotaxis
We consider the simplest parabolic-elliptic model of chemotaxisin the whole space and in several space dimensions. Criteria either for theexistence of radial global-in-time solutions or their blowup in terms of suitable...
On the continuous dependence of solutions to orthogonal additivity problem on given functions
We show that the solution to the orthogonal additivity problem in real inner product spaces depends continuously on the given function and provide an application of this fact.
An infinite natural product
We study a countably infinite iteration of the natural product between ordinals. We present an “effective” way to compute this countable natural product; in the non trivial cases the result depends only on the natural su...
Fixed point theorems for two pairs of mappings satisfying a new type of common limit range property in G_p metric spaces
The purpose of this paper is to prove a general fixed point theorem for mappings involving almost altering distances and satisfying a new type of common limit range property in $G_p$ metric spaces. In the last part of th...
Mathematical models for dynamics of molecular processes in living biological cells. A single particle tracking approach
In this survey paper we present a systematic methodology of how to identify origins of fractional dynamics. We consider three models leading to it, namely fractional Brownian motion (FBM), fractional Lévy stable motion (...