# Automorphism Group and Other Properties of Zero Component Graph over a Vector Space

Authors: Shikun Ou; Yanqi Fan; Qunfang Li
Journal: Journal of Mathematics
 (2021)

---

## Abstract

In this paper, we introduce an undirected simple graph, called the zero component graph on finite-dimensional vector spaces. It is shown that two finite-dimensional vector spaces are isomorphic if and only if their zero component graphs are isomorphic, and any automorphism of a zero component graph can be uniquely decomposed into the product of a permutation automorphism and a regular automorphism. Moreover, we find the dominating number, as well as the independent number, and characterize the minimum independent dominating sets, maximum independent sets, and planarity of the graph. In the case that base fields are finite, we calculate the fixing number and metric dimension of the zero component graphs and determine vector spaces whose zero component graphs are Hamiltonian.


---

## Body

## 1. Introduction

A binary relation on a vector space, group, or ring can be studied with the help of considering the associating graph defined by this relation. Symplectic graphs, orthogonal graphs, subspace inclusion graphs, and nonzero component graphs are such examples which have been considered recently (see [1–4]).In this paper, we always assumen≥2, F is a field, F∗=F\0, and V is an n-dimensional vector space over F. Let A=ε1,…,εn be a basis of V. Then, any α∈V can be uniquely written as α=∑i=1nxiεi with xi∈F, and SAα (resp., ZAα) is the set of all basis vectors whose coefficients are nonzero (resp., zero) in the linear expression of α with respect to (i.e., with respect to) A, namely,(1)SAα=εi|ifxi≠0,resp.,ZAα=εi|ifxi=0.Clearly,SAα∪ZAα=A and SAα∩ZAα=∅.All graphs considered in this paper are undirected simple graphs (without loops and multiedges). The nonzero component graphΓcV of V, introduced by Das [1], is a graph with vertex set V∗=V\0, in which for distinct α,β∈V∗, there exists an edge joining α and β if and only if SAα∩SAβ≠∅. In [1], the author studied the diameter, dominating number, and dependent number of ΓcV. When the base field F is finite, Das [5] considered the clique number, edge connectivity, and chromatic number of ΓcV and showed that ΓcV is Hamiltonian, but not Eulerian. Murtaza et al. [6] considered two parameters, called the locating-dominating number and identifying number, of ΓcV. Also, the nonzero component union graph ΓuV of V has V∗ as its vertex set, but two vertices α,β∈V∗ are adjacent if and only ifSAα,SAβ=V, where S stands for the subspace of V generated by a subset S⊆V. In [7], Das studied some properties of ΓuV, such as the connectedness, dominating number as well as maximal cliques and showed that ΓuV is weakly perfect when the base field F is finite.It is well known that the automorphism group of a graph reflects the symmetry of the graph. Generally, it is an important but difficult work to describe the full automorphism group both in graph theory and in algebra. In [1], the author characterizes the automorphisms of ΓcV. For the automorphisms of symplectic graphs, orthogonal graphs, and subspace inclusion graphs, the reader is referred to [3, 4, 8].The fixing number and metric dimension of a graph (see Section2 for the definitions) are two parameters which “destroy” the automorphisms and symmetry. Moreover, the fixing number has been used to consider the problem of programming a robot to manipulate objects (see [9]), while the metric dimension has been applied to various areas, such as pharmaceutical chemistry, robot navigation, diverse as combinatorial optimization, and sonar (see [10]). Recently, several authors considered the fixing number and metric dimension of some associating graphs defined on a vector space. Fazil [11] computed the fixing number of ΓcV, and Benish [12] studied the relation between fixing number and another parameter, the fixed number, of ΓcV. Ali et al. [13] calculated the metric dimension of ΓcV. For a positive integer k<n, the Kneser graph Kn,k is a graph with all k-subsets of n=1,…,n as vertex set, in which two distinct k-subsets are connected by an edge if they are disjoint. Also, the vertex set of the Johnson graph Jn,k consists of all k-subsets of n, but two distinct k-subsets are adjacent if their intersection is a k−1-subset. In [14], Boutin obtained sharp bounds for the fixing number of Kneser graphs and determined all Kneser graphs whose fixing number is 2, 3, or 4. In [15], using various algebraic, combinatorial, and geometric approaches, Bailey et al. studied the constructions of resolving sets of Kneser and Johnson graphs and provided bounds on their metric dimension. For more works on the fixing number and metric dimension, the reader is referred to [9, 16–21] and the references therein.IfA is a basis of V, then it is clear that V∗ can be partitioned into n classes:(2)ZjA=α∈V|ZAα=j,0≤j≤n−1.On the zero component graphΓV,A of V with respect to A, we mean it is a graph defined as follows: ΓV,A has V∗A=V∗\Z0A as its vertex set, in which distinct α,β∈V∗A are adjacent if and only if ZAα∩ZAβ≠∅. Motivated by all the above, we intend to investigate the properties of ΓV,A.The rest of this paper is structured as follows: in Section2, we introduce some definitions and notation in graph theory. In Section 3, we show that the zero component graph does not depend on the choice of the bases and thus restate the definition of the zero component graph (see Definition 1). In Section 4, we prove that two finite-dimensional vector spaces are isomorphic if and only if their zero component graphs are isomorphic. The automorphisms of the zero component graph are determined in Section 5, and the fixing number and metric dimension are computed in Section 6. Finally, we consider other properties of the zero component graph, such as the girth, minimum independent dominating sets, maximum independent sets, planarity, and hamiltonicity in Section 7.


