## DISTINGUISHING NUMBER OF NON-ZERO COMPONENT GRAPHS

I. JAVAID , M. MURTAZA, H. BENISH ∗

Abstract. A non-zero component graph G ( V ) associated to a finite vector space V is a graph whose vertices are non-zero vectors of V and two vertices are adjacent, if their corresponding vectors have at least one non-zero component common in their linear combination of basis vectors. In this paper, we extend the study of properties of automorphisms of non-zero component graphs. We prove that every permutation of basis vectors can be extended to an automorphism of G ( V ). We prove that the symmetric group of basis vectors of V is isomorphic to the automorphism group of G ( V ). We find the distinguishing number of the graph for both of the cases, when the number of field elements of vector space V are 2 or more than 2.

## 1. Preliminaries

The association of graphs with algebraic structures has become an interesting research topic for the past few decades. See for instance: the study of zero-divisor graphs of commutative rings with unity was initiated by Beck [4] to discuss coloring problem. Commuting graphs associated to symmetric groups were studied by Bondy et al. [3, 6], where the authors discussed connectivity and related properties of these graphs. Power graphs for groups and semigroups were discussed in [7, 8, 14]. Intersection graphs associated to vector spaces were studied in [13, 17]. Das assigned non-zero component graphs to finite dimensional vector spaces in [9]. The author also studied its domination number and independence number. In [10], the author discussed edge-connectivity and the chromatic number of the graph. Nonzero component graphs have very interesting symmetrical structures especially for the case where the number of field elements of vector space is 2. Several authors studied non-zero component graphs for different graph parameters. For instance, metric dimension and partition dimension of non-zero component graphs are studied in [2]. Fixing number of the graph is studied in [11]. Locating-dominating sets and identifying codes of non-zero component graphs are discussed by Murtaza et al. [15]. Automorphisms of non-zero component graphs are studied by Hira et al. in [5], where the authors studied the fixing neighborhoods of pairs of vertices of the

Key words and phrases. Automorphism, distinguishing labeling, distinguishing number. 2010 Mathematics Subject Classification. 05C25

∗ Corresponding author: ijavaidbzu@gmail.com.

graph and the fixed number of the graph. In this paper, we extend the study of properties of automorphisms non-zero component graphs. We find the cardinality of the automorphism group of the graph, distinguishing number of the graph and prove that the automorphism group of the graph is destroyed by only 2 colors for the case where the number of field elements are 2.

How many colors are needed to identify apparently same keys of a key ring? The first time this question was discussed by Rubin [16] in 1980. The problem was transformed into other problems like scheduling meetings, storing chemicals and solution to these problems need proper coloring and one with a small number of colors. Motivated by this problem, Albertson, and Collins [1] introduced the concept of the distinguishing number of a graph as follows: A labeling f : V ( G ) → { 1 2 3 , , , ..., t } is called a t -distinguishing if no non-trivial automorphism of a graph G preserves the vertex labels. The distinguishing number of a graph G , denoted by Dist G ( ), is the least integer t such that G has t -distinguishing labeling. The distinguishing number of a complete graph K n is n , the distinguishing number of a path graph P n is 2 and the distinguishing number of a cyclic C , n n ≥ 6 is 2. For a graph G of order n , 1 ≤ Dist G ( ) ≤ n [1].

/negationslash

