Subspace Sum Graph of a Vector Space
Angsuman Das

































angsumandas@sxccal.edu



Department of Mathematics,
 St. Xavier's College, Kolkata, India.
angsumandas@sxccal.edu
[cor1]Corresponding author






In this paper we introduce a graph structure, called subspace sum graph 𝒢(𝕍) on a finite dimensional vector space 𝕍 where the vertex set is the collection of non-trivial proper subspaces of a vector space and two vertices W_1,W_2 are adjacent if W_1 + W_2=𝕍. The diameter, girth, connectivity, maximal independent sets, different variants of domination number, clique number and chromatic number of 𝒢(𝕍) are studied. It is shown that two subspace sum graphs are isomorphic if and only if the base vector spaces are isomorphic. Finally some properties of subspace sum graph are studied when the base field is finite.




subspace Galois numbers q-binomial coefficient
[2008] 05C25 05C69














§ INTRODUCTION

Apart from its combinatorial motivation, graph theory also helps to characterize various algebraic structures by means of studying certain graphs associated to them. Till date, a lot of research, e.g., <cit.> has been done in connecting graph structures to various algebraic objects. Recently, some works associating graphs with subspaces of vector spaces can be found in <cit.>. 

In this paper we define a graph structure on a finite dimensional vector space 𝕍 over a field 𝔽, called Subspace Sum Graph of 𝕍 and derive some properties of the graph using the algebraic properties of vector subspaces.



§ DEFINITIONS AND PRELIMINARIES

In this section, for convenience of the reader and also for later use, we recall some definitions, notations and results concerning elementary graph theory. For undefined terms and concepts the reader is referred to <cit.>.

By a graph G=(V,E), we mean a non-empty set V and a symmetric binary relation (possibly empty) E on V. The set V is called the set of vertices and E is called the set of edges of G. Two element u and v in V are said to be adjacent if (u,v) ∈ E. H=(W,F) is called a subgraph of G if H itself is a graph and ϕ≠ W ⊆ V and F ⊆ E. If V is finite, the graph G is said to be finite, otherwise it is infinite. Two graphs G=(V,E) and G'=(V',E') are said to be isomorphic if there exists a bijection ϕ: V → V' such that (u,v) ∈ E  (ϕ(u),ϕ(v)) ∈ E'. A path of length k in a graph is an alternating sequence of vertices and edges, v_0,e_0,v_1,e_1,v_2,…, v_k-1,e_k-1,v_k, where v_i's are distinct (except possibly the first and last vertices) and e_i is the edge joining v_i and v_i+1. We call this a path joining v_0 and v_k. A cycle is a path with v_0=v_k. A graph is said to be Eulerian if it contains a cycle containing all the edges in G exactly once. A cycle of length 3 is called a triangle. A graph is connected if for any pair of vertices u,v ∈ V, there exists a path joining u and v. A graph is said to be triangulated if for any vertex u in V, there exist v,w in V, such that (u,v,w) is a triangle. The distance between two vertices u,v ∈ V,  d(u,v) is defined as the length of the shortest path joining u and v, if it exists. Otherwise, d(u,v) is defined as ∞. The diameter of a graph is defined as diam(G)=max_u,v ∈ V  d(u,v), the largest distance between pairs of vertices of the graph, if it exists. Otherwise, diam(G) is defined as ∞. The girth of a graph is the length of its shortest cycle, if it exists. Otherwise, it is defined as ∞. If all the vertices of G are pairwise adjacent, then G is said to be complete. A complete subgraph of a graph G is called a clique. A maximal clique is a clique which is maximal with respect to inclusion. The clique number of G, written as ω(G), is the maximum size of a clique in G. A subset I of V is said to be independent if any two vertices in that subset are pairwise non-adjacent. A maximal independent set is an independent set which is maximal with respect to inclusion. The chromatic number of G, denoted as χ(G), is the minimum number of colours needed to label the vertices so that the adjacent vertices receive different colours. It is known that for any graph G, χ(G)≥ω(G).  A graph G is said to be weakly perfect if χ(G)= ω(G). A graph G is said to be perfect if χ(H)= ω(H), for all induced subgraph H of G.  A subset D of V is said to be dominating set if any vector in V ∖ D is adjacent to at least one vertex in D. A subset D of V is said to be total dominating set if any vector in V is adjacent to at least one vertex in D. A dominating set D  of G is said to be a connected dominating set of G if the subgraph generated by D, ⟨ D ⟩ is connected. A dominating set D  of G is said to be a dominating clique of G if the subgraph generated by D, ⟨ D ⟩ is complete. The dominating number γ(G), the total dominating number γ_t(G), the connected dominating number γ_c(G) and the clique domination number are the minimum size of a dominating set, a total dominating set, a connected dominating set and a dominating clique in G respectively. 




