Necessary and sufficient conditions for quasi-strongly regularity of Graph Product

Tuan Minh Do, Hoa Dinh Vu


A $k$-regular graph ($k\ge 1$) with $n$ vertices is called a quasi-strongly regular graph with parameter $\lambda$ ($\lambda\in\NN$) if any two adjacent vertices have exactly $\lambda$ neighbors in common.A graph product is a binary operation on graphs. In this paper we prove some necessary and sufficient conditions for Decartes Product, Tensor Product, Lexicographical product and Strong product to be quasi-strongly regular.


quasi-strongly regular graph; product graph

Full Text:



Azarija, J. & Tilen Marc, {it There is no (75,32,10,16) strongly regular graph}, arXiv:1509.05933, Dec. 2015.

Azarija, J. & Tilen Marc,

There is no (95,40,12,20) strongly regular graph, arXiv:1603.02032, Mar. 2016.

Behbahani, M. & Clement Lam,

{it Strongly regular graphs with non-trivial automorphisms}, Discr. Math. 311, p. 132-144, 2011.

Bondarenko, Andriy V. & Danylo V. Radchenko,

{it On a family of strongly regular graphs with $lambda = 1$}, arXiv:1201.0383, Feb. 2012.

Bondarenko, A. V., Prymak, A. & Radchenko, D.

{it Non-existence of (76,30,8,14) strongly regular graph and some structural tools}, arXiv:1410.6748, Oct. 2014.

Bondarenko, A. V., Mellit, A., Prymak, A. , Radchenko, D. & Viazovska, M. {it There is no strongly regular graph with parameters (460,153,32,60)}, arXiv:1509.06286, Sep. 2015.

Beineke, L.W. and Wilson, R. J. (Eds.) {it Topics in Algebraic Graph Theory}, Newyork; Cambridge University, p.104, 2004.

Goldberg, F. {it On quasi-strongly regular graphs}, Linear and Multilinear Algebra , Volume 54 - Issue 6,

p. 437-451, 2006.

Vizing, V.G. {it The Cartesian product of graphs}, Vyc. Sis. 9, 30-43, (1963).

Wilfried, I. & Klavar, Sandi. {it Product Graphs: Structure and Recognition}. Wiley. ISBN 0-471-37039-8{{inconsistent citations}}, 2000.


DOI: Display counter: Abstract : 172 views. PDF : 137 views.

Journal of Computer Science and Cybernetics ISSN: 1813-9663

Published by Vietnam Academy of Science and Technology