Now, we define some graph related terminology which is used in this article: Let G be a graph with the vertex set V ( G ) and the edge set E G ( ). Two vertices u and v are adjacent , if they share an edge, otherwise they are called non-adjacent . The number of adjacent vertices of a vertex v is called the degree of v in G . For a graph G , an automorphism of G is a bijective mapping f on V ( G ) such that f ( u f ) ( v ) ∈ E G ( ) if and only if uv ∈ E G ( ). The set of all automorphisms of G forms a group, denoted by Γ( G ), under the operation of composition. For a vertex v of G , the set { f ( v ) : f ∈ Γ( G ) } is the orbit of v , denoted by O ( v ). If two vertices u, v are mapped on each other under the action of an automorphism g ∈ Γ( G ), then we write it u ∼ g v . If u, v cannot be mapped on each other, then we write u /notsimilar g v . An automorphism g ∈ Γ( G ) is said to fix a vertex v ∈ V ( G ) if v ∼ g v . The stabilizer of a vertex v is the set of all automorphisms that fix v and it is denoted by Γ ( v G ). Also, Γ ( v G ) is a subgroup of Γ( G ). Let us consider sets S G ( ) = { v ∈ V ( G ) : |O ( v ) | ≥ 2 } and V s ( G ) = { ( u, v ) ∈ S G ( ) × S G ( ) : u = v and O ( u ) = O ( v ) } . If G is a rigid graph (i.e., a graph with Γ( G ) = id ), then V s ( G ) = ∅ . For v ∈ V ( G ), the subgroup Γ ( v G ) has a natural action on V ( G ) and the orbit of u under this action is denoted by O v ( u ) i.e., O v ( u ) = { g u ( ) : g ∈ Γ ( v G ) } . An automorphism g ∈ Γ( G ) is said to fix a set D ⊆ V ( G ) if for all v ∈ D v , ∼ g v . The set of automorphisms that fix D , denoted by Γ D ( G ), is a subgroup of Γ( G ) and Γ D ( G ) = ∩ v ∈ D Γ ( v G ).

Throughout the paper, V denotes a vector space of dimension n over the field of q elements and { b , b 1 2 , ..., b n } be a basis of V . The non-zero component graph of V [9], denoted by G ( V ), is a graph whose vertex set consists of non-zero vectors of V and two vertices are joined by an edge if they share at least one b i with

non-zero coefficient in their unique linear combination with respect to basis vectors { b , b 1 2 , . . . , b n } . It is proved in [9] that G ( V ) is independent of the choice of basis, i.e., isomorphic non-zero component graphs are obtained for two different bases. In [9], Das studied automorphisms of G ( V ). It was shown that an automorphism maps basis of G ( V ) to a basis of a special type, namely non-zero scalar multiples of a permutation of basis vectors.

Theorem 1.1. [9] Let ϕ : G ( V ) → G ( V ) be a graph automorphism. Then, ϕ maps a basis { α , α , ..., α 1 2 n } of V to another basis { β , β 1 2 , ..., β n } such that there exists a permutation σ from the symmetric group on n elements, where each β i is of the form c α i σ i ( ) and each c i 's are non-zero.

The skeleton of a vertex u ∈ V ( G ( V )) denoted by S u , is the set of all those basis vectors of V which have non-zero coefficients in the representation of u as the linear combination of basis vectors. In [15], we partition the vertex set of G ( V ) into n classes T i , (1 ≤ i ≤ n ), where T i = { v ∈ V : | S v | = i } . For example, if n = 4 and q = 2, then T 3 = { b 1 + b 2 + b , b 3 1 + b 2 + b , b 4 1 + b 3 + b , b 4 2 + b 3 + b 4 } .

The section wise break up of the article is as follows: In Section 2, we study the properties of automorphisms of non-zero component graph. We discuss the relation between vertices and their images under an automorphism of G ( V ) in the terms of their skeletons. We prove that every permutation of basis vectors can be extended to an automorphism of G ( V ). We also prove that the symmetric group of basis vectors is isomorphic to the automorphism group of G ( V ). We find the cardinality of automorphism group of G ( V ). In Section 3, we study distinguishing labelings and distinguishing number of non-zero component graphs for both of the cases, when the number of field elements of vector space V are 2 or more than 2.

## 2. Automorphisms of non-zero component graph

In [5], we study the properties of automorphisms of G ( V ) of a vector space V of dimension n ≥ 3 over the field of 2 elements. Graphs G ( V ) have more interesting symmetrical structures for the case where the number of field elements are 2, as compared to the cases where the number of field elements are more than 2, as G ( V ) does not have twin vertices in the former case. In this section, we extend the study of the properties of automorphisms of G ( V ), where V is a vector space of dimension n over the field of 2 elements.