## 2. Notation and Preliminaries

LetG be a graph with a vertex set VG. Two vertices x,y∈VG are said to be adjacent and written as x∼y if there exists an edge joining x and y, otherwise, nonadjacent and u≁v. A graph is said to be complete if any pair of its vertices are adjacent; as usual, Kn stands for the complete graph of order n. Let Nx (resp., degx) be the neighbors (resp., degree) of x, that is, Nx=z∈VG|x∼z (resp., degx=Nx). If Nx=Ny or Nx∪x=Ny∪y; then, x and y are said to be twins. We use Twx to denote the twin set of x, which consists of all twins of x in G. In particular, a vertex x∈VG is called a singleton whenever Twx=x. Clearly, the relation “≈” is equivalent if it is defined as x≈y⇔x∈Twy; and then VG is a union of some disjoint twin sets of G. The number of twin sets of G is written as twG.ForS⊆VG, it is called a dominating set of G if any vertex in VG\S is adjacent to at least one vertex in S, and it is called an independent set of G if any pair vertices in S are nonadjacent in G. Also, a dominating set is called an independent dominating set if it is an independent set. The minimum dominating set (resp., maximum independent set, minimum independent dominating set) of G is a dominating set (resp., independent set, independent dominating set) with the minimum (resp., maximum, minimum) cardinality, and the cardinality of a minimum dominating set (resp., maximum independent set) is called the dominating number (resp., independent number) of G.A trail inG is an alternating sequence of vertices and edges, x0∼x1∼⋯∼xk for some positive integer k, where xi’s are not necessarily distinct; it is called a path if xi’s are distinct except for possibly the first and last vertices; and this path (resp., trail) is said to be joining x0 and xk. A graph is called connected if, for any pair of vertices, there exists a path joining them; it is called k-connected if each induced subgraph obtained by the graph from deleting k−1 vertices is connected. The connectivity of G is the maximum value of k for which G is k-connected. A cycle of length k is a path x0∼x1∼⋯∼xk with x0=xk; also, a cycle of length 3 is called a triangle. The girth of G is the minimum of the lengths of all cycles in G. Moreover, a graph is called Eulerian (resp., Hamiltonian) if there exists a trail (resp., cycle) which contains all edges (resp., all vertices) in it exactly once.For graphsG and H, they are called isomorphic if there exists an isomorphism ϕ from G to H, that is, ϕ:VG⟶VH is a bijection satisfying: x∼y in G if and only if ϕx∼ϕy in H. An automorphism of G is an isomorphism from G to itself. The set AutG of all automorphisms of G forms a group under the composition of the transformations. G is said to be vertex transitive if, for any x,y∈VG, there exists ϕ∈AutG such that ϕx=y. A subset W⊆VG is called a fixing set (or determining set) of G if the only automorphism of G that fixes every vertex in W is the identity, and the fixing number (or determining number) of G, denoted by fixG, is the smallest size of such a set. For x,y∈VG, the distance between them, written as dx,y, is the length of the shortest path joining them, and the diameter of G is the largest distance between pairs of vertices of G. If W=w1,w2,…,wk is an ordered subset of VG, then the k-dimensional vector dx,w1,…,dx,wk is called the representation of x with respect to W, and x is said to be resolved by W if dx,w1,…,dx,wk≠dy,w1,…,dy,wk for any other vertex y∈VG. Moreover, W is called a resolving set (or locating set) of G if distinct vertices of G have distinct representations with respect to W, and the metric dimension (or locating number) of G, denoted by dimG, is the minimum cardinality of such a set. A graph G is called an FED-graph if fixG=dimG. All other unexplained notations and definitions on graph theory are standard (see [22] or [23] for details).Here, we list some results on graphs, which will be used in this paper.Proposition 1 (Handshaking lemma, [22], Theorem 1.1).
The number of edges in a graphG is 1/2∑x∈VGdegx.Proposition 2 (see [22], p. 18).
A graph as well as its complement has the same automorphisms.Proposition 3 (see [11], Theorem 1).
A finite graph and its complement are of the same fixing number.Proposition 4 (see [24], Lemma 2.8).
LetG be a connected graph. If G has no singleton, then it is an FED-graph, and fixG=dimG=VG−twG.Proposition 5 (see [22], Theorem 3.5).
A connected graph is Eulerian if and only if each vertex is of even degree.Proposition 6 (Kuratowski’s theorem, [22], Theorem 10.30).
A graph is planar if and only if it contains no subdivisions ofK5 or K3,3, where Kn,n stands for the balanced complete bipartite graph of order 2n.Proposition 7 (see [22], Corollary 18.12).
IfG is a connected graph in which all vertices are of odd degree, then it is Hamiltonian.Proposition 8 (Chvátal–Erdős theorem, [22], Theorem 18.10).
LetG be a connected graph on at least 3 vertices with independent number ι and connectivity κ. If ι≤κ, then G is Hamiltonian.Proposition 9 (see [25]).
LetG be a 2-connected graph with minimum degree δ and independent number ι. If δ≥max|VG|+2/3,ι, then G is Hamiltonian.


