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

Refinements of the Hermite–Hadamard inequality in NPC global spaces

In this paper we establish different refinements and applications of the Hermite–Hadamard inequality for convex functions in the context of NPC global spaces.

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...

Report of Meeting. The Eighteenth Debrecen–Katowice Winter Seminar on Functional Equations and Inequalities Hajdúszoboszló (Hungary), January 31–February 3, 2018

Report of Meeting. The Eighteenth Debrecen–Katowice Winter Seminar on Functional Equations and Inequalities Hajdúszoboszló (Hungary), January 31–February 3, 2018.

Multi ping-pong and an entropy estimate in groups

We provide an entropy estimate from below for a finitely generated group of transformation of a compact metric space which contains a ping-pong game with several players located anywhere in the group.

Lie derivations on trivial extension algebras

In this paper we provide some conditions under which a Lie derivation on a trivial extension algebra is proper, that is, it can be expressed as a sum of a derivation and a center valued map vanishing at commutators. We t...

Download PDF file
  • EP ID EP230395
  • DOI 10.1515/amsil-2015-0003
  • Views 163
  • Downloads 0

How To Cite

Anna Bień (2015). Gamma graphs of some special classes of trees. Annales Mathematicae Silesianae, 29(), 25-34. https://europub.co.uk/articles/-A-230395