$$\text{Lemma $2.1. $[15] If $v\in T_{s}$ for $s\ (1\leq s\leq n)$, then $deg(v)= (2^{s}-1)2^{n-s}-1$.}$$

/negationslash

/negationslash

Lemma 2.2. [5] Let u, v ∈ V ( G ( V )) such that u ∈ T r and v ∈ T s where r = s and 1 ≤ r, s ≤ n , then u ∼ g v for all g ∈ Γ( G ( V )) .

From Lemma 2.2, we have the following straightforward remark.

Remark 2.3. [5] Since u ∈ T n where S u = { b , b 1 2 , ..., b n } is the only element in T n . Therefore, by Lemma 2.2, g u ( ) = u for all g ∈ Γ( G ( V )) .

Lemma 2.4. [5] Let b l ∈ T 1 be a basis vector and g ∈ Γ b l . Let u ∈ V ( G ( V )) , then b l ∈ S u if and only if b l ∈ S g u ( ) .

Lemma 2.5. [5] Let u, v ∈ T i for some i (1 ≤ i ≤ n -1) and u ∼ g v for some g ∈ Γ( G ( V )) . The following statements hold:

- (i) If b ∈ S u ∩ S v , then g b ( ) ∈ S u ∩ S v .
- (ii) If b ∈ S u -S v , then g b ( ) ∈ S v -S u .

Lemma 2.6. [5] Let b , b l m ∈ T 1 be two distinct basis vectors of V and g ∈ Γ( G ( V )) be an automorphism such that b l ∼ g b m . Let u ∈ V ( G ( V )) , then we have:

/negationslash

- (i) If b l ∈ S u and b m ∈ S u , then b l ∈ S g u ( ) and b m ∈ S g u ( ) .

/negationslash

- (ii) b , b l m ∈ S u if and only if b , b l m ∈ S g u ( ) .

Lemma 2.7. Let b , b l m ∈ T 1 be two distinct basis vectors, then there exist ( n -1 i -1 ) -( n -2 i -2 ) pairs of distinct vertices u, v ∈ T i for each i (1 ≤ i ≤ n -1) , such that b l ∈ S u \ S v and b m ∈ S v \ S u .

Proof. For i = 1, b l ∈ S b l \ S b m and b m ∈ S b m \ S b l . For 2 ≤ i ≤ n -1, there are ( ) n i vertices in each T i and out of these ( ) n i vectors, there are ( n -1 i -1 ) vectors that contain b l in their skeletons. Similarly, there are ( n -1 i -1 ) vectors in each T i that contain b m in their skeletons. Also, there are ( n -2 i -2 ) vectors that contain both b l and b m in their skeletons. Thus, there are ( n -1 i -1 ) -( n -2 i -2 ) vectors in each T i that contain b l and but not b m in their skeletons. /square

The following Lemma shows that every non-trivial automorphism g of G ( V ) does not belongs to the stabilizer of at least two of the basis vectors, i.e., g moves at least two basis vectors from their places.

Lemma 2.8. Let g ∈ Γ( G ( V )) be a non-trivial automorphism, there exist at least two distinct basis vectors b , b l m ∈ T 1 , such that g b ( l ) = b m .

Proof. Since g is non-trivial, therefore there exist distinct vectors u, v ∈ V ( G ( V )), such that g u ( ) = v . Also, by the contrapositive argument of Lemma 2.2, both u and v belong to the same class T i for some i , 1 ≤ i ≤ n -1. If i = 1, then the result is obvious. Therefore, we assume 2 ≤ i ≤ n -1. Since u and v are distinct, therefore S u -S v is non-empty. Let b l ∈ S u -S v , then b l is adjacent to u and non-adjacent to v . Since g is an automorphism, therefore g b ( l ) is adjacent g u ( ) = v but non-adjacent to g v ( ). Thus, g b ( l ) ∈ S v -S g v ( ) . Clearly, b l and g b ( l ) = b m (say) are distinct basis vectors because if g b ( l ) = b l , then b l ∈ S v , a contradiction. Hence, proved. /square