§ SUBSPACE SUM GRAPH OF A VECTOR SPACE

Let 𝕍 be a finite dimensional vector space over a field 𝔽 of dimension greater than 1 and θ denote the null vector. We define a graph 𝒢(𝕍)=(V,E) as follows: V= the collection of non-trivial proper subspaces of 𝕍 and for W_1,W_2 ∈ V, W_1 ∼ W_2 or (W_1,W_2) ∈ E if W_1 + W_2=𝕍. Since, dim(𝕍)>1, V ≠∅.


 Consider a 3 dimensional vector space 𝕍 over ℤ_2 with a basis {α_1,α_2,α_3}. The following are the possible non-trivial proper subspaces of 𝕍: W_1=⟨α_1 ⟩,W_2=⟨α_2 ⟩, W_3=⟨α_3 ⟩,W_4=⟨α_1 +α_2 ⟩,W_5=⟨α_2+α_3 ⟩,W_6=⟨α_1+α_3 ⟩,W_7=⟨α_1+α_2+α_3 ⟩,W_8=⟨α_1,α_2 ⟩,W_9=⟨α_1,α_3 ⟩,W_10=⟨α_2,α_3 ⟩,W_11=⟨α_1,α_2+α_3 ⟩,W_12=⟨α_2, α_1+α_3 ⟩,W_13=⟨α_3,α_1+α_2 ⟩,W_14=⟨α_1+α_2,α_2+α_3 ⟩. Then the graph 𝒢(𝕍) is given in Figure <ref>. For discussion on chromatic number and clique number of this graph, see Remark <ref> of Section <ref>. 



Throughout this paper, even if it is not mentioned explicitly, the underlying field is 𝔽 and 𝕍 is finite dimensional. Now we study some basic properties like completeness, connectedness, diameter and girth of 𝒢(𝕍).

 𝒢(𝕍) is complete if and only if dim(𝕍)=2.

If dim(𝕍)=2, then the vertices of 𝒢(𝕍) are the one dimensional subspaces of 𝕍. Now, the sum of two distinct one dimensional subspaces in a two dimensional vector space is two dimensional and hence equal to 𝕍 and hence 𝒢(𝕍) is complete. Conversely, if 𝒢(𝕍) is complete and dim(𝕍)≥ 2, then there exists two distinct one dimensional subspaces of 𝕍 whose sum is not 𝕍. This contradicts the completeness of 𝒢(𝕍) and hence dim(𝕍)=2. 

 If dim(𝕍)≥ 3, then 𝒢(𝕍) is connected and  diam(𝒢(𝕍))= 2.

Let W_1, W_2 be two distinct non-trivial proper subspaces of 𝕍. If W_1 + W_2 = 𝕍, then d(W_1, W_2)=1 and we are done. However, as dim(𝕍)≥ 3, by Theorem <ref>, there exists W_1, W_2 which are not adjacent in 𝒢(𝕍). If W_1 ≁W_2, then W_1 + W_2 ⊂𝕍. Two cases may arise.

 Case 1: W_1 ∩ W_2 ≠{θ}. Then there exists a non-trivial proper subspace W_3 such that (W_1 ∩ W_2)+W_3=𝕍. Since, W_1 ∩ W_2 ⊂ W_1,W_2, therefore W_1 + W_3=𝕍 and W_2+ W_3 = 𝕍. Thus, we have W_1 ∼ W_3 ∼ W_2 and hence d(W_1,W_2)=2.

Case 2: W_1 ∩ W_2 = {θ}. Let dim(W_1)=k_1; dim(W_2)=k_2 with k_1 ≤ k_2. Moreover, let W_1=⟨α_1,α_2,…,α_k_1⟩; W_2=⟨β_1,β_2,…,β_k_2⟩. Since W_1 ∩ W_2 = {θ}, therefore {α_1,α_2,…,α_k_1,β_1,β_2,…,β_k_2} is linearly independent. Also, as W_1 + W_2 ⊂𝕍, {α_1,α_2,…,α_k_1,β_1,β_2,…,β_k_2} can be extended to a basis 
    {α_1,α_2,…,α_k_1,β_1,β_2,…,β_k_2,γ_1,γ_2,…,γ_k_3}𝕍, dim(𝕍)=n=k_1 + k_2 + k_3.
 Set W_3=⟨α_1 + β_1, α_2 + β_2,…, α_k_1+β_k_1,β_k_1 + 1,β_k_1 + 2,…,β_k_2,γ_1,γ_2,…,γ_k_3⟩. Clearly, dim(W_3)=k_2+k_3<n. We claim that W_1+W_3=𝕍 and W_2+W_3=𝕍.

