ON THE DIAMETER AND CONNECTIVITY OF BIPARTITE KNESER TYPE-k GRAPHS | ||
| Journal of Algebraic Systems | ||
| دوره 13، شماره 3، بهمن 2025، صفحه 81-94 اصل مقاله (164.84 K) | ||
| نوع مقاله: Original Manuscript | ||
| شناسه دیجیتال (DOI): 10.22044/jas.2024.13249.1733 | ||
| نویسندگان | ||
| Sreeja Ponnamma* 1؛ Sreekumar Kesavan pillai G.2؛ Manilal Karunakaran1 | ||
| 1Department of Mathematics, University College, University of Kerala, Thiruvananthapuram, India. | ||
| 2Department of Mathematics, University of Kerala, Thiruvananthapuram, India. | ||
| چکیده | ||
| Let $n\in \mathbb{Z}^{+}$, $n>1$, and $k$ be an integer, $1\leq k \leq n-1$. The graph $H_{T}(n,k)$ is defined as a graph with vertex set $V$, as all non-empty subsets of $\mathcal{S}_n=\{1,2,3,\ldots,n\}$. It is a bipartite graph with partition $(V_{1},V_{2})$, in which $V_{1}$ contains the $k$-element subsets of $\mathcal{S}_n$ and $V_{2}$ contains $i$-element subsets of $\mathcal{S}_n$, for $1\le i \le n, \ i\neq k$. An edge exists between a vertex $U\in V_{1}$ and a vertex $W \in V_{2}$ if either $U\subset W$ or $W \subset U$. In this paper, we established formulae for the number of edges, vertex connectivity, edge connectivity and degree polynomial. Then, we analysed the clique number and diameter of $H_T(n,k)$. We also verified that the graphs $H_{T}(n,k)$ and $H_{T}(n,n-k)$ are isomorphic. Degree-based topological indices such as the general Randic connectivity index, the first general Zagreb index and the general sum connectivity index are also computed. Also, we proved that the line graph of $H_T(n,k)$ is not a bipartite graph. | ||
| کلیدواژهها | ||
| vertex connectivity؛ clique number؛ diameter؛ the general Randic connectivity index؛ the first general Zagreb index | ||
| مراجع | ||
|
1. A. R. Ashrafi and A. Ghalavand, On edge-degree based invariants of graphs, Asian-Eur. J. Math., 15(9) (2022), Article ID: 2250161.
2. J. Bamberg, A. Devillers, M. Ioppolo and C. E. Praeger, Codes and designs in Johnson graphs from symplectic actions on quadratic forms, (2022), arXiv:2202.06237.
3. I. N. Cangul, A. Saleh, A. Alqesmah and H. Alashwali, Entire Wiener index of graphs, Commun. Comb. Optim., 7(2) (2022), 227–245.
4. S. R. Canoy Jr. and M. A. Labendia, Polynomial representation and degree sequence of a graph, International Journal of Mathematical Analysis, 8 (2014), 1445–1455.
5. G. Chartrand and P. Zhang, Introduction to Graph Theory, McGraw Hill Education, 2013.
6. Y. Chen and Y. Wang, On the diameter of generalized Kneser graphs, Discrete Math., 308(18) (2008), 4276–4279.
7. T. Chowdhury and A. Pramanik, LDPC code construction from bipartite Kneser graphs, Proceedings of the 2nd International Conference on Communication, Devices and Computing, Springer, (2020), 1-12.
8. C. Godsil and G. Royle, Algebraic Graph Theory, International series of monographs on Physics, Springer 2013.
9. I. Gutman, B. Furtula and V. Katanic, Randic index and information, AKCE Int. J. Graphs Comb., 15(3) (2018), 307–312.
10. R. Kogani and S. M. Mirafzal, On determining the distance spectrum of a class of distance integral graphs, J. Algebr. Syst., 10(2) (2023), 299–308.
11. A. E. Kupriyanov, A. V. Bobu and A. M. Raigorodskii, A generalization of Kneser graphs, Math. Notes, 107(3) (2020), 392–403.
12. S. M. Mirafzal, The automorphism group of the bipartite Kneser graph, ProceedingsMathematical Sciences, 129 (2018), 1–8.
13. J. Plesnik and S. Znam, On equality of edge-connectivity and minimum degree of a graph, Arch. Math. (Brno), 25(1) (1989), 19–25.
14. N. Saeed, K. Long, Z. S. Mufti, H. Sajid and A. Rehman, Degree-based topological indices of Boron B12, Journal of Chemistry, 2021(6) (2021), 1–6.
15. K. G. Sreekumar, K. Manilal and J. K. Rajan, 2S3 transformation for dyadic fractions in the interval (0, 1), Commun. Comb. Optim., 8(2) (2023), 411–421.
16. K. G. Sreekumar, P. Ramesh Kumar and K. Manilal, Automorphism groups of bipartite Kneser type-k graphs, Asian-Eur. J. Math., 16(3) (2023), Article ID: 2350047.
17. M. Valencia-Pabon and J. C. Vera, On the diameter of Kneser graphs, Discrete Math., 305(1) (2005), 383–385
| ||
|
آمار تعداد مشاهده مقاله: 297 تعداد دریافت فایل اصل مقاله: 138 |
||