k-Intersection Graph of a Finite Set

Document Type: Original Scientific Paper


1 Department of Pure Mathematics, Ferdowsi University of Mashhad, Mashhad, I. R. Iran

2 Department of Pure Mathematics and The Center of Excellence in Analysis on Algebraic Structures, Ferdowsi University of Mashhad, Mashhad, I. R. Iran

3 Department of Pure Mathematics, Ferdowsi University of Mashhad, International Campus Mashhad, I. R. Iran



For any nonempty set Ω and k-subset Λ, the k-intersection graph, denoted by Γm(Ω,Λ), is an undirected simple graph whose vertices are all m-subsets of Ω and two distinct vertices A and B are adjacent if and only if A∩B ⊈ Λ. In this paper, we determine diameter, girth, some numerical invariants and planarity, Hamiltonian and perfect matching of these graphs. finally we investigate their adjacency matrices.


[1] R. B. Bapat, Graphs and Matrices, Springer-Verlag, London, 2010.
[2] J. Bosák, The graphs of semigroups, Proc. Symposium Smolenice, Prague
(1964) 119–125.
[3] B. Csákány and G. Pollák, The graph of subgroups of a finite group,
Czechoslovak Math. J. 19 (1969) 241–247.
[4] I. Chakrabarty, S. Ghosh, T. K. Mukherjee and M. K. Sen, Intersection graphs
of ideals of ring, Discrete Math. 309 (2009) 5381–5392.
[5] L. E. Dickson, History of the Theory of Numbers, Chelsea, 1952.
[6] I. Fabrici and T. Madaras, The structure of 1-planar graphs, Discrete Math.
307 (2007) 854–865.

[7] C. Godsil and G. F. Royle, Algebraic Graph Theory, Springer, 2001.
[8] V. P. Korzhik, Minimal non-1-planar graphs, Discrete Math. 308 (2008) 1319–
[9] B. Zelinka, Intersection graphs of finite abelian groups, Czechoslovak Math.
J. 25(100) (1975) 171–174.

Volume 4, Issue 2
Special Issue: Spectral Graph Theory and Mathematical Chemistry with Connection to Computer Science
Autumn 2019
Pages 305-317