On fixing sets of composition and corona product of graphs

I. Javaid; M. S. Aasi; I. Irshad; M. Salman

paper

On fixing sets of composition and corona product of graphs

arXiv:1507.02053

Abstract

A fixing set $F$ of a graph $G$ is a set of those vertices of the graph $G$ which when assigned distinct labels removes all the automorphisms from the graph except the trivial one. The fixing number of a graph $G$ , denoted by $f i x (G)$ , is the smallest cardinality of a fixing set of $G$ . In this paper, we study the fixing number of composition product, $G_{1} [G_{2}]$ and corona product, $G_{1} ⊙ G_{2}$ of two graphs $G_{1}$ and $G_{2}$ with orders $m$ and $n$ respectively. We show that for a connected graph $G_{1}$ and an arbitrary graph $G_{2}$ having $l \geq 1$ components $G_{2}^{1}$ , $G_{2}^{2}$ , ... $G_{2}^{l},$ $mn - 1 \geq f i x (G_{1} [G_{2}]) \geq m (i = 1 \sum l f i x (G_{2}^{i}))$ . For a connected graph $G_{1}$ and an arbitrary graph $G_{2}$ , which are not asymmetric, we prove that $f i x (G_{1} ⊙ G_{2}) = m f i x (G_{2})$ . Further, for an arbitrary connected graph $G_{1}$ and an arbitrary graph $G_{2}$ we show that $f i x (G_{1} ⊙ G_{2}) = ma x {f i x (G_{1}), m f i x (G_{2})}$ .

12 pages

Cited by in corpus (1)

On the Fractional fixing number of graphs