Extension of strongly regular graphs

MaRDI QIDQ1010654zbMATH OpenFDO

Authors Ralucca Gera, J. Shen

Publication date 7 April 2009

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/129722, http://www.emis.de/journals/EJC/Volume_15/Abstracts/v15i1n3.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

common friendfriend of everybodyfriendship theoremstrongly regular graph

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Association schemes, strongly regular graphs (05E30)

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.

Recommendations

• On a generalization of the friendship theorem
• scientific article; zbMATH DE number 6930592
• The Friendship Theorem
• scientific article; zbMATH DE number 540110
• The Friendship Theorem

Cited in

(5)

• The maximum spectral radius of C₄-free graphs of given order and size
• On extended connectivity indices
• On strongly k-extendable graphs
• On the extension of connected irregular (λ,μ)-graphs
• Minimum 2-percolating sets in 2-connected, diameter 2 graphs

This page was built for publication: Extension of strongly regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1010654)