Extension of strongly regular graphs
Loading...
Authors
Gera, Ralucca
Shen, J.
Subjects
Advisors
Date of Issue
2008
Date
Publisher
Language
Abstract
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 A be any nonnegative integer and p be any positive integer. Suppose each pair of friends have exactly A common friends and each pair of strangers have exactly p 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.
Type
Article
Description
The article of record as published may be located at http://www.combinatorics.org/ojs/index.php/eljc/article/view/v15i1n3
The Electronic Journal of Combinatorics 15(1) (2008), #N3
The Electronic Journal of Combinatorics 15(1) (2008), #N3
Series/Report No
Department
Applied Mathematics
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
Citation
Electronic Journal of Combinatorics / Volume 15, Issue 1
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.