The next result shows that every permutation of basis vectors can be extended to an automorphism of non-zero component graph.

Theorem 2.9. Every permutation of basis vectors of G ( V ) can be extended to an automorphism of G ( V ) .

/negationslash

/negationslash

/negationslash

Proof. Let h be a permutation of basis vectors. Let u ∈ V ( G ( V )) be an arbitrary vertex, then u ∈ T m for some m , 1 ≤ m ≤ n . Let S u = { b , b 1 2 , ..., b m } . We define an extension g : V ( G ( V )) → V ( G ( V )) of h on vertex set V ( G ( V )) as g u ( ) = v , where v is a vector whose skeleton is S v = { h b ( 1 ) , h ( b 2 ) , ..., h ( b m ) } . We claim that g is an automorphism of G ( V ). If u is a basis vector, then g u ( ) = h u ( ). Let u , u 1 2 ∈ T m be two distinct vectors, then S u 1 = S u 2 . Since h is a permutation on basis vectors, therefore S g u ( 1 ) = S g u ( 2 ) ⇒ g u ( 1 ) = g u ( 2 ). Now, we show that g preserves the relation of adjacency. Let u, v, w ∈ V ( G ( V )) be any three vertices such that u is adjacent v and non-adjacent to w . Then S u ∩ S v = ∅ and S u ∩ S w = ∅ . Since h is a permutation, therefore disjoint sets of basis vectors have disjoint image sets and overlapping sets of basis vectors have overlapping image sets under permutation h . Thus, S g u ( ) ∩ S g v ( ) = ∅ and S g u ( ) ∩ S g w ( ) = ∅ and hence, g u ( ) is adjacent to g v ( ) and g u ( ) is non-adjacent to g w ( ). Hence, g preserves the relation of adjacency and non-adjacency among the vertices of G ( V ). /square

/negationslash

/negationslash

Corollary 2.10. Every automorphism of G ( V ) can be restricted to a permutation of basis vectors.

Proof. Let g ∈ Aut G ( ( V )) be an arbitrary automorphism. Since every automorphism is itself a permutation on the vertex set of G ( V ), therefore the restriction of g on the elements of T 1 forms a permutation h of basis vectors. /square

Let Sym denotes the symmetric group basis vectors { b , b 1 2 , ..., b n } , then the following theorem shows that the symmetric group of basis vectors is isomorphic to the automorphism group of the graph.

Theorem 2.11. The symmetric group of basis vectors { b , b 1 2 , ..., b n } is isomorphic to the automorphism group of G ( V ) .

$$S y m \cong A u t ( G ( \mathbb { V } ) )$$

.

Proof. Let h ∈ Sym be a permutation of basis vectors. Also let g ∈ Aut G ( ( V )). We define a function ψ : Sym → Aut G ( ( V )) as ψ h ( ) = g , where g is the extension of h as defined in Theorem 2.9, i.e., action of g on a vertex u is defined by the action of permutation h on the elements of basis vectors in the skeleton of u . We claim that ψ is a bijective function.

/negationslash

/negationslash

- (1) ψ is well defined : Let g , g 1 2 ∈ Aut G ( ( V )) such that g 1 = g 2 . Let h , h 1 2 ∈ Sym be two permutations of basis vectors such that g 1 is the extension of h 1 and g 2 is the extension of h 2 . Since g 1 = g 2 , therefore there exist a vertex u ∈ T m for some m , 1 ≤ m ≤ n -1 such that g 1 ( u ) = g 2 ( u ). Let

/negationslash

/negationslash

/negationslash

/negationslash

- S u = { b , b 1 2 , ..., b m } . Then S g 1 ( u ) = S g 2 ( u ) ⇒ { h 1 ( b 1 ) , h 1 ( b 2 ) , ..., h 1 ( b m ) } /negationslash = { h 2 ( b 1 ) , h 2 ( b 2 ) , ..., h 2 ( b m ) } ⇒ h 1 ( b j ) = h 2 ( b j ) for at least one j , (1 ≤ j ≤ m ) ⇒ h 1 = h 2 .

/negationslash