## 3. Zero Component Graph of a Vector Space

We first show that the zero component graph ofV does not depend on the choice of the bases.Theorem 1.
LetA=ε1,…,εn and B=η1,…,ηn be bases of V, then ΓV,A and ΓV,B are isomorphic.Proof.
Clearly, there exists an invertible linear transformationf on V such that fεi=ηi for any 1≤i≤n. Considering the restriction of f on V∗A, we see that f is also a bijection from V∗A to V∗B. For any α, α′∈V∗A, we obtain that α∼α′ in ΓV,A if and only if there exists some 1≤j≤n such that εj∈ZAα∩ZAα′, if and only if ηj∈ZBfα∩ZBfα′, or equivalently fα∼fα′ in ΓV,B. Therefore, f is an isomorphism from ΓV,A to ΓV,B.Remark 1.
In case the zero component graph ofV does not depend on the choice of the bases, two vectors may be adjacent with respect to one basis but not adjacent with respect to another basis. For example, suppose that V is a 3-dimensional vector space over F, and A=ε1,ε2,ε3 is a basis of V. Then, B=ε1,ε1+ε2,ε2+ε3 is also a basis of V. It is easily seen that ε1+ε2≁ε2+ε3 in ΓV,A, but ε1+ε2∼ε2+ε3 in ΓV,B.
As usual, denote byei∈V, 1≤i≤n, the vector with the i-th component 1 and the others 0. It is well known that E=e1,…,en constructs a basis of V. Theorem 1 shows that we need only to consider the zero component graph ΓV,E of V. For the convenience of writing, we set e=∑i=1nei and use ΓV, V∗, Sα, Zα for α∈V, as well as Zj for 0≤j≤n−1, instead of ΓV,E, V∗E, SEα, ZEα, as well as ZjE, respectively. Then, by Theorem 1, we can restate the definition of the zero component graph as follows.Definition 1.
The zero component graphΓV of V is a graph defined as follows: ΓV has V∗=V∗\Z0 as its vertex set, and for distinct α,β∈V∗, α∼β if and only if Zα∩Zβ≠∅.
Next, we describe the connectedness and diameter ofΓV.Lemma 1.
(i)
Ifn=2, then ΓV is a union of two complete graphs(ii)
Ifn≥3, then ΓV is a connected graph with diameter 2Proof.
The result is clear forn=2. Let n≥3. Then, by e−e1≁e−e2, we see that ΓV is not complete. On the other hand, for any distinct α,β∈V∗, if α≁β, then there exist 1≤k,l≤n such that ek∈Zα\Zβ and el∈Zβ\Zα, and further α∼e−ek−el∼β. Consequently, ΓV is a connected graph with diameter 2.


## 4. Zero Component Graph and Graph Isomorphism Problem

