Extension of strongly regular graphs

Ralucca Gera ; Jian Shen

The electronic journal of combinatorics, Tome 15 (2008)

Résumé

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.

Détail

DOI : 10.37236/878

Classification : 05E30, 05C75
Mots-clés : strongly regular graph, friendship theorem, common friend, friend of everybody