Proof of Claim: β_1=(α_1+β_1)-α_1 ∈ W_1+W_3. Similarly, β_2,β_3,…,β_k_1∈ W_1+W_3. Also, β_k_1 +1,…, β_k_2,γ_1,γ_2,…,γ_k_3∈ W_3 and α_1,α_2,…,α_k_1∈ W_1. Thus,
 
⟨α_1,α_2,…,α_k_1,β_1,β_2,…,β_k_2,γ_1,γ_2,…,γ_k_3⟩⊂ W_1+W_3 and hence W_1+W_3=𝕍. Similarly W_2+W_3=𝕍.

Thus we have W_1 ∼ W_3 ∼ W_2, and combining both the cases, we get  diam(𝒢(𝕍))= 2.




𝒢(𝕍) is triangulated and hence girth(𝒢(𝕍))=3.

Let W_1=⟨α_1,α_2,…,α_k ⟩ be a k-dimensional subspace of 𝕍 and {α_1,α_2,…,α_k} be extended to a basis of 𝕍 as {α_1,α_2,…,α_k,β_1,β_2,…,β_l }  where n=k+l. Without loss of generality, we take k ≤ l and set W_2=⟨β_1, β_2, …, β_l ⟩ and W_3= ⟨α_1 + β_1, α_2+ β_2, …, α_k + β_k, β_k+1,…, β_l ⟩. By similar arguments to that of the proof of claim in Theorem <ref>, it is clear that W_1+W_3=W_2+W_3=W_1+W_2=𝕍 and hence W_1,W_2,W_3 forms a triangle in 𝒢(𝕍). 



§ MAXIMAL CLIQUES AND MAXIMAL INDEPENDENT SETS IN 𝒢(𝕍)

In this section, we study the structure of maximal cliques and maximal independent sets in 𝒢(𝕍).

 The collection 𝒲_n-1 of all (n-1) dimensional subspaces of 𝕍 is a maximal clique in 𝒢(𝕍).

As any two distinct n-1 dimensional subspaces are adjacent in 𝒢(𝕍), the collection 𝒲_n-1 of all (n-1) dimensional subspaces of 𝕍 is a clique in 𝒢(𝕍). For maximality, let if possible, 𝒲_n-1∪{W} be a clique where W is non-trivial proper subspace of 𝕍 with dim(W)=k < n-1. Since k < n-1, there exist W' ∈𝒲_n-1 such that W ⊂ W'. Thus W+W'=W'≠𝕍, thereby contradicting that 𝒲_n-1∪{W} is a clique. Hence, 𝒲_n-1 is a maximal clique in 𝒢(𝕍). 

 There exists a graph homomorphism from 𝒢(𝕍) to the subgraph induced by 𝒲_n-1, defined in Theorem <ref>. 

Since 𝒲_n-1 is a clique, subgraph induced by it ⟨𝒲_n-1⟩ is a complete graph. As every non-trivial proper subspace W of 𝕍 is contained in at least one (possibly more than one) subspace in 𝒲_n-1,  there exists a map φ: 𝒢(𝕍) →⟨𝒲_n-1⟩ given by W ↦ W', where W' is an n-1 dimensional subspace of 𝕍 containing W. The existence of such a map is guaranteed by the axiom of choice. 

It is to be noted that if W_1 ∼ W_2 in 𝒢(𝕍), i.e., W_1+W_2=𝕍, then W_1 and W_2 are not contained in same subspace in 𝒲_n-1. Thus W'_1≠ W'_2. Thus, as ⟨𝒲_n-1⟩ is a complete graph, W'_1∼ W'_2. Hence φ preserve adjacency and is a graph homomorphism. 



Lemma <ref> will be useful in finding clique number and chromatic number of 𝒢(𝕍) when the field 𝔽 is finite. (See Theorem <ref>) 


 If n is odd, i.e., n=2m+1, then the collection 𝒲[m] of all non-trivial subspaces of 𝕍 with dimension less than or equal to m is a maximal independent set in 𝒢(𝕍).