In this section, we investigate the interrelationship between the isomorphism of two vector spaces and that of their zero component graphs. Before that, we study the twins and the number of twin sets of the zero component graph.Lemma 2.
Two vectorsα,β∈V∗ are twins in ΓV if and only if Zα=Zβ (or equivalently Sα=Sβ).Proof.
The sufficiency is clear; thus, we need only to prove the necessity. Letα,β∈V∗ be twins in ΓV. If Zα≠Zβ, then Zα⊈Zβ or Zα⊉Zβ. Without loss of the generalization, assume Zα⊈Zβ; say ej∈Zα\Zβ for some 1≤j≤n. It follows α∼e−ej and β≁e−ej, a contradiction. Thus, Zα⊆Zβ. Similarly, Zα⊇Zβ. Therefore, Zα=Zβ.Lemma 3.
Letn≥3. Then,(i)
The number of twin sets ofΓV is twΓV=2n−2(ii)
Any vertex inΓV is a singleton when F=2, but not a singleton when F≠2Proof.
(i) follows fromV∗=∪1≤i≤n−1Zi and the fact that Zi is a union of ni twin sets in ΓV (see Lemma 2), where ni=n!/i!n−i!.
For (ii), we see that the case ofF=2 is clear according to Lemma 2. Assume F≠2. For any α∈V∗ and any x∈F\0,1, it is obvious that α and xα are twins. This shows that α is not a singleton in ΓV, which confirms (ii).
The following result is a direct consequence of Lemma1 (i).Theorem 2.
Letn,m≥3; letV and W be, respectively, an n-dimensional vector space and an m-dimensional vector space over F. Then, V is isomorphic to W as vector spaces if and only if ΓV is isomorphic to ΓW.In the following, we will prove that two vector spaces over distinct finite fields are isomorphic if and only if their zero component graphs are isomorphic. To this end, we give the vertex degree ofΓV.Lemma 4.
Letn≥3, q=F, and α∈Zj1≤j≤n−1. Then, the degree of α in ΓV is degα=qn−qn−jq−1j−2.Proof.
Assumeβ=∑i=1n−jxiei∈Zj with xi∈F∗ and denote(3)Niβ=γ∈V|Zγ∩Zβ=i,1≤i≤j.
Clearly, any pair ofN1β,…,Njβ do not intersect with each other, and Niβ=jiqn−jq−1j−i. Then, by Nβ=∪i=1jNiβ\0,β, we get(4)degβ=∑i=1jNiβ−2=∑i=1jjiqn−jq−1j−i−2=qn−qn−jq−1j−2.
For anyα∈Zj, we write α=∑i=1n−jaieki with ai∈F∗ and 1≤k1<⋯<kn−j≤n. Take a permutation σ on n such that σi=ki for 1≤i≤j, and define the map ϕσ:V⟶V by ϕσ∑i=1nyiei=∑i=1nyieσi for any yi∈F. Then, the restriction of ϕσ on V∗ is an automorphism of ΓV, and ϕσ−1α=∑i=1n−jaiei∈Twβ. Therefore, degα=degϕσ−1α=degβ=qn−qn−jq−1j−2.
By Lemma4, we get the following results immediately.Corollary 1.
Letn≥3, and q=F. Then, the order and size m of ΓV are qn−q−1n−1 and qn−1qn−2−q−1nq+1n−3/2, respectively.Proof.
It is easily seen that the order ofΓV is V∗=V−Z0−1=qn−q−1n−1. For the size of ΓV, by Handshaking lemma (see Proposition 1), Lemma 4, and Zj=njq−1n−j for 1≤j≤n−1, we have(5)2m=∑j=1n−1Zjqn−qn−jq−1j−2,=∑j=1n−1njq−1n−jqn−qn−jq−1j−2,=qn−1qn−2−q−1nq+1n−3,from which it follows the result.Corollary 2.
Letn≥3, and q=F. Then, the maximum and minimum degree of ΓV are qn−qq−1n−1−2 and qn−1−2, respectively.Corollary 3.
Letn≥3, and let F be a finite field. Then, ΓV is Eulerian if and only if F is even.Proof.
WhenF is even (resp., odd), by Lemma 4, we obtain that each vertex in ΓV is of even degree (resp., odd degree), which shows ΓV is (resp., not) Eulerian.
Finally, we show that two vector spaces over distinct finite fields are isomorphic if and only if their zero component graphs are isomorphic.Theorem 3.
Letn,m≥2; V an n-dimensional vector space over a field with q1 elements; and W an m-dimensional vector space over a field with q2 elements. Then, V is isomorphic to W as vector spaces if and only if ΓV is isomorphic to ΓW.Proof.
The necessity is obvious; thus, it suffices to prove the sufficiency. Assume thatΓV is isomorphic to ΓW. If n=2, then by Lemma 1 (i), we know that ΓV is a union of two complete graphs each of which is of order q1−1, and so is ΓW. Again, by Lemma 1 (i), we have m=2 and q1=q2. Similarly, one may get n=2 and q1=q2 when m=2. Hence, V and W are isomorphic as vector spaces when n=2 or m=2. Now, let n,m≥3. Lemma 3 (i) shows that the numbers of twin sets of ΓV and ΓW are 2n−2 and 2m−2, respectively, which follows n=m. On the other hand, the minimum degrees of ΓV and ΓW are, respectively, q1n−1−2 and q2m−1−2 according to Corollary 2. Then, by n=m, we obtain q1=q2. Thus, V and W are isomorphic as vector spaces.


