On some properties of vector space based graphs

Abstract

In this paper, we study some problems related to subspace inclusion graph $\mathcal{I}n(\mathbb{V})$ and subspace sum graph $\mathcal{G}(\mathbb{V})$ of a finite-dimensional vector space $\mathbb{V}$. Namely, we prove that $\mathcal{I}n(\mathbb{V})$ is a Cayley graph as well as Hamiltonian when the dimension of $\mathbb{V}$ is 3. We also find the exact value of independence number of $\mathcal{G}(\mathbb{V})$ when the dimension of $\mathbb{V}$ is odd. The above two problems were left open in previous works in the literature. Moreover, we prove that the determining numbers of $\mathcal{I}n(\mathbb{V})$ and $\mathcal{G}(\mathbb{V})$ are bounded above by 6. Finally, we study some forbidden subgraphs of these two graphs.

Keywords:

• Maximal intersecting family
• Hamiltonian
• base

2008 MSC::

• 05C25
• 05C45
• 05E18

Disclosure statement

No potential conflict of interest was reported by the author(s).

Disclosure Statement

No conflict of interest was reported by the author(s).

Additional information

Funding

The first author acknowledges the Isaac Newton Institute for Mathematical Sciences, Cambridge, for support and hospitality during the programme Groups, representations and applications: new perspectives (supported by EPSRC grant no. EP/R014604/1), where he held a Simons Fellowship. The second author acknowledges the funding of Department of Science and Technology grant SR/FST/MS-I/2019/41, Govt. of India. The third author acknowledges HRI Post-Doctoral Fellowship and SERB-National Post-Doctoral Fellowship (File No. PDF/2021/ 001899) and profusely thanks Science and Engineering Research Board for this funding. The work is support by Department of Science and Technology, Government of India (FIST programme).