For any W_1,W_2 ∈𝒲[m], W_1+W_2 ≠𝕍 as dim(W_1+W_2)≤ 2m <n. Thus, 𝒲[m] is an independent set. For any W with dim(W)>m, there exists a subspace W' ∈𝒲[m] such that W+W'=𝕍. Thus, 𝒲[m] is a maximal independent set. 

 Let n is even, i.e., n=2m and 𝒲[m-1] be the collection of all non-trivial subspaces of 𝕍 with dimension less than or equal to m-1. Let α (≠θ) ∈𝕍 and 𝒲^α[m] be the collection of all non-trivial subspaces of 𝕍 containing α and having dimension m. Then 𝒲[m-1]∪𝒲^α[m] is a maximal independent set in 𝒢(𝕍).

Let W_1,W_2 ∈𝒲[m-1]∪𝒲^α[m]. If at least one of W_1,W_2 ∈𝒲[m-1], W_1+W_2 ≠𝕍 as dim(W_1+W_2)≤ 2m-1 <n and thus W_1 ≁W_2. If both W_1,W_2 ∈𝒲^α[m], then as α∈ W_1 ∩ W_2, dim(W_1∩ W_2)≥ 1 and as a result dim(W_1+W_2)=dim(W_1)+dim(W_2)-dim(W_1∩ W_2)≤ 2m-1<n. Thus W_1 ≁W_2. Hence 𝒲[m-1]∪𝒲^α[m] is an independent set.

For maximality, let W be a proper subspace of 𝕍 not in 𝒲[m-1]∪𝒲^α[m]. If dim(W)=m, then as α∉W, there exists a subspace W' ∈𝒲^α[m] such that W+W'=𝕍. If dim(W)>m, then there exists a subspace W”∈𝒲[m-1] such that W+W”=𝕍. Thus, 𝒲[m-1]∪𝒲^α[m] is a maximal independent set in 𝒢(𝕍). 





§ DOMINATING SETS IN 𝒢(𝕍)

In this section, we study the minimal dominating sets and domination number of 𝒢(𝕍) and use it prove that the subspace sum graph of two vector spaces are isomorphic if and only if the two vector spaces are isomorphic.
 If 𝒲 be a dominating set in 𝒢(𝕍), then |𝒲|≥ n, where dim(𝕍)=n.

Let α be a non-null vector in 𝕍. Consider the subspace ⟨α⟩. Since 𝒲 is a dominating set, either ⟨α⟩∈𝒲 or there exists W_1 ∈𝒲 such that ⟨α⟩∼ W_1 i.e., ⟨α⟩ + W_1 = 𝕍. If ⟨α⟩∈𝒲, we choose some other α'≠θ from 𝕍 such that ⟨α' ⟩∉𝒲. However, if ⟨α⟩∈𝒲 for all α∈𝕍∖{θ}, then 𝒲 contains all the one-dimensional subspaces of 𝕍. Now, irrespective of whether the field is finite or infinite, the number of one-dimensional subspaces of 𝕍 is greater than n. (See Remark <ref>) Hence, the lemma follows trivially. Thus, we assume that α∉𝒲. Then as indicated earlier there exists W_1 ∈𝒲 such that ⟨α⟩ + W_1 = 𝕍. Note that dim(W_1)=n-1. 

We choose a non-null vector α_1 ∈ W_1. By similar arguments we can assume that ⟨α_1⟩∉𝒲. As 𝒲 is a dominating set, there exists W_2∈𝒲 such that ⟨α_1 ⟩ + W_2 =𝕍. It is to be noted that dim(W_2)=n-1 and W_1≠ W_2, as α_1∈ W_1∖ W_2.

Now consider the subspace W_1∩ W_2. As W_1,W_2 are of dimension n-1, W_1+W_2=𝕍. Thus by the result dim(W_1+W_2)=dim(W_1)+dim(W_2)-dim(W_1 ∩ W_2), we have dim(W_1 ∩ W_2)=n-2. We choose α_2(≠θ) ∈ W_1 ∩ W_2 and without loss of generality assume that ⟨α_2 ⟩∉𝒲. Therefore there exists W_3 ∈𝒲 such that ⟨α_2 ⟩ + W_3=𝕍. Again we note that dim(W_3)=n-1 and W_3≠ W_1, W_3 ≠ W_2, as α_2∈ (W_1 ∩ W_2)∖ W_3.

Now consider the subspace W_1∩ W_2 ∩ W_3. Since dim(W_3)=n-1 and (W_1 ∩ W_2)⊄W_3, we have (W_1∩ W_2)+W_3=𝕍. Thus by using dim[(W_1∩ W_2)+W_3]=dim(W_1∩ W_2)+dim(W_3)-dim(W_1 ∩ W_2 ∩ W_3), we have dim(W_1 ∩ W_2∩ W_3)=n-3. As in earlier cases, we choose α_3(≠θ) ∈ W_1 ∩ W_2∩ W_3 and there exists W_4 ∈𝒲 such that ⟨α_3 ⟩ + W_4=𝕍 with dim(W_4)=n-1 and W_4≠ W_1, W_2, W_3.

