Deza graphs: A generalization of strongly regular graphs. (English) Zbl 0959.05122

Summary: We consider the following generalization of strongly regular graphs. A graph \(G\) is a Deza graph if it is regular and the number of common neighbors of two distinct vertices takes on one of two values (not necessarily depending on the adjacency of the two vertices). We introduce several ways to construct Deza graphs, and develop some basic theory. We also list all diameter two Deza graphs which are not strongly regular and have at most 13 vertices.


05E30 Association schemes, strongly regular graphs
Full Text: DOI


[1] and Algebraic combinatorics I: Association schemes, Benjamin-Cummings Lecture Note Series 58, Benjamin/Cummings, London, 1984.
[2] Algebraic graph theory, Cambridge University Press, Cambridge, 1993.
[3] and Distance-regular graphs, Springer-Verlag, New York, 1989.
[4] and ?Strongly regular graphs and partial geometries,? Enumeration and design, Proceedings of the Silver Jubilee Conference at the University of Waterloo, and (Editors), Academic Press, Toronto, 1984, pp. 85-122.
[5] and ?Partial lambda-geometries of small nexus,? Combinatorial mathematics, optimal designs and their applications, (Editor), Fort Collins, 1978, Ann Discrete Math 6, North Holland, 1980.
[6] Cigic, Glasnik Matematicki 31 pp 47– (1996)
[7] Graphs with few eigenvalues?An interplay between combinatorics and algebra, PhD thesis, Tilburg University, Tilburg, 1996.
[8] and ?The ridge graph of the metric polytope and some relatives,? Polytopes: Abstract, convex and computational, et al. (Editors), NATO ASI Series, Kluwer Academic, 1994, pp. 359-372. · Zbl 0809.52017
[9] Gropp, Discrete Math 125 pp 201– (1994)
[10] ?Dual seidel switching,? Papers dedicated to and (Editors), EUT Report 84-WSK-03, Eindhoven University of Technology, The Netherlands, 1984, pp. 183-190.
[11] Graph theory, Addison-Wesley, Reading, 1969.
[12] Hemmeter, European J Combin
[13] Higman, European J Combin 9 pp 411– (1988) · Zbl 0659.05033
[14] Hughes, Lecture Notes in Math. 893 pp 43– (1981)
[15] ?The interval function of a graph,? PhD Thesis, Free University Amsterdam, 1980, MC Tract 132, CWI, Amsterdam, 1980.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.