Extension of Strongly Regular Graphs

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 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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Feb 11, 2008
Accession Number
ADA479816

Entities

People

  • Jian Shen
  • Ralucca Gera

Organizations

  • Naval Postgraduate School

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Applied Mathematics
  • Classification
  • Eigenvalues
  • Friendship
  • Information Operations
  • Literature
  • Mathematics
  • Schools

Fields of Study

  • Mathematics

Readers

  • Asian Economic Studies
  • Graph Algorithms and Convex Optimization.
  • Strategic Security Studies