Volume 20, Issue 1 (4-2025)
IJMSI 2025, 20(1): 125-130 |
Back to browse issues page
Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
Saravanan M, Kathiresan K. On the Independence Graph of Hamming Graph. IJMSI 2025; 20 (1) :125-130
URL: http://ijmsi.ir/article-1-1865-en.html
URL: http://ijmsi.ir/article-1-1865-en.html
Abstract:
The independence graph Ind(G) of a graph G is the graph with vertices as maximum independent sets of G and two vertices are adjacent, if and only if the corresponding maximum independent sets are disjoint. In this work, we find the independence graph of Cartesian product of d copies of complete graphs Kq, which is known as the Hamming graph H(d, q). Greenwell and Lovasz [7] found that the independence number of direct product of d copies of Kq as qd−1. We prove that the independence number of Hamming graph H(d, q), which is cartesian product of d copies of Kq, is also qd−1. As an application of our findings, we find answers for rook problem in higher dimensional square chess board.
Type of Study: Research paper |
Subject:
General
References
1. G. Abay-Asmerom, R. Hammack, C. E. Larson, D. T. Taylor, Notes on the Independence Number in the Cartesian Product of Graphs, Discuss. Math. Graph Theory, 31, (2011), 25-35. [DOI:10.7151/dmgt.1527]
2. F. Alayont, N. Krzywonos, Rook Polynomials in Three and Higher Dimensions, Involve, 6(1), (2013), 35-52. [DOI:10.2140/involve.2013.6.35]
3. B. Bresar, B. Zmazek, On the Independence Graph of a Graph, Discrete Math., 272, (2003), 263-268. [DOI:10.1016/S0012-365X(03)00194-8]
4. A. E. Brouwer, A. M. Cohen, A. Neumair, Distance Regular Graphs, Springer - verlag, NewYork, 1989. [DOI:10.1007/978-3-642-74341-2]
5. Hon-Chan Chen, Ting-Yem Ho, The Rook Problem on Saw-toothed Chessboards, Appl. Math. Lett., 21, (2008), 1234-1237 [DOI:10.1016/j.aml.2007.12.003]
6. T. Derikvand, M. R. Oboudi, On the Number of Maximum Independent Sets of Graphs, Trans. Comb., 3(1), (2014), 29-36
7. D. Greenwell, L. Lovasz, Applications of Product Colouring, Acta Math. Hungar., 25(3-4), (1974), 335-340. [DOI:10.1007/BF01886093]
8. P. Hell, X. Yu, H. Zhou, Independence Ratios of Graph Powers, Discrete Math., 127, (1994), 213-220. [DOI:10.1016/0012-365X(92)00480-F]
9. W. Imrich, S. Klavzar, Product Graphs, Wiley-Interscience, NewYork, 2000.
10. M. J. Jou, G. J. Chang, The Number of Maximum Independent Sets in Graphs, Taiwan. J. Math., 4(4), (2000), 685-695. [DOI:10.11650/twjm/1500407302]
11. I. Kaplansky, J. Riordan, The Problem of the Rooks and Its Applications, Duke Math. J., 13(2), (1946), 259-268. [DOI:10.1215/S0012-7094-46-01324-5]
12. S. Klavzar, Some New Bounds and Exact Results on the Independence Number of Cartesian Product Graphs, Ars Combin., 74, (2005), 173-186.
13. A. Varvak, Rook Numbers and the Normal Ordering Problem, J. Combin. Theory Ser. A, 112, (2005), 292-307. [DOI:10.1016/j.jcta.2005.07.012]
14. D. B. West, Introduction to Graph Theory, Prentice Hall, Upper Saddle River, New Jersey, 2000.
15. X. Zhu, On the Bounds for the Ultimate Independence Ratio of a Graph, Discrete Math., 156, (1996), 229-236. [DOI:10.1016/0012-365X(93)E0171-Y]
| Rights and permissions | |
 |
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. |