This process continues till we get W_n ∈𝒲 such that ⟨α_n-1⟩ + W_n=𝕍 with dim(W_n)=n-1 and W_n≠ W_1, W_2,…,W_n-1 and dim(W_1 ∩ W_2 ∩⋯ W_n)=0.

Thus, there are at least n many distinct subspaces W_1, W_2,…,W_n in 𝒲 and the lemma holds. 

 If the base field 𝔽 is infinite and since n>1, then there are infinitely many one-dimensional subspaces. If 𝔽 is finite with q elements and since n>1, then from the proof of Theorem <ref>, it follows that number of one-dimensional subspaces is q^n-1+q^n-2+⋯+1 is greater than n.

 Let {α_1,α_2,…,α_n} be a basis of 𝕍 and W_i=⟨α_1,α_2,…,α_i-1,α_i+1,…α_n⟩ for i=1,2,⋯,n. Then the collection 𝒲={W_i: 1≤ i ≤ n} is a minimum dominating set in 𝒢(𝕍) and hence γ(𝒢(𝕍))=n.

Let W be an arbitrary vertex of 𝒢(𝕍) and θ≠α∈ W. Suppose α=c_1α_1+c_2α_2+⋯ +c_n α_n with at least one c_i≠ 0. If c_j ≠ 0, then ⟨α⟩ + W_j = 𝕍 and hence W+W_j=𝕍, i.e., W ∼ W_j. Thus 𝒲 is a dominating set. Now consider 𝒲∖{W_i}. As ⟨α_i ⟩ + W_j=W_j for i ≠ j, we have ⟨α_i ⟩≁W_j, ∀ W_j ∈𝒲∖{W_i}. Thus 𝒲∖{W_i} is not a dominating set, thereby showing that 𝒲 is a minimal dominating set. Now the theorem follows from Lemma <ref>. Let 𝕍_1 and 𝕍_2 be two finite dimensional vector spaces over the same field 𝔽. Then 𝕍_1 and 𝕍_2 are isomorphic as vector spaces if and only if 𝒢(𝕍_1) and 𝒢(𝕍_2) are isomorphic as graphs.

It is quite obvious that if 𝕍_1 and 𝕍_2 are isomorphic as vector spaces, then 𝒢(𝕍_1) and 𝒢(𝕍_2) are isomorphic as graphs. For the other part, let 𝒢(𝕍_1) and 𝒢(𝕍_2) be isomorphic as graphs. Let dim(𝕍_1)=n_1 and dim(𝕍_2)=n_2. Then, by Theorem <ref>, the domination numbers of 𝒢(𝕍_1) and 𝒢(𝕍_2) are n_1 and n_2 respectively. However, as the two graphs are isomorphic, n_1=n_2=n (say). Thus 𝕍_1 and 𝕍_2 are of same finite dimension over the field 𝔽 and hence both are isomorphic to 𝔽^n as vector spaces.

If 𝕍 is an n dimensional vector space, then the total domination number γ_t, connected domination number γ_c and clique domination number γ_cl of 𝒢(𝕍) are all equal to n, i.e., 
    γ=γ_t=γ_c=γ_cl=n.

It is known that if a graph has a dominating clique and γ≥ 2, then γ≤γ_t ≤γ_c ≤γ_cl (See pg. 167 of <cit.>). Thus, it suffices to show that the minimum dominating set 𝒲={W_i: 1≤ i ≤ n} (constructed as in Theorem <ref>) is a total dominating set, a connected dominating set as well as a dominating clique. Since W_i ∼ W_j in 𝒢(𝕍) for i ≠ j, 𝒲 is a total dominating set. Moreover, the subgraph ⟨𝒲⟩ spanned by 𝒲 is a complete graph and hence connected. Thus, 𝒲 is a connected dominating set as well as a dominating clique. 



§ THE CASE OF FINITE FIELDS

In this section, we study some properties of 𝒢(𝕍) if the base field 𝔽 is finite, say of order q=p^r where p is a prime. In particular, we find the order, degree, chromatic number, clique number and edge connectivity of 𝒢(𝕍) and show that 𝒢(𝕍) is never Hamiltonian.