## 5. Automorphism ofΓV

We first construct two types of standard automorphisms ofΓV as follows.Definition 2.
LetG be a graph and ρ a bijection on VG. If ρ permutates the twins in G, then it is called a regular automorphism of G.Definition 3.
Denote bySymn the symmetric group consisting of all permutations on n. If σ∈Symn, then the map ϕσ:V⟶V,∑i=1naiei↦∑i=1naieσi is an invertible linear transformation on V. By the proof of Theorem 1, we know that the restriction of ϕσ on V∗ is an automorphism of ΓV, called a permutation automorphism of ΓV.Lemma 5.
(i)
Letρ and ϕσ be defined as above. Then, ϕσ−1⋅ρ⋅ϕσ is a regular automorphism of ΓV.(ii)
If an automorphismϕ of ΓV is a regular automorphism but also a permutation automorphism, then ϕ is the identity.Proof.
For anyα=∑i=1naiei∈V∗ with ai∈F, it is clear that ρϕσα=ρ∑i=1naieσi and ∑i=1naieσi are twins. By Lemma 2, we assume ρ∑i=1naieσi=∑i=1naibieσi with bi∈F∗. Then,(6)ϕσ−1ρϕσα=ϕσ−1∑i=1naibieσi=∑i=1naibiei.
Again, by Lemma2, we know that ϕσ−1ρϕσα and α are twins. By the arbitrariness of α, we prove (i).
Assumeϕ=ρ=ϕσ with σ∈Symn. For 1≤i≤n, by applying ϕ on ei, we have ρei=eσi, which shows that eσi and ei are twins. It follows σi=i for any 1≤i≤n. Hence, σ=1, and further ϕσ=1 or ϕ=1. This confirms (ii).
Next, we need to present a result on the zero-divisor graph. LetR be a commutative ring, then the zero-divisor graph ΓzR of R is a graph defined as follows: ΓzR has vertex set consisting of all nonzero zero-divisors of R, and two nonzero zero-divisors are adjacent in ΓzR if and only if their product in R is 0. If F=2, we denote by ℤ2n the ring which has V as an additive group and the multiplication of two elements α=∑i=1naiei,β=∑i=1nbiei∈V with ai,bi∈F are defined naturally:(7)α⋅β=∑i=1naibiei.
It is clear thatV∗ is also the vertex set of Γzℤ2n. In [24], the automorphisms of Γzℤ2n were described as follows.Proposition 10 (see [24], Theorem 1).
Any automorphism ofΓzℤ2n is a permutation automorphism, and AutΓzℤ2n≅Symn.The following result shows that the relation betweenΓV, for F=2, and Γzℤ2n.Lemma 6.
IfF=2, then the complement graph ΓV¯ of ΓV is isomorphic to Γzℤ2n.Proof.
Defineg:V∗⟶V∗ by gα=e−α,∀α∈V∗. It is clear that g is a bijection on V∗. Moreover, for any α,β∈V∗, we see that α≁β in ΓV (or equivalently Zα∩Zβ=∅) if and only if Sgα∩Sgβ=∅, if and only if gαgβ=0. Thus, α∼β in ΓV¯ if and only if gα∼gβ in Γzℤ2n, and therefore, g is an isomorphism from ΓV¯ to Γzℤ2n
By Proposition2, Proposition 10, and Lemma 6, we can immediately determine the automorphisms of ΓV for F=2.Lemma 7.
IfF=2, then any automorphism of ΓV is a permutation automorphism, and AutΓV≅Symn.In the following, we consider the case for an arbitrary finite-dimensional vector space. Before that, we introduce the quotient graphΓV˜ of ΓV, which is defined as follows: ΓV˜ has all twin sets of ΓV as its vertex set, and for any α,β∈V∗, Twα∼Twβ in ΓV˜ if and only if Twα≠Twβ as well as Zα∩Zβ≠∅. It is easily seen that the definition is well defined since Zα∩Zβ≠∅⇔Zα′∩Zβ′≠∅ for any α′∈Twα and β′∈Twβ (see Lemma 2), and ΓV˜ is isomorphic to ΓV2, where V2 is the vector space over the field ℤ2. Let ϕ be an automorphism of ΓV. We define ϕ˜ on ΓV˜ by(8)ϕ˜Twα=Twϕα,∀α∈V∗.Lemma 8.
Letϕ be an automorphism of ΓV; then, ϕ˜ defined as in (8) is an automorphism of ΓV˜.Proof.
IfTwα=Twβ for α,β∈V∗, then α,β∈V∗ are twins in ΓV. Furthermore, ϕα and ϕβ are also twins in ΓV, following Twϕα=Twϕβ. Hence, ϕ˜ is well defined. It is clear that ϕ˜ is a bijection. Moreover, from the fact that ϕα∼ϕβ in ΓV if and only if α∼β in ΓV, it follows that Twϕα∼Twϕβ in ΓV˜ if and only if Twα∼Twβ in ΓV˜. Thus, ϕ˜ is an automorphism of ΓV˜.
Now, we can consider the case for an arbitrary finite-dimensional vector space.Theorem 4.
Letn≥2. Then, a bijection on V∗ is an automorphism of ΓV if and only if it can be uniquely decomposed into the product of a permutation automorphism and a regular automorphism of ΓV.Proof.
The uniqueness of decomposition is clear according to Lemma5 (ii); thus, it suffices to prove the existence. When F=2, we get the result by Lemma 7. Now, assume F≠2.
For any automorphismϕ of ΓV, define ϕ˜ as in (8). Then, by Lemma 8, we know that ϕ˜ is an automorphism of ΓV˜, which is isomorphic to ΓV2 (where V2 is the vector space over the field ℤ2). Applying Lemma 7, we see that there exists a permutation σ∈Symn such that(9)ϕ˜Twα=Twϕσα,∀α∈V∗.
By the definition ofϕ˜, we have Twϕα=Twϕσα, or, equivalently, ϕα and ϕσα are twins. Consequently, there exists a regular automorphism ρ of ΓV such that ϕα=ρϕσα for any α∈V∗, and therefore ϕ=ρ⋅ϕσ.
The following is a direct consequence of Lemma1 (i) and Theorem 4.Corollary 4.
ΓV is vertex transitive if and only if n=2.Denote byRegΓV and PerΓV the sets consisting of all regular automorphisms and all permutation automorphisms of ΓV, respectively. Then, RegΓV and PerΓV are subgroups of the automorphism group AutΓV of ΓV. Finally, by Theorem 4, we can describe AutΓV and its order as follows.Corollary 5.
(i)
AutΓV=PerΓV⋉RegΓV. In particular, AutΓV=PerΓV when F=2.(ii)
Ifq=F, then AutΓV=n!∏i=1n−1q−1i!k with k=ni.Proof.
Theorem4 shows AutΓV=PerΓV⋅RegΓV. Then, by PerΓV∩RegΓV=1 (see Lemma 5 (ii)) and the fact that RegΓV is a normal subgroup of AutΓV (see Lemma 5 (i)), we obtain the result of (i).
(ii) follows from (i),PerΓV≅Symn, and RegΓV≅∏i=1n−1∏j=1kSymq−1i.


