Menu
In this paper, we introduce a graph structure, called component intersection graph, on a finite dimensional vector space \(\mathbb{V}\). The connectivity, diameter, maximal independent sets, clique number, chromatic number of component intersection graph have been studied.
Apart from its combinatorial motivation, graph theory can also identify various algebraic structures. The investigation of graphs associated to algebraic structures is very important and main task of studying graphs associated to algebraic structures is to characterize the algebraic structures with graph and vice versa. Many fundamental papers devoted to graphs assigned to a ring had been studied. Till date, a lot of researches, viz.[1, 2, 3, 4, 5, 6] have been performed on simple graph structures to commutative rings. Recently, some algebraic graphs associated to groups, modules and vector spaces have been studied by different mathematicians (see [2, 6, 7, 8, 9]).
For the last few decades several mathematicians studied such graphs on various algebraic structures. These interdisciplinary studies allow us to obtain characterizations and representations of special classes of algebraic structures in terms of graphs and vice versa. The first step in this direction was initiated by Bosak [10] in 1964. After that Cs\(\acute{a}\)k\(\acute{a}\)ny and Poll\(\acute{a}\)k [11] studied the graphs of subgroups of a finite group. Zelinka [12] continued the work on intersection graphs of the nontrivial subgroups of finite abelian groups.
In[5], Chakrabarty et. al introduced the intersection graph \(G(R)\) of a family of nontrivial left ideals of a ring \(R\). Let \(L(R)\) denotes the set of all nontrivial (nonzero proper) left ideals of \(R.\) The intersection graph of \(L(R)\) is the undirected simple graph (without loops and multiple edges) whose vertices are in a one-to-one correspondence with all nontrivial left ideals of \(R\) and two distinct vertices are joined by an edge if and only if the corresponding left ideals of \(R\) have a nontrivial (nonzero)intersection.
Most properties of a vector space are connected to the behavior of its basis. Also, basis plays a crucial roles in the study of vector space constructions. Let \(\mathfrak{B}=\{\mathfrak{v}_{1},\mathfrak{v}_{2},\ldots,\mathfrak{v}_{n}\}\) be a basis of a \(n\)-dimensional vector space \(\mathbb{V}\) over a field \(\mathbb{F}.\) Then any vector \(\mathfrak{v}\in\mathbb{V}\) can be expressed as a linear combination of the form \(\mathfrak{v}=\sum\limits_{i=1}^{n}\alpha_{i}\mathfrak{v}_{i}.\) We define skeleton of \(\mathfrak{v}\) with respect to \(\mathfrak{B},\) as \(\mathfrak{S}_{\mathfrak{B}}(\mathfrak{v})=\{\mathfrak{v}_{i}~|~ \alpha_{i}\neq0\}\) and \(\mathbb{V}_{\mathfrak{B}}=\{\mathfrak{v}\in\mathbb{V}~|~ 0<|\mathfrak{S}_{\mathfrak{B}}(\mathfrak{v})|<n \},\) \(\mathfrak{S}^{k}=\{\mathfrak{v}\in\mathbb{V}~|~ k\leq|\mathfrak{S}_{\mathfrak{B}}(\mathfrak{v})|\leq n-1 \},\) \([\mathfrak{S}^{k}]=\{u\in\mathbb{V}~|~ |\mathfrak{S}_{\mathfrak{B}}(u)|=k\},\) \([\mathfrak{S}_{v}^{k}]=\{u\in\mathbb{V}~|~ |\mathfrak{S}_{\mathfrak{B}}(u)|=k~\mbox{and}~v\in\mathfrak{S}_{\mathfrak{B}}(u)\}.\)
Das [13] introduced and studied the nonzero component graph \(\Gamma(\mathbb{V}_{\mathfrak{v}})\) on a finite dimensional vector space \(\mathbb{V},\) which is a simple undirected graph with vertex set as nonzero vectors of \(\mathbb{V}\) and any two distinct vertices \(x, y\) are adjacent if and only if there exists at least one \(\mathfrak{v}_{i}\) along which both \(x\) and \(y\) have nonzero components. Later, on in [8] Das investigated another interesting graph known as non-zero component union graph \(\Gamma(\mathbb{V}_{\mathfrak{B}}),\) which is a simple undirected graph with vertex set as non-zero vectors of \(\mathbb{V}\) and any two distinct vertices \(u, v\) are adjacent if and only if \(\mathfrak{S}_{\mathfrak{B}}(\mathfrak{u})\cup\mathfrak{S}_{\mathfrak{B}}(\mathfrak{v})=\mathfrak{B}.\)
Motivated by the above work, we introduce a new graph structure \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V})\) known as component intersection graph associated with the basis \(\mathfrak{B}\) of a finite dimensional vector space \(\mathbb{V}\). \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V})\) is a graph with the set of vertices \(\mathbb{V}_{\mathfrak{B}}\) and any two distinct vertices \(\mathfrak{u}\) and \(\mathfrak{v}\) of \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V})\) are adjacent if and only if \(\mathfrak{S}_{\mathfrak{B}}(\mathfrak{u})\cap\mathfrak{S}_{\mathfrak{B}}(\mathfrak{v})=\emptyset.\)
In Section 3, we investigate some basic properties of component intersection graph \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V})\) and show that \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V})\) is connected and \(diam(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V}))=3.\) Also, we investigate the graph theoretic properties of \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V})\) and algebraic properties of \(\mathbb{V}.\) Furthermore, we establish the equivalence between vector space isomorphism and graph isomorphism. Apart from this, we also study some basic properties of \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V}),\) i.e., maximal clique, chromatic number of \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V}).\)
In Section 4, we evaluate the order of \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V})\) and the degree of a vertex of \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V}),\) when the order of the base field \(\mathbb{F}\) is finite i.e., \(\mathbb{F}=\mathbb{F}_{q}\). Moreover, we show that \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V})\) is Eulerian. Finally in Section 5, we discuss the area of further research for \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V})\) , for example, the structure of automorphism group, domination number and independent sets of \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V}),\) when the base field \(\mathbb{F}\) is finite.
Throughout this paper, \(\mathbb{V}\) denotes a finite dimensional vector space over a field \(\mathbb{F}\) and \(\mathbb{F}_{q}\) is a finite field of order \(q.\) Let \(G=(V(G),E(G))\) be a Graph, where \(V(G)\) is the set of vertices and \(E(G)\) is the set of edges of \(G.\) We say that \(G\) is connected if there exists a path between any two distinct vertices of \(G\). For vertices \(a\) and \(b\) of \(G\), \(d(a,b)\) denotes the length of the shortest path from \(a\) to \(b\). In particular, \(d(a,a)=0\) and \(d(a,b)=\infty~\mbox{if~there~is~no~such~path}.\) The diameter of \(G\), denoted by \(diam(G)=sup\{d(a,b)~|~a,b\in V(G)\}.\) A cycle in a graph \(G\) is a path that begins and ends at the same vertex. A cycle of length \(n\) is denoted by \(C_{n}.\) A graph is said to be Eulerian if it contains a cycle containing all the edges in \(G\) exactly once. The girth of \(G\), denoted by \(gr(G)\), is the length of a shortest cycle in \(G,\) \(~(gr(G)=\infty ~ \mbox{if}~G~\mbox{contains~no~cycle}).\) Two graphs \(G_{1} =(V(G_{1}),E(G_{1}))\) and \(G_{2}=(V(G_{2}),E(G_{2}))\) are said to be isomorphic if there exists a bijection \(\phi: V(G_{1})\rightarrow V(G_{2}))\) such that \((u,v)\in E(G_{1})\) if and only if \((\phi(u),\phi(v))\in E(G_{2}).\) A complete graph \(G\) is a graph where all distinct vertices are adjacent. The complete graph with \(|V(G)|=n\) is denoted by \(K_{n}.\) A graph \(H=(V(H),E(H))\) is said to be a subgraph of \(G,\) if \(V(H)\subseteq V(G)\) and \(E(H)\subseteq E(G).\) Moreover, \(H\) is said to be induced subgraph of \(G\) if \(V(H)\subseteq V(G)\) and \(E(H)=\{(u,v)\in E(G)~|~u,v\in V(H)\}\) and is denoted by \(G[V(H)].\) Also \(G\) is called a null graph if \(E(G)=\emptyset.\) For a graph \(G,\) a complete subgraph of \(G\) is called a clique. The clique number, \(\omega(G),\) is the greatest integer \(n\geqslant 1\) such that \(K_{n}\subseteq G,\) and \(\omega(G)=\infty ~\text{if}~\) \(K_{n}\subseteq G\) for all \(n\geqslant 1.\) The chromatic number \(\chi(G)\) of a graph \(G\) is the minimum number of colours needed to colour all the vertices of \(G\) such that every two adjacent vertices get different colours. For a connected graph \(G,\) \(\delta= \mbox{min}\{deg(x)~|~x\in V(G)\}\) and \(\Delta=\mbox{max}\{deg(x)~|~x\in V(G)\}.\) A subset \(\mathfrak{D}\) of \(V(G)\) is said to be dominating set if each vertex in \(V(G)\setminus \mathfrak{D}\) is adjacent to at least one vertex in \(\mathfrak{D}.\) The dominating number \(\gamma(G)\) are the minimum size of a dominating set in \(G.\) Graph-theoretic terms are presented as they appeared in Diestel [14].
In this section, we study some basic properties, like connectedness, diameter, completeness, clique number and chromatic number of \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V}).\)
Example 1. Let \(\mathbb{F}_{2}\times\mathbb{F}_{2}\) and \(\mathbb{F}_{2}\times\mathbb{F}_{2}\times\mathbb{F}_{2}\) be the vector spaces over \(\mathbb{F}_{2}\) and \(\mathfrak{B}_{1}=\{\alpha_{1},\alpha_{2}\},\) \(\mathfrak{B}_{2}=\{\beta_{1},\beta_{2},\beta_{3}\}\) be the bases of \(\mathbb{F}_{2}\times\mathbb{F}_{2}\) and \(\mathbb{F}_{2}\times\mathbb{F}_{2}\times\mathbb{F}_{2}\) respectively. Clearly, \(V(\mathfrak{I}^{\mathfrak{B}_{1}}(\mathbb{F}_{2}\times\mathbb{F}_{2}))=\{\alpha_{1},\alpha_{2}\}\) and \(V(\mathfrak{I}^{\mathfrak{B}_{2}}(\mathbb{F}_{2}\times\mathbb{F}_{2}\times\mathbb{F}_{2})) =\{\beta_{1},\beta_{2},\beta_{3},\beta_{1}+\beta_{2},\beta_{2}+\beta_{3},\beta_{1}+\beta_{3}\}\) respectively. The components intersection graphs \(\mathfrak{I}^{\mathfrak{B}_{1}}(\mathbb{F}_{2}\times\mathbb{F}_{2})\) and \(\mathfrak{I}^{\mathfrak{B}_{2}}(\mathbb{F}_{2}\times\mathbb{F}_{2}\times\mathbb{F}_{2})\) are given by the following Figures 1 and 2.
Remark 1. In view of above example, it may be noticed that the vertex set of our proposed graph \(\mathfrak{I}^{\mathfrak{B}_{1}}(\mathbb{F}_{2}\times\mathbb{F}_{2})\) is different from the vertex set of \(\Gamma((\mathbb{F}_{2}\times\mathbb{F}_{2})_{\alpha})\) and \(\Gamma(\mathbb{F}_{2}\times\mathbb{F}_{2})_{\mathfrak{B}_{1}}\) introduced by Das [8, 13]. Also the vertex set of \(\mathfrak{I}^{\mathfrak{B}_{2}}(\mathbb{F}_{2}\times\mathbb{F}_{2}\times\mathbb{F}_{2})\) is different from the vertex set of \(\Gamma((\mathbb{F}_{2}\times\mathbb{F}_{2}\times\mathbb{F}_{2})_{\alpha})\) and \(\Gamma(\mathbb{F}_{2}\times\mathbb{F}_{2}\times\mathbb{F}_{2})_{\mathfrak{B}_{2}}.\) The vertices \(\alpha_{1}\) and \(\alpha_{2}\) are not adjacent in \(\Gamma(\mathbb{V}_{\alpha}),\) but are adjacent in \(\mathfrak{I}^{\mathfrak{B}_{1}}(\mathbb{F}_{2}\times\mathbb{F}_{2}).\) Moreover, \(\beta_{1}\) and \(\beta_{2}\) are not adjacent in \(\Gamma(\mathbb{F}_{2}\times\mathbb{F}_{2}\times\mathbb{F}_{2})_{\mathfrak{B}_{2}}\) and \(\Gamma((\mathbb{F}_{2}\times\mathbb{F}_{2}\times\mathbb{F}_{2})_{\beta})\), but are adjacent in \(\mathfrak{I}^{\mathfrak{B}_{2}}(\mathbb{F}_{2}\times\mathbb{F}_{2}\times\mathbb{F}_{2}).\)
Remark 2. Let \(\mathcal{B}=\{\gamma_{1},\gamma_{2},\ldots,\gamma_{n}\}\) be the basis of a vector space \(\mathbb{V}\) such that \(n\geq3.\) The vertex set of \(\mathfrak{I}^{\mathcal{B}}(\mathbb{V})\) is different from the vertex set of \(\Gamma(\mathbb{V})_{\mathcal{B}}\) and \(\Gamma(\mathbb{V}_{\gamma}).\) Also \(\gamma_{1}\) and \(\gamma_{2}\) are not adjacent in \(\Gamma(\mathbb{V}_{\gamma})\) and \(\Gamma(\mathbb{V})_{\mathcal{B}},\) but are adjacent in \(\mathfrak{I}^{\mathcal{B}}(\mathbb{V}).\)
Theorem 1. Let \(\mathbb{V}\) be a \(n\)-dimensional vector space over a field \(\mathbb{F}.\) Then \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V})\) is a complete bipartite graph if and only if \(n=2\).
Proof. Suppose that \(dim(\mathbb{V})=2\) and \(\mathfrak{B}=\{u,v\}\) is a basis of \(\mathbb{V}.\) Then \(V(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V}))\) can be partitioned into two sets \(\mathfrak{B}_{u}=\{\alpha u ~|~ 0\neq\alpha\in\mathbb{F}\}\) and \(\mathfrak{B}_{v}=\{\beta v ~|~ 0\neq\beta\in\mathbb{F}\}\) such that \(\mathfrak{B}_{u}\cap\mathfrak{B}_{v}=\emptyset\) and \(\mathfrak{B}_{u}\cup\mathfrak{B}_{v}=V(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V})).\) If \(u_{1}\in\mathfrak{B}_{u}\) and \(u_{2}\in\mathfrak{B}_{v},\) then \(u_{1}\sim u_{2}\) in \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V})\) and any two vertices of \(\mathfrak{B}_{u}\) are not adjacent in \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V}).\) Similarly, any two vertices of \(\mathfrak{B}_{v}\) are not adjacent in \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V}).\) Hence \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V})\) is complete bipartite.
Conversely, assume that \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V})\) is complete bipartite and let \(dim(\mathbb{V})=k.\) If \(k>2,\) then there exists a basis \(\mathfrak{B}=\{v_{1},v_{2},\cdots,v_{k}\}\) of \(\mathbb{V}\) such that \(\mathfrak{S}(v_{i})\cap\mathfrak{S}(v_{j})=\emptyset\) for \(i\neq j\) and \(1\leq i,j\leq k.\) Thus \(v_{1},v_{2},v_{3}\in V(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V}))\) such that \(\mathfrak{S}(v_{i})\cap\mathfrak{S}(v_{j})=\emptyset\) for \(i\neq j\) and \(1\leq i,j\leq 3\) and \(v_{1}\sim v_{2}\sim v_{3}\sim v_{1}\) is a cycle of length three. Hence \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V})\) is not complete bipartite. If \(k=2,\) then by direct part of this theorem, \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V})\) is complete bipartite. This complete the proof. ◻
If \(\mathbb{V}\) is a finite dimensional vector space over \(\mathbb{F},\) then it is easy to show that \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V})\) is empty graph if and only if \(dim(\mathbb{V})=1.\) Apart from this, the following theorem holds trivially;
Theorem 2. \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V})\) is complete if and only if \(dim(\mathbb{V})=2\) and \(\mathbb{F}=\mathbb{F}_{2}.\)
Now we facilities our discussion with the following lemma;
Lemma 1. Let \(\mathbb{V}\) be a finite dimensional vector space such that \(dim(\mathbb{V})\geq2.\) Then \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V})\) is connected and \(diam(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V}))\leq3.\)
Proof. Let \(\mathfrak{B}\) be a basis of \(\mathbb{V}\) and \(u,v\) be two distinct vertices of \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V}).\) We have the following cases;
◻
The following theorem gives a characterization of the diameter of \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V})\);
Theorem 3. Let \(\mathbb{V}\) be a \(n\)-dimensional vector spaces over \(\mathbb{F}.\) Then \[diam(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V}))=\left\{ \begin{array}{ll} 1, & \mbox{if~ $n=2$ and $\mathbb{F}=\mathbb{F}_{2}$,} \\ 2, & \mbox{if~ $n=2$ and $\mathbb{F}\neq\mathbb{F}_{2}$,}\\ 3 , & \mbox{if~ $n\geq3$.} \end{array} \right.\]
Proof. Suppose that \(\mathfrak{B}=\{v_{1},v_{2},\cdots,v_{n}\}\) is a basis of \(\mathbb{V}.\) We have the following cases;
◻
The following theorem gives a characterization of the diameter of \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V})\);
Theorem 4. Let \(\mathbb{V}\) be a \(n\)-dimensional vector space over \(\mathbb{F}.\) Then \[gr(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V}))=\left\{ \begin{array}{ll} \infty, & \mbox{if~ $n=2$ and $\mathbb{F}=\mathbb{F}_{2}$,} \\ 4, & \mbox{if~ $n=2$ and $\mathbb{F}\neq\mathbb{F}_{2}$,}\\ 3 , & \mbox{if~ $n\geq3$.} \end{array} \right.\]
Proof. Suppose that \(\mathfrak{B}=\{v_{1},v_{2},\cdots,v_{n}\}\) is a basis of a \(n\)-dimensional vector space \(\mathbb{V}\) over a field \(\mathbb{F}.\) Now we have the following three cases;
◻
Theorem 5. Let \(\mathbb{V}\) be a vector space over a field \(\mathbb{F}\) with \(dim(\mathbb{V})\geq4.\) Then \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V})\) is triangulated.
Proof. Let \(\mathfrak{B}=\{v_{1},v_{2},\cdots,v_{n}\}\) be a basis of \(\mathbb{V}\) and \(w\in V(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V})).\) We have the following two cases;
◻
Theorem 6. Let \(\mathbb{V}\) be a finite dimensional vector space. Then \(dim(\mathbb{V})=n\) if and only if \(\omega(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V}))=n.\)
Proof. Suppose that \(\mathfrak{B}=\{v_{1},v_{2},\cdots,v_{n}\}\) is a basis of \(\mathbb{V}.\) Note that \(\mathfrak{B}\subseteq V(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V}))\) is a clique in \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V}).\) If possible, suppose \(\mathfrak{B}\cup\{w\}\) is a clique of \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V}),\) where \(w\in V(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V})).\) Then \(\mathfrak{S}_{\mathfrak{B}}(v_{i})\cap\mathfrak{S}_{\mathfrak{B}}(w)=\emptyset\) for all \(i=1,2,\cdots,n\) and \(\mathfrak{S}_{\mathfrak{B}}(w)=\emptyset,\) a contradiction. Finally, we prove that there does not exist any clique of size \(n+1.\) If \(\{w_{1},w_{2},\cdots,w_{n+1}\}\) is a clique of size \(n+1,\) then \(\mathfrak{S}_{\mathfrak{B}}(w_{i})\cap\mathfrak{S}_{\mathfrak{B}}(w_{j})=\emptyset\) for all \(i\neq j\) and \(1\leq i,j\leq n+1,\) \(|\bigcup\limits_{i=1}^{n+1}\mathfrak{S}_{\mathfrak{B}}(w_{i})|>|\mathfrak{B}|,\) a contradiction. Therefore the clique number \(\omega(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V}))\) of \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V})\) is \(n.\)
Conversely, assume that \(\omega(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V}))=n\) and dimension of \(\mathbb{V}\) is \(m.\) Then by direct part of this theorem, \(\omega(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V}))=m.\) Therefore \(m=n.\) ◻
Corollary 1. Let \(\mathbb{V}_{1}\) and \(\mathbb{V}_{2}\) be two finite dimensional vector spaces over the field \(\mathbb{F}\). Then \(\mathbb{V}_{1}\) and \(\mathbb{V}_{2}\) are isomorphic (as vector spaces) if and only if \(\mathfrak{I}^{\mathfrak{B}_{1}}(\mathbb{V}_{1})\) and \(\mathfrak{I}^{\mathfrak{B}_{2}}(\mathbb{V}_{2})\) are isomorphic (as graphs).
Proof. It is obvious that if \(\mathbb{V}_{1}\) and \(\mathbb{V}_{2}\) are isomorphic (as vector spaces), then \(\mathfrak{I}^{\mathfrak{B}_{1}}(\mathbb{V}_{1})\) and \(\mathfrak{I}^{\mathfrak{B}_{2}}(\mathbb{V}_{2})\) are isomorphic (as graphs).
Conversely, assume that \(\mathfrak{I}^{\mathfrak{B}_{1}}(\mathbb{V}_{1})\) and \(\mathfrak{I}^{\mathfrak{B}_{2}}(\mathbb{V}_{2})\) are isomorphic (as graphs) and \(dim(\mathbb{V}_{1}),\) \(dim(\mathbb{V}_{2})\) are \(m,\) \(n\) respectively. Then by Theorem 6, the clique number \(\omega(\mathfrak{I}^{\mathfrak{B}_{1}}(\mathbb{V}_{1}))\) and \(\omega(\mathfrak{I}^{\mathfrak{B}_{2}}(\mathbb{V}_{2}))\) are \(n-1\) and \(m-1\) respectively. However, as the two graphs are isomorphic, \(m=n.\) Thus \(\mathbb{V}_{1}\) and \(\mathbb{V}_{2}\) are finite dimensional over the field \(\mathbb{F}\) with \(m=n\) and hence both are isomorphic (as vector spaces). ◻
Corollary 2. Let \(\mathbb{V}\) be a vector space over a field \(\mathbb{F}\) and \(\mathfrak{I}^{\mathfrak{B}_{1}}(\mathbb{V}),\) \(\mathfrak{I}^{\mathfrak{B}_{2}}(\mathbb{V})\) be the graphs associated with \(\mathbb{V}\) with respect to the bases \(\mathfrak{B}_{1}=\{u_{1},u_{2},\cdots,u_{n}\}\) and \(\mathfrak{B}_{2}=\{v_{1},v_{2},\cdots,v_{n}\}\) of \(\mathbb{V}\) respectively. Then \(\mathfrak{I}^{\mathfrak{B}_{1}}(\mathbb{V})\) and \(\mathfrak{I}^{\mathfrak{B}_{2}}(\mathbb{V})\) are graph isomorphic.
Remark 3. The above corollary shows that the graph theoretic properties of \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V})\) does not depend on the choice of the basis \(\mathfrak{B}.\)
Theorem 7. Let \(\mathbb{V}\) be a \(n\)-dimensional vector space. Then the following statements hold;
Proof. Suppose that \(\mathfrak{B}=\{u_{1},u_{2},\ldots,u_{n}\}\) is a basis of \(\mathbb{V}.\)
◻
Theorem 8. If \(\mathbb{V}\) be a \(n\)-dimensional vector space, then \(\lambda(\mathfrak{I}_{\mathfrak{B}}(\mathbb{V}))=n\).
Proof. Let \(\mathfrak{B}=\{v_{1},v_{2},\cdots,v_{n}\}\) be a basis of \(\mathbb{V}.\) Since the clique number \(\omega(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V}))\) of \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V})\) is \(n\), \(\lambda(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V}))\geq n\). By Theorem 7 \((i)\), \(\lambda(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V}))\leq|\mathfrak{B}|.\) Moreover, since \(\mathfrak{B}\) is a maximal clique, \(\omega(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V}))\geq|\mathfrak{B}|.\) Since \(\omega(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V}))\leq \lambda(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V})),\) we have the following inequality. \[\omega(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V}))\leq \lambda(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V})) \leq|\mathfrak{B}|\leq\omega(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V})),\] and hence the theorem follows. ◻
Lemma 2. If \(\mathbb{V}\) is a \(n\)-dimensional vector space, then \(|\mathfrak{S}_{n-1}|\geq n.\)
Proof. Suppose that \(\mathfrak{B}=\{\mathfrak{v}_{1},\mathfrak{v}_{2},\cdots,\mathfrak{v}_{n}\}\) is a basis of a \(n\)-dimensional vector space \(\mathbb{V}.\) Clearly, \(\mathfrak{u}_{i} = \mathfrak{v}_{1}+\mathfrak{v}_{2}+\cdots+\mathfrak{v}_{i-1}\) \(+\mathfrak{v}_{i+1}+\cdots+\cdots,\mathfrak{v}_{n},\) for \(1\leq i\leq n\) are distinct \(n\) member of \(\mathfrak{S}_{n-1}.\) Hence proved. ◻
Lemma 3. If \(\mathbb{V}\) is a \(n\)-dimensional vector space and \(\mathfrak{D}\) is a dominating set in \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V}),\) then \(|\mathfrak{D}|\geq n.\)
Proof. Suppose that \(\mathfrak{D}\) is a dominating set of \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V}).\) We know that by Lemma 2, \(|\mathfrak{S}_{n-1}|\geq n.\) If \(\mathfrak{S}_{n-1}\subseteq\mathfrak{D},\) then \(|\mathfrak{D}|\geq n\) and we are done. Otherwise, there exist \(\mathfrak{u}_{i}^{1}\in\mathfrak{S}_{n-1}\setminus\mathfrak{D}\) and \(\mathfrak{w}_{1}\in\mathfrak{D}\cap\mathfrak{S}_{1}\) such that \(\mathfrak{u}_{i}^{1}\sim\mathfrak{w}_{1}.\) Clearly, \(|\mathfrak{S}_{\mathfrak{B}}(\mathfrak{w}_{1})|=1.\) Without loss of generality, we assume that \(\mathfrak{u}_{1}^{1}= \mathfrak{v}_{2}+\mathfrak{v}_{3}+\cdots+\mathfrak{v}_{n}.\) Therefore \(\mathfrak{u}_{j}^{2}= \mathfrak{v}_{2}+\mathfrak{v}_{3}+\cdots+\mathfrak{v}_{j-1}+\mathfrak{w}_{1}+\mathfrak{v}_{j+1}\) \(+\mathfrak{v}_{n},\) \(2\leq j\leq n\) are distinct \((n-2)\) member of \(\mathfrak{S}_{n-1}\) and \(\mathfrak{u}_{j}^{2}\nsim\mathfrak{w}_{1}.\) If \(\mathfrak{u}_{j}^{2}\in\mathfrak{D}\) for all \(2\leq j\leq n,\) then \(|\mathfrak{D}|\geq n\) and we are done. Otherwise, there exists \(\mathfrak{u}_{j}^{2}\notin\mathfrak{D}.\) Without loss of generality we assume that \(\mathfrak{u}_{2}^{2}\notin\mathfrak{D}.\) Since \(\mathfrak{u}_{2}^{2}\notin\mathfrak{D}\) and \(\mathfrak{u}_{2}^{2}\nsim\mathfrak{w}_{1},\) there exists \(\mathfrak{w}_{2}\in\mathfrak{S}_{1}\cap\mathfrak{D}\) such that \(\mathfrak{u}_{2}^{2}\sim\mathfrak{w}_{2}.\) Clearly, \(|\mathfrak{S}_{\mathfrak{B}}(\mathfrak{w}_{2})|=1\) and \(\mathfrak{u}_{2}^{2}= \mathfrak{w}_{1}+\mathfrak{v}_{3}+\cdots+\mathfrak{v}_{n}.\) Therefore \(\mathfrak{u}_{k}^{3}= \mathfrak{w}_{1}+\mathfrak{v}_{3}+\cdots+\mathfrak{v}_{k-1}+\mathfrak{w}_{2}+\mathfrak{v}_{k+1}\) \(+\mathfrak{v}_{n},\) \(3\leq k\leq n\) are distinct \((n-3)\) member of \(\mathfrak{S}_{n-1}\) and \(\mathfrak{u}_{k}^{3}\nsim\mathfrak{w}_{1}, \mathfrak{u}_{k}^{3}\nsim\mathfrak{w}_{2}.\) If \(\mathfrak{u}_{k}^{3}\in\mathfrak{D}\) for all \(3\leq k\leq n,\) then \(|\mathfrak{D}|\geq n\) and we are done. Otherwise, there exists \(\mathfrak{u}_{k}^{3}\notin\mathfrak{D}.\) Without loss of generality we assume that \(\mathfrak{u}_{3}^{3}\notin\mathfrak{D}.\) Since \(\mathfrak{u}_{3}^{3}\notin\mathfrak{D}\) and \(\mathfrak{u}_{3}^{3}\nsim\mathfrak{w}_{1}, \mathfrak{u}_{3}^{3}\nsim\mathfrak{w}_{2},\) there exists \(\mathfrak{w}_{3}\in\mathfrak{S}_{1}\cap\mathfrak{D}\) such that \(\mathfrak{w}_{3}\sim\mathfrak{u}_{3}^{3}.\) Clearly, \(|\mathfrak{S}_{\mathfrak{B}}\mathfrak{w}_{3})|=1\) and \(\mathfrak{u}_{3}^{3}= \mathfrak{w}_{1}+\mathfrak{w}_{2} +\mathfrak{v}_{4}+\cdots+\mathfrak{v}_{n}.\) Therefore \(\mathfrak{u}_{l}^{4}= \mathfrak{w}_{1}+\mathfrak{w}_{2}+\mathfrak{v}_{4}+\cdots+\mathfrak{v}_{l-1}\) \(+\mathfrak{w}_{3}+\mathfrak{v}_{l+1}+\mathfrak{v}_{n},\) \(4\leq l\leq n\) are distinct \((n-4)\) member of \(\mathfrak{S}_{n-1}\) and \(\mathfrak{u}_{l}^{4}\nsim\mathfrak{w}_{1},\) \(\mathfrak{u}_{l}^{4}\nsim\mathfrak{w}_{2}.\) \(\mathfrak{u}_{l}^{4}\nsim\mathfrak{w}_{3}.\) If \(\mathfrak{u}_{k}^{4}\in\mathfrak{D}\) for all \(4\leq k\leq n,\) then \(|\mathfrak{D}|\geq n\) and we are done. Otherwise, there exists \(\mathfrak{u}_{k}^{4}\notin\mathfrak{D}.\) Without loss of generality we assume that \(\mathfrak{u}_{4}^{4}\notin\mathfrak{D}.\) Since \(\mathfrak{u}_{4}^{4}\notin\mathfrak{D}\) and \(\mathfrak{u}_{4}^{4}\nsim\mathfrak{w}_{1}, \mathfrak{u}_{4}^{4}\nsim\mathfrak{w}_{2},\mathfrak{u}_{4}^{4}\nsim\mathfrak{w}_{3},\) there exists \(\mathfrak{w}_{4}\in\mathfrak{S}_{1}\cap\mathfrak{D}\) such that \(\mathfrak{w}_{4}\sim\mathfrak{u}_{4}^{4}.\) Clearly, \(|\mathfrak{S}_{\mathfrak{B}}(\mathfrak{w}_{4})|=1\) and \(\mathfrak{u}_{4}^{4}= \mathfrak{w}_{1}+\mathfrak{w}_{2}+\mathfrak{w}_{3}+\mathfrak{v}_{5}\cdots+\mathfrak{v}_{n}.\) Continuing in the similar way, there exist at least \(n\) distinct members \(\mathfrak{w}_{1},\mathfrak{w}_{2},\cdots,\mathfrak{w}_{n}\) in \(\mathfrak{D}\) and the lemma follows. ◻
Theorem 9. If \(\mathbb{V}\) is a \(n\)-dimensional vector space over a field \(\mathbb{F},\) then \(\gamma(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V}))=n.\)
Proof. Suppose that \(\mathfrak{B}=\{\mathfrak{v}_{1},\mathfrak{v}_{2},\dots,\mathfrak{v}_{n}\}\) is a basis of \(\mathbb{V}.\) Let \(\mathfrak{u}\) be an arbitrary vertex of \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V}).\) Now we show that either \(\mathfrak{u}\in\mathfrak{B}\) or \(\mathfrak{u}\sim\mathfrak{v}_{j}\) for some \(1\leq j\leq n.\) Assume that \(\mathfrak{u}\notin\mathfrak{B}\) and \(\mathfrak{u}\nsim\mathfrak{v}_{j}\) for all \(1\leq j\leq n.\) Then \(\mathfrak{S}_{\mathfrak{B}}(\mathfrak{u})\cap\mathfrak{S}_{\mathfrak{B}}(\mathfrak{v}_{j})\neq\emptyset\) for all \(1\leq j\leq n\) and \(\{v_{1},v_{2},\cdots,v_{n}\}\subseteq\mathfrak{S}_{\mathfrak{B}}(\mathfrak{u}),\) i.e., \(\mathfrak{S}_{\mathfrak{B}}(\mathfrak{u})=\mathfrak{B},\) which is a contradiction. Thus either \(\mathfrak{u}\in\mathfrak{B}\) or \(\mathfrak{u}\sim\mathfrak{v}_{j}\) for some \(1\leq j\leq n\) and \(\mathfrak{B}\) is a domination set for \(\mathfrak{I}^{n}(\mathbb{V}).\) For minimal dominating set \(\mathfrak{B}_{j}=\mathfrak{D}\setminus\{\mathfrak{u}_{j}\}\) and \(\mathfrak{u}_{j}= \mathfrak{v}_{1}+\mathfrak{v}_{2}+\cdots+\mathfrak{v}_{j-1}+\mathfrak{v}_{j+1}+\cdots+\mathfrak{v}_{n}\in V(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V}))\) \(\mathfrak{S}_{\mathfrak{B}}(\mathfrak{u}_{j})\cap\mathfrak{S}_{\mathfrak{B}}(\mathfrak{v}_{j})\neq\emptyset\) for all \(\mathfrak{v}_{i}\in\mathfrak{B}_{j},\) i.e., \(\mathfrak{v}_{i}\nsim\mathfrak{u}_{j}\) for all \(\mathfrak{v}_{i}\in\mathfrak{B}_{j}\) and \(\mathfrak{v}_{i}\notin\mathfrak{B}_{j}.\) Thus \(\mathfrak{B}\) is a minimum dominating set of \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V})\) and by Lemma 3, we get the required result. ◻
In this section, we study some basic properties of \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V}),\) when the order of the base field \(\mathbb{F}\) is finite i.e., \(\mathbb{F}=\mathbb{F}_{q}\). Moreover, we find order of \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V})\) and degree of vertex of \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V}).\)
Theorem 10. Let \(\mathbb{V}\) be a \(n\)-dimensional vector space over a field \(\mathbb{F}_{q}.\) Then order of \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V})\) is \(q^{n}-(q-1)^{n}-1.\)
Proof. Suppose that \(\mathfrak{B}\) is a basis of \(n\)-dimensional vector space \(\mathbb{V}\) over a field \(\mathbb{F}_{q}.\) Note that \(V(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V}))=\) \(\mathfrak{B}_{\mathbb{V}}=\{v\in\mathbb{V}~|~ 1\leq|\mathfrak{S}_{\mathfrak{B}}(v)|\leq n-1\}\) and the number of ways choosing \(u\in\mathbb{V}\) such that \(|\mathfrak{S}_{\mathfrak{B}}(v)|=n\) is \((q-1)^{n}.\) Therefore the order of \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V})\) is \(q^{n}-(q-1)^{n}-1.\) ◻
Theorem 11. Let \(\mathbb{V}\) be a \(n\)-dimensional vector space over a field \(\mathbb{F}_{q}.\) If \(v\) is a vertex in \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V})\) such that \(|\mathfrak{S}_{\mathfrak{B}}(v)|=k,\) then \[deg(v)=q^{n-k}-1.\]
Proof. Let \(\mathfrak{B}=\{v_{1},v_{2},\cdots,v_{n}\}\) be a basis of \(n\)-dimensional vector space \(\mathbb{V}\) over a field \(\mathbb{F}_{q}\) and \(w\in V(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V}))\) such that \(|\mathfrak{S}_{\mathfrak{B}}(w)|=k.\) For \(deg(w),\) we find the total number of vertices \(u_{i}\) of \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V})\) such that \(\mathfrak{S}_{\mathfrak{B}}(w)\cap\mathfrak{S}_{\mathfrak{B}}(u_{i})=\emptyset.\) For this without loss of generality, we may assume that \(\mathfrak{S}_{\mathfrak{B}}(w)=\{v_{1},v_{2},\cdots,v_{k}\}=\mathfrak{B}_{k}.\) If \(u\in V(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V}))\) such that \(u=\alpha_{1}v_{1}+\alpha_{2}v_{2}+\cdots+\alpha_{n}v_{n}\) and \(u\sim w,\) then \(\mathfrak{S}_{\mathfrak{B}}(w)\cap\mathfrak{S}_{\mathfrak{B}}(u)=\emptyset,\) i.e., \(\alpha_{i}=0\) for all \(i=1,2,\cdots,k.\) Thus the set \(\mathfrak{B}^{\ast}\) of all \(u_{i}\in V(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V}))\) such that \(u_{i}=\alpha_{1}v_{1}+\alpha_{2}v_{2}+\cdots+\alpha_{n}v_{n}\) and \(\alpha_{j}=0\) for \(1\leq j\leq k\) and \(j\neq 0\) for some \(k+1\leq j\leq n\) has \(|\mathfrak{B}^{\ast}|=q^{n-k}-1\) elements. Therefore the \(deg(w)= q^{n-k}-1.\) ◻
Corollary 3. Let \(\mathbb{V}\) be a \(n\)-dimensional vector space over a field \(\mathbb{F}_{q}.\) Then the following statements hold:
In this paper, we have introduced a component intersection graph \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V})\) of a finite dimensional vector space \(\mathbb{V}\) and investigated various inter-relationships between \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V})\) (as a graph) and \(\mathbb{V}\) (as a vector space). The main aim of this analysis is to study the basic properties of connectedness, diameter, clique, and chromatic number of \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V})\). As an area of further research, one can look into the structure of automorphism group, independent number and genus of \(\mathfrak{I}^{\mathfrak{B}}(\mathbb{V})\) in case of finite field.
The authors are indebted to the referee for his/her useful suggestions critical comments.
The author declares no conflict of interests.