/negationslash

/negationslash

- (2) ψ is one-one : Let h , h 1 2 ∈ Sym be two permutations such that h 1 = h 2 . Let g 1 and g 2 be the extensions of h 1 and h 2 , respectively. Since h 1 = h 2 , therefore h 1 ( b j ) = h 2 ( b j ) for at least one j , (1 ≤ j ≤ m ) ⇒ { h 1 ( b 1 ) , h 1 ( b 2 ) , ..., h 1 ( b m ) } /negationslash = { h 2 ( b 1 ) , h 2 ( b 2 ) , ..., h 2 ( b m ) } ⇒ S g 1 ( u ) = S g 2 ( u ) ⇒ g 1 ( u ) = g 2 ( u ) ⇒ g 1 = g 2 .

/negationslash

/negationslash

/negationslash

- (3) ψ is onto : By Corollary 2.10 the restriction of every automorphism g ∈ Aut G ( ( V )) forms a permutation h of basis vectors. Therefore, g is an extension of permutation h of basis vectors. Thus, for an automorphism g ∈ Aut G ( ( V )), there exist a permutation h ∈ Sym such that ψ h ( ) = g .
- (4) ψ is homomorphism : Let h , h 1 2 ∈ Sym and g , g 1 2 ∈ Aut G ( ( V )) such that g 1 and g 2 are the extension automorphisms of h 1 and h 2 , respectively, as defined in Theorem 2.9. We claim that ψ h h ( 1 2 ) = ψ h ( 1 ) ψ h ( 2 ) = g g 1 2 . Let ψ h h ( 1 2 ) = g and u ∈ T m for some m , 1 ≤ m ≤ n -1 such that S u = { b , b 1 2 , ..., b m } . Then g u ( ) has skeleton S g u ( ) = { h h 1 2 ( b 1 ) , h 1 h 2 ( b 2 ) , ..., h 1 h 2 ( b m ) } = { h 1 ( h 2 ( b 1 )) , h 1 ( h 2 ( b 2 )) , ..., h 1 ( h 2 ( b m )) } = S g 1 ( g 2 ( u )) = S g 1 g 2 ( u ) ⇒ g = g g 1 2 ⇒ ψ h h ( 1 2 ) = ψ h ( 1 ) ψ h ( 2 ).

Thus, ψ is an isomorphism between Sym and Aut G ( ( V

)). /square

Theorem 2.11 leads to the following straight forward result.

Theorem 2.12. Non-zero component graph G ( V ) has n ! automorphisms.

$$| A u t ( G ( \mathbb { V } ) ) | = n!$$

Proof. Proof simply follows from the fact that the symmetric group of basis vectors has n ! elements and the symmetric group of basis vectors is isomorphic to the automorphism group of the graph. /square

## 3. Distinguishing labeling of non-zero component graph

We have seen in the previous section that the symmetric group of basis vectors is isomorphic to the automorphism group of non-zero component graph of a vector space of dimension n ≥ 3 over the field of 2 element. Therefore, it is sufficient to destroy the symmetric group of basis vectors, in order to destroy the automorphism group of G ( V ). In this section, we again consider the case where V is a vector space over the field of 2 elements except for Theorem 3.4 where field elements are more than 2. We use distinguishing labeling with the minimum number of labels (or colors) to destroy the symmetric group of basis vectors which leads us to destroy the automorphism group of the graph.

/negationslash

/negationslash

Lemma 3.1. Let b , b l m ∈ T 1 be two distinct basis vectors of V and u, v ∈ T i for some i (2 ≤ i ≤ n -1) such that b l ∈ S u \ S v and b m ∈ S v \ S u . Let f : V ( G ( V )) →{ 1 2 , } be a labeling such that f ( u ) = f ( v ) , then f breaks all automorphisms g ∈ Aut G ( ( V )) which maps b l and b m on each other, i.e., b l ∼ b m .

/negationslash

/negationslash