It is known that the number of k dimensional subspaces of an n-dimensional vector space over a finite field of order q is the q-binomial coefficient (See Chapter 7 of <cit.>)

    [ [ n; k ]]_q=(q^n -1)(q^n-q)⋯ (q^n-q^k-1)(q^k-1)(q^k-q)⋯ (q^k-q^k-1),
 and hence the total number of non-trivial proper subspaces of 𝕍, i.e., the order of 𝒢(𝕍) is given by 
    ∑_k=1^n-1[ [ n; k ]]_q=G(n,q)-2,

where G(n,q) is the Galois number[For definition, see <cit.>.].


 Let W be a k-dimensional subspace of an n-dimensional vector space 𝕍 over a finite field 𝔽 with q elements. Then degree of W in 𝒢(𝕍), deg(W)=∑_r=0^k-1N_r, where 
    N_r=(q^k-1)(q^k-q)⋯(q^k-q^r-1)(q^n-q^k)(q^n-q^k+1)⋯(q^n-q^n-1)(q^n-k+r-1)(q^n-k+r-q)⋯(q^n-k+r-q^n-k+r-1)


Since deg(W)= the number of subspaces whose sum with W is 𝕍 and dim(W)=k<n, the subspaces adjacent to W have dimension at least n-k, i.e., a subspace W' is adjacent to W if dim(W')=n-k+r and dim(W∩ W')=r where 0≤ r ≤ k-1. To find such subspaces W', we choose r linearly independent vectors from W and n-k linearly independent vectors from 𝕍∖ W, and generate W' with these n-k+r linearly independent vectors.[For details, see pg. 22 of <cit.>] Since, the number of ways we can choose r linearly independent vectors from W is (q^k-1)(q^k-q)⋯(q^k-q^r-1), the number of ways we can choose n-k linearly independent vectors from 𝕍∖ W is (q^n-q^k)(q^n-q^k+1)⋯(q^n-q^n-1) and the number of bases of an n-k+r dimensional subspace is (q^n-k+r-1)(q^n-k+r-q)⋯(q^n-k+r-q^n-k+r-1), the number of subspaces W' with dim(W')=n-k+r and dim(W∩ W')=r is 

    N_r=(q^k-1)(q^k-q)⋯(q^k-q^r-1)(q^n-q^k)(q^n-q^k+1)⋯(q^n-q^n-1)(q^n-k+r-1)(q^n-k+r-q)⋯(q^n-k+r-q^n-k+r-1)

Now, as 0≤ r ≤ k-1, 

    deg(W)=∑_r=0^k-1N_r.
 It is clear from Theorem <ref> that deg(W) depends solely on its dimension and it is minimized if dim(W)=1 and maximized if dim(W)=n-1, i.e., 
    δ=q^n-1Δ=∑_r=0^n-2[ [ n-1;   r ]]_q q^n-r-1q^r+q^r-1+⋯ +q+1.
 
 𝒢(𝕍) is Eulerian if and only if q is even.

From Theorem <ref>, 

    N_r={(q^k-1)(q^k-q)⋯(q^k-q^r-1)}{(q^n-q^k)(q^n-q^k+1)⋯(q^n-q^n-1)}(q^n-k+r-1)(q^n-k+r-q)⋯(q^n-k+r-q^n-k+r-1)


    ={q^{1+2+⋯+(r-1)}(q^k-1)⋯(q^k-r+1-1)}{q^{k+(k+1)+⋯ +(n-1)}(q^n-k-1)⋯(q-1)}q^{1+2+⋯+ (n-k+r-1)}(q^n-k+r-1)(q^n-k+r-1-1)⋯(q-1)


    =q^r(r-1)/2(q^k-1)⋯(q^k-r+1-1)q^{n(n-1)-k(k-1)}/2(q^n-k-1)⋯(q-1)q^{(n-k+r)(n-k+r-1)}/2(q^n-k+r-1)(q^n-k+r-1-1)⋯(q-1)


    =q^r(r-1)/2q^{n(n-1)-k(k-1)}/2q^{(n-k+r)(n-k+r-1)}/2· (q^k-1)⋯(q^k-r+1-1)(q^n-k-1)⋯(q^n-k+r+1-1)


    =q^(n-k)(k-r)· (q^k-1)⋯(q^k-r+1-1)(q^n-k-1)⋯(q^n-k+r+1-1)


If q is even, N_r is even for all r satisfying 0≤ r ≤ k-1. Hence, by Theorem <ref>, for any subspace W of 𝕍 of dimension k, deg(W)=∑_r=0^k-1N_r is even. As all vertices of 𝒢(𝕍) are of even degree, 𝒢(𝕍) is Eulerian. On the other hand, if q is odd, as the minimum degree δ=q^n-1, 𝒢(𝕍) is not Eulerian. 


 Edge connectivity of Γ(𝕍) is q^n-1.

From <cit.>, as Γ(𝕍) is of diameter 2 (by Theorem <ref>), its edge connectivity is equal to its minimum degree, i.e., q^n-1. 

 Let 𝕍 be an n-dimensional vector space over a finite field of order q. Then the clique number and chromatic number of 𝒢(𝕍) are both equal to 1+q+⋯+q^n-1.

By Theorem <ref>, 𝒲_n-1 is a maximal clique and 
    |𝒲_n-1|=[ [   n; n-1 ]]_q=[ [ n; 1 ]]_q=q^n-1q-1=1+q+⋯+q^n-1.
 Now, by Lemma <ref>, 𝒢(𝕍) is |𝒲_n-1|-colourable, i.e., χ(𝒢(𝕍))≤ |𝒲_n-1|. Moreover, as 𝒲_n-1 is a maximal clique, ω(𝒢(𝕍))≥ |𝒲_n-1|. As chromatic number of a graph is greater or equal to its clique number, we have the following inequality:

    ω(𝒢(𝕍)) ≤χ(𝒢(𝕍))≤ |𝒲_n-1| ≤ω(𝒢(𝕍)),
 i.e., 
    ω(𝒢(𝕍)) = χ(𝒢(𝕍))= |𝒲_n-1| =1+q+⋯+q^n-1.
  

 Theorem <ref> shows that 𝒢(𝕍) is weakly perfect. In Theorem <ref>, we establish a necessary and sufficient condition for 𝒢(𝕍) to be prefect. In Figure <ref>, the 7 inner vertices forms a maximum clique and the chromatic number is also 1+2+2^2=7. Also, as q=2, by Corollary <ref>, 𝒢(𝕍) is Eulerian.

 𝒢(𝕍) is perfect if and only if dim(𝕍)=3.

Let n=dim(𝕍)≥ 4. Let S={α_1,α_2,α_3,α_4} be 4 linearly independent vectors in 𝕍 and let S∪ T be the extension of S to a basis of 𝕍. Consider the following induced 5-cycle in 𝒢(𝕍): W_1∼ W_2 ∼ W_3 ∼ W_4 ∼ W_5 ∼ W_1 where W_1=⟨α_1,α_2,T⟩, W_2=⟨α_3,α_4,T⟩, W_3=⟨α_1+α_3,α_2,T⟩, W_4=⟨α_1,α_4, T ⟩ and W_5=⟨α_1+α_3,α_2+α_4,T ⟩. Thus, by Strong Perfect Graph Theorem, 𝒢(𝕍) is not perfect.

Let n=dim(𝕍)=3 and if possible, let there exists an induced odd cycle W_1∼ W_2∼ W_3∼⋯∼ W_2k+1∼ W_1 of  length greater than 3 in 𝒢(𝕍), where W_i's are distinct proper non-trivial subspaces of 𝕍.   Since, W_i ∼ W_i+1, therefore W_i + W_i+1=𝕍, i.e., at least one of W_i or W_i+1 is of dimension 2. Without loss of generality, let W_1 be of dimension 2. Now, there are two possibilities: dim(W_2)=1 or dim(W_2)=2.

If dim(W_2)=1, then as W_2 ∼ W_3, dim(W_3) must be 2. However, in that case we have W_1+W_3=𝕍, i.e., W_1 ∼ W_3, a contradiction. On the other hand, let dim(W_2)=2. Since, W_1 ≁W_3, i.e., W_1+W_3≠𝕍, we have dim(W_3)=1. Again, as W_2 ≁W_4, i.e., W_2+W_4≠𝕍, we have dim(W_4)=1. But, this implies W_3+W_4 ≠𝕍, i.e., W_3 ≁W_4, a contradiction. Thus, there does not exist any induced odd cycle of length greater than 3 in 𝒢(𝕍).

Let n=dim(𝕍)=3 and if possible, let there exists an induced odd cycle W_1∼ W_2∼ W_3∼⋯∼ W_2k+1∼ W_1 of  length greater than 3 in 𝒢(𝕍), where W_i's are distinct proper non-trivial subspaces of 𝕍. It is to be noted that in 𝒢(𝕍), W_i ≁W_j implies W_i+W_j=𝕍. Thus, as in previous case, without loss of generality, let W_1 be of dimension 2. Since, W_2 ∼ W_1 in 𝒢(𝕍), W_1+W_2≠𝕍, i.e.,  W_2 ⊂ W_1 and dim(W_2)=1.  Now, as W_2 ≁W_4 in 𝒢(𝕍), W_2+W_4 = 𝕍, i.e., dim(W_4)=2. Also, as W_3∼ W_4, we have W_3+W_4≠𝕍 and hence dim(W_3)=1. Similarly, as W_5∼ W_4, we have W_5+W_4≠𝕍 and hence dim(W_5)=1. Again as W_3≁W_5, we have W_3+W_5= 𝕍. However this is impossible as dim(W_3)=dim(W_5)=1. Thus, there does not exist any induced odd cycle of length greater than 3 in 𝒢(𝕍).

Thus, as neither 𝒢(𝕍) nor its complement have any induced odd cycle of length greater than 3, by Strong Perfect Graph Theorem, 𝒢(𝕍) is perfect. Hence, the theorem. 





§ CONCLUSION

In this paper, we represent subspaces of a finite dimensional vector space as a graph and study various inter-relationships among 𝒢(𝕍) as a graph and 𝕍 as a vector space. The main goal of these discussions was to study the algebraic properties of 𝕍 and graph theoretic properties of 𝒢(𝕍), and to establish the equivalence between the corresponding graph and vector space isomorphisms. Apart from this, we also study basic properties e.g., completeness, connectedness, domination, chromaticity, maximal cliques, perfectness and maximal independent sets of 𝒢(𝕍). As a topic of further research, one can look into the structure of automorphism groups, Hamiltonicity and independence number of 𝒢(𝕍).




§ ACKNOWLEDGEMENT

The author is thankful to Sabyasachi Dutta, Anirban Bose and Sourav Tarafder for some fruitful discussions on the paper. The research is partially funded by NBHM Research Project Grant, (Sanction No. 2/48(10)/2013/ NBHM(R.P.)/R&D II/695), Govt. of India. 

20
anderson-livingston D. F. Anderson and P. S. Livingston: The zero-divisor graph of a commutative ring, Journal of Algebra, 217 (1999), 434-447.
mks-ideal I. Chakrabarty, S. Ghosh, T.K. Mukherjee, and M.K. Sen: Intersection graphs of ideals of rings, Discrete Mathematics 309, 17 (2009): 5381-5392.
angsu-comm-alg A. Das: Non-Zero Component Graph of a Finite Dimensional Vector Space, Communications in Algebra, Vol. 44, Issue 9, 2016: 3918-3926.
angsu-lin-mult-alg A. Das: Non-Zero Component Union Graph of a Finite Dimensional Vector Space, Linear and Multilinear Algebra, DOI: 10.1080/03081087.2016.1234577
angsu-comm-alg-2 A. Das: Subspace Inclusion Graph of a Vector Space, Communications in Algebra, Vol. 44, Issue 11, 2016: 4724-4731.
angsu-jaa A. Das: On Non-Zero Component Graph of Vector Spaces over Finite Fields, Journal of Algebra and Its Applications, Volume 16, Issue 01, January 2017.

galois-number J. Goldman, G.C. Rota: The number of subspaces of a vector space, Recent Progress in Combinatorics (Proc. Third Waterloo Conf. on Combinatorics, 1968), Academic Press, New York, 75-83, 1969.
domination-book T.W. Haynes, S.T. Hedetniemi and P.J. Slater: Fundamentals of Domination in Graphs, Marcel Dekker Inc., 1998.
int-vecsp-2 N. Jafari Rad, S.H. Jafari: Results on the intersection graphs of subspaces of a vector space, http://arxiv.org/abs/1105.0803v1
quantum-book V. Kac, P. Cheung: Quantum Calculus, Universitext, Springer, 2002.
int-vecsp-3 J.D. Laison and Y. Qing: Subspace Intersection Graphs, Discrete Mathematics 310, 3413-3416, 2010.
survey2 H.R. Maimani, M.R. Pournaki, A. Tehranian, S. Yassemi: Graphs Attached to Rings Revisited, Arab J. Sci. Eng. 36, 997-1011, 2011.
plesnik J. Plesnik: Critical graphs of given diameter, Acta Fac. Rerum Natur. Univ. Comenian. Math., 30, 71-93, 1975.
int-vecsp-1 Y. Talebi, M.S. Esmaeilifar, S. Azizpour: A kind of intersection graph of vector space, Journal of Discrete Mathematical Sciences and Cryptography 12, no. 6, 681-689, 2009.
west-graph-book D.B. West: Introduction to Graph Theory, Prentice Hall, 2001.

