PIMS Postdoctoral Fellow Seminar

Wed., Feb. 8, 2023 11:30 a.m.

Speaker: Mahsa N. Shirazi, University of Manitoba

Title: Extensions of the Friendship Theorem

Registration in advance and details at: https://www.pims.math.ca/scientific-event/230208-tppfsmns

Abstract:

For r ≥ 1, a graph has r-friendship property if every pair of vertices has exactly r common neighbours. The motivation for this definition is from the friendship theorem, which is on the graphs with 1-friendship property. The friendship theorem, first proved by Erdös, Rényi, and Sós in 1996, states that if G is a graph in which every pair of vertices has exactly one common neighbour, then G has a universal vertex v adjacent to all others, and the graph induced by V (G) \ {v} is a matching.

In this talk, we present a brief history of the problem, we study graphs with r-friendship property, where r ≥ 2. We show all such graphs are strongly regular. Furthermore, we prove that for any r ≥ 2, there are only finitely many graphs with r-friendship property. We provide some classes of strongly regular graphs with r-friendship property, and their connections to design theory. At the end, we discuss about some open problems and con- jectures on this topic.

This is an ongoing joint work with Karen Gunderson.