Proof. If f ( u ) = f ( v ), then u and v have different labels, therefore these cannot map on each other and labeling f breaks all the automorphisms that map u and v on each other. Since b l is adjacent to u but non-adjacent to v and b m is adjacent to v but non-adjacent to u and u and v cannot map on each other, therefore by Lemma 2.6(i), b l and b m cannot map on each other, as the automorphisms in Aut G ( ( V )) that maps b l and b m are broken by labeling f . Hence, b l ∼ b m . /square

Since every permutation of basis vectors can be written as the product of transpositions of basis vectors, therefore we label the vertices of G ( V ) with labeling f in such a way that all those automorphisms of G ( V ) are destroyed that contain transpositions of basis vectors.

Theorem 3.2. Let G ( V ) be the non-zero component graph of a vector space of dimension n ≥ 3 over the field of 2 elements. Then Dist G ( ( V )) = 2 .

Proof. Since G ( V ) is not a rigid graph, therefore Dist G ( ( V )) ≥ 2. We define labeling f : V ( G ( V )) →{ 1 2 , } in such a way that after assigning the labels to the vertices of G ( V ), all those automorphisms of G ( V ) are destroyed that contain transpositions of basis vectors. There are ( ) n 2 transpositions of basis vectors. We proceed by assigning labels to the vertices of classes T 1 , T n -1 , T 2 .

- (1) Labeling the vertices of T 1 : Consider labeling f defined on the vertices of T 1 , i.e., basis vectors as:

$$f ( b _ { i } ) = \begin{cases} \ 1 & i f \quad 1 \leq i \leq \lfloor \frac { n } { 2 } \rfloor \\ 2 & i f \quad \lfloor \frac { n } { 2 } \rfloor + 1 \leq i \leq n \end{cases}$$

/negationslash

Since, basis vectors b i , for all i (1 ≤ i ≤ /floorleft n 2 /floorright ) have different labels from the labels of b j , for all j ( /floorleft n 2 /floorright +1 ≤ j ≤ n ), therefore b i ∼ b j for all i, j ( i = j ) where (1 ≤ i ≤ /floorleft n 2 /floorright ) and ( /floorleft n 2 /floorright + 1 ≤ j ≤ n ) under all automorphisms of Aut G ( ( V )). If n is even, then ( ) n 2 -2 ( n 2 2 ) = n 2 4 transpositions of basis vectors are destroyed by labeling the vertices of T 1 . If n is odd, then ( ) n 2 -( /floorleft n 2 /floorright 2 ) -( /floorleft n 2 /floorright +1 2 ) = n 2 -1 4 transpositions of basis vectors are destroyed by labeling the vertices of T 1 .

/negationslash

- (2) Labeling the vertices of T n -1 : We label the vertices u ∈ T n -1 as:

$$f ( u ) = \begin{cases} \ 1 & i f \ \ S _ { u } = \{ b _ { 2 }, b _ { 3 }, \dots, b _ { \lfloor \frac { n } { 2 } \rfloor } \} \ o r \ S _ { u } = \{ b _ { \lfloor \frac { n } { 2 } \rfloor + 2 }, b _ { \lfloor \frac { n } { 2 } \rfloor + 3 }, \dots, b _ { n } \} \\ 2 & i f \ \ o t h e r w i s e \end{cases}$$

/negationslash

Consider u, v ∈ T n -1 such that S u = { b , b 2 3 , ..., b /floorleft n 2 /floorright } and S v = { b , b 1 3 , b 4 , ..., b /floorleft n 2 /floorright } , then f ( u ) = f ( v ). Also, b 2 ∈ S u \ S v and b 1 ∈ S v \ S u . Therefore,

/negationslash

/negationslash

/negationslash by Lemma 3.1 labeling f breaks the automorphisms that map b 1 and b 2 on each other (reader can notice that, even basis vectors b 1 and b 2 have same label 1 assigned by labeling f , but the automorphism that maps b 1 and b 2 on each other is destroyed due to f ( u ) = f ( v )). Thus, b 1 ∼ b 2 . In the similar way, reader can verify b 1 ∼ b j where 3 ≤ j ≤ /floorleft n 2 /floorright and b /floorleft n 2 /floorright +1 ∼ b k where /floorleft n 2 /floorright + 2 ≤ k ≤ n . There are n -2 transposition of basis vectors that are destroyed by labeling the vertices of T n -1 .

