Extension of strongly regular graphs
type: Item
instance of: scholarly article
title: Extension of strongly regular graphs
zbMATH Open document ID: 1158.05342
author: Ralucca Gera
author: J. Shen
published in: The Electronic Journal of Combinatorics
publication date: 2009-04-07T00:00:00Z
full work available at URL: https://eudml.org/doc/129722
full work available at URL: v15i1n3.html
review text: 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.
Mathematics Subject Classification ID: 05E30
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 5540865
zbMATH Keywords: strongly regular graph
zbMATH Keywords: friendship theorem
zbMATH Keywords: common friend
zbMATH Keywords: friend of everybody
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 5540865