Traversibility of subspace based nonzero component graph of vector spaces over finite fields

Articles in Press

Document Type : Original paper

Authors

1 Department of Mathematics, University of Kashmir, Srinagar, India

2 Department of Mathematics, Nanjing University, Nanjing, China

Abstract

Let $\mathbb{V}$ be an $n$-dimensional vector space over a field $\mathcal{F}$ having basis $\mathcal{B}=\left\lbrace \alpha_1, \alpha_2, \dots, \alpha_n\right\rbrace $ and $W$ be an $m$ dimensional subspace of $\mathbb{V}$ with basis $\{\alpha_{w_1}, \alpha_{w_2},\dots, \alpha_{w_m}\}$, where $\alpha_{w_i}$ is some $\alpha_{j}\in \mathcal{B}$. The $subspace~based~nonzero~component~graph$, denoted by $\Gamma_W(\mathbb{V}_\alpha)=\left( V,E\right)$, of a finite dimensional vector space with respect to $W$ and $\mathcal{B}$ is defined as follows: $V=\mathbb{V}\setminus W$ and for $\mathbf{u},\mathbf{v}\in V$, there is an edge between $\mathbf{u}$ and $\mathbf{v}$ if and only if either $W_{\mathbf{u}}\subset W_{\mathbf{v}}$ or $W_{\mathbf{v}}\subset W_{\mathbf{w}}$, where $\mathbf{u}=u_1\alpha_1+u_2\alpha_2+\dots+u_k\alpha_k$, $1\leq k\leq n$ and $W_{\mathbf{u}}=\{\alpha_{w_1}, \alpha_{w_2},\dots, \alpha_{w_m}\}\cup \{\alpha_1, \alpha_2, \dots, \alpha_k\}$. In this paper, we determine the order, size and edge-connectivity of $\Gamma_W(\mathbb{V}_\alpha)$. We show that the graph $\Gamma_W(\mathbb{V}_\alpha)$ is Hamiltonian but not Eulerian. We also show that under some mild conditions, the graph $\Gamma_W(\mathbb{V}_\alpha)$ lies on a triangle. Finally, we determine the clique number and the chromatic number of $\Gamma_W(\mathbb{V}_\alpha)$.

Keywords

Main Subjects

References

[1] I. Beck, Coloring of commutative rings, J. Algebra 116 (1988), no. 1, 208–226. https://doi.org/10.1016/0021-8693(88)90202-5
[2] R.C. Brigham and R.D. Dutton, A compilation of relations between graph invariants, Networks 15 (1985), no. 1, 73–107. https://doi.org/10.1002/net.3230150108
[3] P.J. Cameron and S. Ghosh, The power graph of a finite group, Discrete Math. 311 (2011), no. 13, 1220–1222.
https://doi.org/10.1016/j.disc.2010.02.011
[4] I. Chakrabarty, S. Ghosh, T.K. Mukherjee, and M.K. Sen, Intersection graphs of ideals of rings, Discrete Math. 309 (2009), no. 17, 5381–5392. https://doi.org/10.1016/j.disc.2008.11.034
[5] I. Chakrabarty, S. Ghosh, and M.K. Sen, Undirected power graphs of semigroups, Semigroup Forum 78 (2009), 410–426. https://doi.org/10.1007/s00233-008-9132-y
[6] G. Chartrand and P. Zhang, Introduction to Graph Theory, Tata McGraw Hill, New Delhi, 2006.
[7] W. Chen, On vector spaces associated with a graph, SIAM J. Appl. Math. 20 (1971), no. 3, 526–529. https://doi.org/10.1137/0120054
[8] A. Das, Non-zero component graph of a finite dimensional vector space, Comm. Algebra 44 (2016), no. 9, 3918–3926.
[9] A. Das, Subspace inclusion graph of a vector space, Comm. Algebra 44 (2016), no. 11, 4724–4731. https://doi.org/10.1080/00927872.2015.1110588
[10] A. Das, Non-zero component union graph of a finite-dimensional vector space, Linear Multilinear Algebra 65 (2017), 1276–1287. https://doi.org/10.1080/03081087.2016.1234577
[11] A. Das, On nonzero component graph of a vector space over finite fields, J. Algebra Appl. 16 (2017), no. 1, 1750007.
https://doi.org/10.1142/S0219498817500074
[12] A. Das, On subspace inclusion graph of a vector space, Linear Multilinear Algebra 66 (2018), no. 3, 554–564. https://doi.org/10.1080/03081087.2017.1306016
[13] M.H. de Carvalho and C.H.C. Little, Vector spaces and the Petersen graph, The Electronic J. Comb. 15 (2008), no. 1, #R9. https://doi.org/10.37236/733
[14] F.R. DeMeyer, T. McKenzie, and K. Schneider, The zero-divisor graph of a commutative semigroup, Semigroup Forum 65 (2002), 206–214. https://doi.org/10.1007/s002330010128
[15] G.A. Dirac, Some theorems on abstract graphs, Proc. Lond. Math. Soc. S3-2 (1952), no. 1, 69–81. https://doi.org/10.1112/plms/s3-2.1.69
[16] R. Gould, Graphs and vector spaces, Studies Appl. Math. 37 (1958), 193–214. https://doi.org/10.1002/sapm1958371193
[17] N. Jafari Rad and S.H. Jafari, A note on the intersection graphs of subspaces of a vector space, Ars Combin. 125 (2016), 401–407.
[18] V. Manjula, Vector space of a graph, Int. J. Math. Computer Research 2 (2014), 2320–7167.
[19] J.A. Nash-Williams, Edge-disjoint Hamiltonian Circuits in Graphs with vertices of high valency, Studies in Pure Mathematics (L. Mirsky, ed.), Academic Press, 1971, pp. 157–183.
[20] S. Pirzada, An Introduction to Graph Theory, Universities Press, Orient BlackSwan, Hyderabad, 2012.
[21] S. Pirzada, B.A. Wani, and S. Al-Kaseasbeh, Subspace based nonzero component graph of a finite dimensional vector space, Asian-Eur. J. Math. 15 (2022), no. 12, 2250214. https://doi.org/10.1142/S179355712250214X
[22] J. Plesnik, Critical graphs of given diameter, Acta Fac. Rerum Natur. Univ. Comenian. Math. 30 (1975), 71–93.
[23] S.P. Redmond, The zero-divisor graph of a noncommutative ring, Int. J. Commut. Rings 1 (2002), no. 4, 203–211.
[24] S.P. Redmond, An ideal based zero divisor graph of a commutative ring, Comm. Algebra 31 (2003), no. 9, 4425–4443. https://doi.org/10.1081/AGB-120022801
[25] Y. Talebi, M.S. Esmaeilifar, and S. Azizpour, A kind of intersection graph of vector space, J. Discrete Math. Sci. Cryptography 12 (2009), no. 6, 681–689.
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 26 August 2026

Files

Share

How to cite

Statistics