/negationslash

- (3) Labeling the vertices of T 2 : We label the vertices u ∈ T 2 as:

$$f ( u ) = \begin{cases} \ 1 & i f \ \ S _ { u } = \{ b _ { i }, b _ { i + 1 } \} \ w h e r e \ 1 \leq i \leq n - 1 \\ 2 & i f \ \ o t h e r w i s e \end{cases}$$

/negationslash

/negationslash

We claim that labeling f defined on the vertices of T 2 destroys the remaining transpositions of basis vectors. The remaining transpositions of basis vectors are b i ∼ b j where i = j (2 ≤ i, j ≤ /floorleft n 2 /floorright ) and b i ∼ b j where i = j ( /floorleft n 2 /floorright +1 ≤ i, j ≤ n ). Consider the first case and let b l ∼ b m for some l = m (2 ≤ l, m ≤ /floorleft n 2 /floorright ). Then there exist vertices u, v ∈ T 2 such that S u = { b l -1 , b l } and S v = { b l -1 , b m } . Then by the definition of labeling f , f ( u ) = 1 = 2 = f ( v ) and b l ∈ S u \ S v and b m ∈ S v \ S u . Hence by Lemma 3.1, labeling f breaks the automorphism that maps b l and b m on each other. Similarly, for the second case, let b l ∼ b m for some l = m ( /floorleft n 2 /floorright + 1 ≤ l, m ≤ n ) and using the same arguments as in the first case we see that labeling f breaks the automorphism that map b l and b m on each other. Thus, all the remaining transpositions of basis vectors are destroyed by labeling f . If n is even, then ( ) n 2 -n 2 4 -( n -2) = n 2 -6 n +8 4 transpositions of basis vectors are destroyed by labeling the vertices of T 2 . Similarly, if n is odd, then ( ) n 2 -n 2 -1 4 -( n -2) = n 2 -6 n +9 4 transpositions of basis vectors are destroyed by labeling the vertices of T 2 .

/negationslash

/negationslash

- (4) Labeling the vertices of T 3 ,..., T n -2 , T n : The vertices in the remaining classes T 3 ,..., T n -2 , T n can be labeled with any one label 1 or 2.

We have seen that labeling f destroys all possible transpositions of basis vectors and hence destroys the permutation group of basis vectors. Thus, by Theorem 2.11, the automorphism group of G ( V ) is destroyed by labeling f . Hence, f is a 2-distinguishing labeling of G ( V ) and consequently, Dist G ( ( V )) = 2.

/square

We now discuss the case when G ( V ) is non-zero component graph of vector space V where n ≥ 3 and q ≥ 3. Since G ( V ) has ( ) n i twin sets in classes T i for each i (1 ≤ i ≤ n ). Also each of these twin sets has ( q -1) i number of vertices. Let T i k 1 ≤ k ≤ ( ) n i denotes the k th twin set in class T i . Since at least m labels are required to label a twin set of cardinality m , therefore we have the following result for the distinguishing number of a graph which has twin sets.

/negationslash

Proposition 3.3. [12] Let W ,W ,..., W 1 2 t are disjoint twin sets of connected graph G and m = max {| W i | : where 1 ≤ i ≤ } t , then Dist G ( ) ≥ m .

Theorem 3.4. Let G V be the non-zero component graph of vector space V of dimension n ≥ 3 and q ≥ 3 . Then Dist G ( ( V )) = ( q -1) n

Proof. Since twin sets T i k (1 ≤ i ≤ n ) (1 ≤ k ≤ ( ) n i ) are disjoint and each contains ( q -1) i twin vertices. Also, ( q -1) n = max {| T i k | : (1 ≤ i ≤ n ) } . Therefore, by Proposition 3.3, Dist G ( ( V )) ≥ ( q -1) n . Also, ( q -1) n ≥ ( q -1) i for all i (1 ≤ i ≤ n ), therefore twin sets T i k are independently labeled by ( q -1) i labels out of ( q -1) n labels. Thus, all automorphisms of disjoint twin sets T i k are destroyed. Hence, Dist G ( V ) = ( q -1) n . /square

