Extension of strongly regular graphs
Summary: The Friendship Theorem states that if any two people in a party have exactly one common friend, then there exists a politician who is a friend of everybody. In this paper, we generalize the Friendship Theorem. Let \(\lambda\) be any nonnegative integer and \(\mu\) be any positive integer. Suppose each pair of friends have exactly \(\lambda\) common friends and each pair of strangers have exactly \(\mu\) common friends in a party. The corresponding graph is a generalization of strongly regular graphs obtained by relaxing the regularity property on vertex degrees. We prove that either everyone has exactly the same number of friends or there exists a politician who is a friend of everybody. As an immediate consequence, this implies a recent conjecture by Limaye et.al.
scientific article; zbMATH DE number 5540865