Abstract:
A Deza graph with parameters (v,k,b,a) is a k-regular graph with v vertices where any two vertices have either a or b common neighbors. We describe strict Deza graphs that do not contain K1,3 among their induced subgraphs and are unions of closed neighborhoods of two nonadjacent vertices. The latter condition means that there are two nonadjacent vertices such that any other vertex is adjacent to at least one of them.
This publication is cited in the following 2 articles:
V. V. Kabanov, A. V. Mityanina, “Claw-free strictly Deza graphs”, Sib. elektron. matem. izv., 14 (2017), 367–387
S. V. Goryainov, G. S. Isakova, V. V. Kabanov, N. V. Maslova, L. V. Shalaginov, “On Deza graphs with disconnected second neighborhood of a vertex”, Proc. Steklov Inst. Math. (Suppl.), 297, suppl. 1 (2017), 97–107