## Acknowledgments

This research was supported by Higher Education Commission of Pakistan with grant no. 7354/Punjab/NRPU/R&amp;D/HEC/2017.

## References

- [1] M. O. Albertson, K. Collins, Symmetry breaking in graphs, Electron. J. Combin., 3 (1996), R 18.
- [2] U. Ali, S. A. Bokhary, K. Wahid, G. Abbas, On resolvability of a graph associated to a finite vector space, J. Algebra Appl. , 1950029.
- [3] C. Bates, D. Bondy, S. Perkins and P. Rowley, Commuting involution graphs for symmetric groups, J. Algebra. , 266(2003), 133-153.
- [4] I. Beck, Coloring of commutative rings, J. Algebra. , 116(1988), 208-226.
- [5] H. Benish, I. Javaid, M. Murtaza, Automorphism related parameters of a graph associated to a finite vector space, accepted for publication in Utilitas Mathematica.
- [6] D. Bondy, The connectivity of commuting graphs, J. Combin. Theory Ser. A. , 113(2006), 995-1007.
- [7] P. J. Cameron and S. Ghosh, The power graph of a finite group, Disc. Math. , 311(2011), 1220-1222.
- [8] I. Chakrabarty, S. Ghosh and M. K. Sen, Undirected power graphs of semi group, Semi group. Forum. , 78(2009), 410-426.
- [9] A. Das, Non-Zero component graph of a finite dimensional vector space, Communi. in Algebra. , 44(2016), 3918-3926.
- [10] A. Das, On non-zero component graph of vector spaces over finite fields, J. Algebra Appl. , 2016, 1750007.
- [11] M. Fazil, Determining sets and related parameters in graphs, PhD Thesis.
- [12] M. Fazil, M. Murtaza, Z. Ullah, U. Ali and I. Javaid, On the distinguishing number of functigraphs, Symmetry , 10(8), 2018, p.332.
- [13] N. Jafari Rad and S. H. Jafari, Results on the intersection graphs of subspaces of a vector space, http://arxiv.org/abs/1105.0803v1.
- [14] A. R. Moghaddamfar, S. Rahbariyan and W. J. Shi, Certain properties of the power graph associated with finit group, J. Algebra Appl. , 13(2014), 450040.
- [15] M. Murtaza, I. Javaid and M. Fazil, Locating-dominating sets and identifying codes of a graph associated to a finite vector space, arXiv preprint arXiv:1701.08537, (2017).

- [16] F. Rubin, The blind man's keys. Journal of Recreational Maths 12(1980).
- [17] Y. Talebi, M.S. Esmaeilifar and S. Azizpour, A kind of intersection graph of vector space, J. Disc. Math. Sci. Crypt., 12, 6(2009), 681-689.

Centre for advanced studies in Pure and Applied Mathematics, Bahauddin Zakariya University Multan, Pakistan

Email: ijavaidbzu@gmail.com, mahru830@gmail.com, hira benish@yahoo.com.
I. Javaid M. Murtaza H. Benish
Distinguishing Number of Non-Zero Component Graphs
A non-zero component graph $G(\mathbb{V})$ associated to a finite vector
space $\mathbb{V}$ is a graph whose vertices are non-zero vectors of
$\mathbb{V}$ and two vertices are adjacent, if their corresponding vectors have
at least one non-zero component common in their linear combination of basis
vectors. In this paper, we extend the study of properties of automorphisms of
non-zero component graphs. We prove that every permutation of basis vectors can
be extended to an automorphism of $G(\mathbb{V})$. We prove that the symmetric
group of basis vectors of $\mathbb{V}$ is isomorphic to the automorphism group
of $G(\mathbb{V})$. We find the distinguishing number of the graph for both of
the cases, when the number of field elements of vector space $\mathbb{V}$ are 2
or more than 2.