## 6. Fixing Number and Metric Dimension ofΓV

In this section, we always assumeF is a finite field with q≥2 elements. If n=2, nothing needs to do for the metric dimension of ΓV according to Lemma 2; the fixing number ΓV is 1 when q=2, and 2q−2 otherwise. In the following, we consider the case for n≥3.Firstly, by Proposition4, Lemma 3, and Corollary 1, we have the following result immediately.Lemma 9.
Letn≥3 and q≥3. Then, ΓV is an FED-graph, and fixΓV=dimΓV=qn−q−1n−2n+1.Next, we give the value of the fixing number ofΓV for n≥3 and q=2.Lemma 10.
Letn≥3 and q=2. Then, fixΓV=⌈log2n⌉.Proof.
By Proposition3 and Lemma 6, we have fixΓV=fixΓzℤ2n. Furthermore, from fixΓzℤ2n=⌈log2n⌉ (see [24], Theorem 3.5), it follows that fixΓV=⌈log2n⌉.
The vectorα=∑i=1naiei∈V with ai∈F is said to be δ1α,δ2α,…,δnα-type, where(10)δjα=1,ifaj≠0,0,ifaj=0,for 1≤j≤n. The following result is trivial.Lemma 11.
Ifq=2, then all vectors in V∗ are of different types.Now, we can calculate the metric dimension ofΓV for n≥3 and q=2.Lemma 12.
Letn≥3 and q=2. Then, dimΓV=n when n≥4, and dimΓV=2 when n=3.Proof.
Whenn=3, it is clear that dimΓV≠1 as shown in Figure 1.
Moreover,W1=e1+e3,e2+e3 is a resolving set of ΓV. So, dimΓV=2. Now, let n≥4. We first assert that W2=e−ej|1≤j≤n⊆V∗ is a resolving set of ΓV. For any α∈V∗, it is of δ1α,…,δnα-type, and its presentation with respect to W2 is δ1α+1,…,δnα+1, where δjα is defined as in (10). Since the types of all vectors in V∗ are different (see Lemma 11), the same is for their representation with respect to W2. Hence, W2 is a resolving set of ΓV, and therefore dimΓV≤n. Next, we need to show dimΓV≥n. Suppose dimΓV=k and that U=α1,α2,…,αk⊆V∗ is a resolving set of ΓV. Define the map h:V∗\U⟶ℤ2k as(11)hβ=dβ,α1−1,dβ,α2−1,…,dβ,αk−1,∀β∈V∗\U.
Lemma1 (ii) shows that h is well defined. Moreover, for any β≠γ∈V∗\U, since their representation with respect to U is different, we see that hβ≠hγ. Consequently, h is injective, and further 2n−2−k=V∗\U≤ℤ2k=2k. It follows that k≥n. Thus, dimΓV=n.
Finally, combining Lemmas9, 10, and 12, we get the following theorem.Figure 1
ΓV for n=3 and q=2.Theorem 5.
Letn≥3 and q=F. Then, ΓV is an FED-graph if and only if q≥3, or n=3 as well as q=2. Moreover, fixΓV=dimΓV=qn−q−1n−2n+1 when q≥3; fixΓV=dimΓV=2 when n=3, q=2; and fixΓV=⌈log2n⌉ as well as dimΓV=n when n≥4, q=2.


## 7. Other Properties ofΓV

We first consider the girth, minimum independent dominating sets, maximum independent sets, and planarity ofΓV when F is an arbitrary field.Theorem 6.
Each vertex inΓV belongs to some triangle in ΓV. Furthermore, the girth of ΓV is 3.Proof.
The case forn=2 is clear according to Lemma 1 (i). Now, let n≥3. For any α∈V∗, if Zα=n−1, assume ek∉Zα for some 1≤k≤n. Choose distinct i,j∈n\k; then α∼ei∼ej∼α; if Zα≤n−2, say es,et∉Zα for some 1≤s,t≤n, then α∼es∼et∼α. Therefore, in any case, α belongs to a triangle in ΓV.Lemma 13.
Letn≥3. Then, the dominating number of ΓV is 2.Proof.
This is a direct consequence of the fact that any vertex is adjacent to at least one ofe1,e2.Theorem 7.
Letn≥3. Then, I=α,β⊆V∗ is a minimum independent dominating set of ΓV if and only if Zα∩Zβ=∅ as well as Zα∪Zβ=e1,…,en.Proof.
LetI=α,β⊆V∗ be an independent dominating set of ΓV. It is clear that Zα∩Zβ=∅. If Zα∪Zβ≠e1,…,en, say ej∉Zα∪Zβ for some 1≤j≤n, then α≁e−ej and β≁e−ej. This implies that I is not a dominating set of ΓV, a contradiction. Hence, Zα∪Zβ=e1,…,en.
Conversely, assumeZα∩Zβ=∅ and Zα∪Zβ=e1,…,en for α,β∈V∗. By Zα∩Zβ=∅, we see that I=α,β is an independent set of ΓV. On the other hand, for any γ∈V∗, since Zα∩Zγ=∅ implies Zβ∩Zγ≠∅, we obtain that α≁γ leads to β∼γ, which shows that I is a dominating set. Therefore, I is an independent dominating set, and further a minimum independent dominating set of ΓV.Lemma 14.
The independence number ofΓV is n (i.e., the dimension of V).Proof.
Letι be the independence number of ΓV. Clearly, e−ei|1≤i≤n⊆V∗ is an independent set of ΓV. This implies ι≥n. Now, it suffices to show ι≤n. Suppose to the contrary, ι≥n+1, and assume that αj|1≤j≤n+1 is an independent set of ΓV. Then, Zα1,…,Zαn+1 are disjoint nonempty sets. From ∪j=1n+1Zαj⊆ei|1≤i≤n, it follows that n+1≤∑j=1n+1Zαj≤∪j=1n+1Zαj≤n, a contradiction.Theorem 8.
The setI=αj|1≤j≤n⊆V∗ is a maximum independent set of ΓV if and only if I⊆Z1, and Zα1,…,Zαn are disjoint.Proof.
The sufficiency is obvious; thus, we need only to prove the necessity. LetI=αj|1≤j≤n⊆V∗ be an independent set of ΓV. Clearly, Zα1,…,Zαn are disjoint. It suffices to show αj∈Z1; that is, αj has exactly one zero component, 1≤j≤n. The case for n=2 is clear. Let n≥3, and suppose, to the contrary, there exists some 1≤k≤n such that αk∉Z1. Without loss of the generalization, assume en−1,en∈Zαk. For any j≠k, by αj≁αk, we get en−1,en∉Zαj, and consequently ∪j≠kZαj⊆ei|1≤i≤n−2. Hence, n−1≤∑j≠kZαj≤∪j≠kZαj≤n−2, a contradiction.Theorem 9.
ΓV is planar if and only if n=2 and F≤5, or n=3 and F=2.Proof.
Whenn=2 (by Lemma 1 (i)), we know that ΓV is a union of two complete graphs each of which is of order F−1. This follows that ΓV is planar if and only if F≤5 (see Proposition 6). When n=3 and F=2, we obtain that ΓV is planar as shown in Figure 1. When n≥4 (resp., n=3 and F≥3), the subgraph of ΓV induced by e1,e2,e3,e1+e2,e1+e3,e2+e3 (resp., aei|a=1,2and1≤i≤3) is K6 and further nonplanar.
Next, we provide a lower bound for the connectivity ofΓV when F is a finite field.Lemma 15.
Letn≥3 and q=F. Then, the connectivity of ΓV is greater than or equal to qn−2−1.Proof.
Letα and β be two nonadjacent vertices in ΓV and suppose that X⊆V∗ such that α and β are in different components of ΓV∗\X, the subgraph of ΓV induced by V∗\X. It is easily seen that X⊇Nα∩Nβ; indeed, if X⊉Nα∩Nβ, then α∼γ∼β in ΓV∗\X for any γ∈Nα∩Nβ\X, a contradiction. Assume ek∈Zα, el∈Zβ and set(12)Y=γ∈V∗|ek,el∈Zγ.
Fromα≁β, it follows that el∉Zα and ek∉Zβ, which implies α,β∉Y. Furthermore, Y⊆Nα∩Nβ⊆X, and thus X≥Y=qn−2−1, from which we obtain the result.
Finally, we can characterize the hamiltonicity ofΓV when F is a finite field.Theorem 10.
Letn≥3 and let F be a finite field. Then, ΓV is Hamiltonian.Proof.
IfF is odd, then each vertex in ΓV is of odd degree (see Lemma 4). By Proposition 7, we know that ΓV is Hamiltonian. Now, let F be even. If n≥5 or F≥4, we have Fn−2−1≥n; that is, the connectivity of ΓV is greater than or equal to the independent number (see Lemma 14 and Lemma 15); then, by Chvátal–Erdős theorem (see Proposition 8), we obtain that ΓV is Hamiltonian. The case for n=3 and F=2 is clear according to Figure 1. If n=4 and F=2, then ΓV is 2-connected with minimum degree δ=2n−1−2 (see Corollary 2) and independent number n, which follows δ≥maxV∗+2/3,n. Applying a theorem of Nash-Williams (see Proposition 9), we see that ΓV is Hamiltonian.


## 8. Conclusion

In this paper, we present an undirected simple graph, called the zero component graphΓV, over a finite-dimensional vector space V, and investigate various interrelationships among ΓV and V. The aim of this paper is to determine the automorphisms, compute the fixing number as well as metric dimension, and study other properties such as girth, minimum independent dominating sets, maximum independent sets, planarity, and hamiltonicity of ΓV. In addition, a lower bound for the connectivity is given. As a topic of further research, one can give the exact value of the connectivity and clique number of ΓV.



---

*Source: 5595620-2021-04-10.xml*