On a generalization of the friendship theorem

Mohammad Hailat

Discussiones Mathematicae Graph Theory (2012)

  • Volume: 32, Issue: 1, page 153-160
  • ISSN: 2083-5892

Abstract

top
The Friendship Theorem states that if any two people, of a group of at least three people, have exactly one friend in common, then there is always a person who is everybody's friend. In this paper, we generalize the Friendship Theorem to the case that in a group of at least three people, if every two friends have one or two common friends and every pair of strangers have exactly one friend then there exist one person who is friend to everybody in the group. In particular, we show that the graph corresponding to this problem is of type G = K₁∨(sK₂ + tK₃), where s and t are non-negative integers and Kₘ is the complete graph on m vertices.

How to cite

top

Mohammad Hailat. "On a generalization of the friendship theorem." Discussiones Mathematicae Graph Theory 32.1 (2012): 153-160. <http://eudml.org/doc/271073>.

@article{MohammadHailat2012,
abstract = {The Friendship Theorem states that if any two people, of a group of at least three people, have exactly one friend in common, then there is always a person who is everybody's friend. In this paper, we generalize the Friendship Theorem to the case that in a group of at least three people, if every two friends have one or two common friends and every pair of strangers have exactly one friend then there exist one person who is friend to everybody in the group. In particular, we show that the graph corresponding to this problem is of type G = K₁∨(sK₂ + tK₃), where s and t are non-negative integers and Kₘ is the complete graph on m vertices.},
author = {Mohammad Hailat},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {(λ,μ)-graph; Friendship Theorem; -graph; friendship theorem},
language = {eng},
number = {1},
pages = {153-160},
title = {On a generalization of the friendship theorem},
url = {http://eudml.org/doc/271073},
volume = {32},
year = {2012},
}

TY - JOUR
AU - Mohammad Hailat
TI - On a generalization of the friendship theorem
JO - Discussiones Mathematicae Graph Theory
PY - 2012
VL - 32
IS - 1
SP - 153
EP - 160
AB - The Friendship Theorem states that if any two people, of a group of at least three people, have exactly one friend in common, then there is always a person who is everybody's friend. In this paper, we generalize the Friendship Theorem to the case that in a group of at least three people, if every two friends have one or two common friends and every pair of strangers have exactly one friend then there exist one person who is friend to everybody in the group. In particular, we show that the graph corresponding to this problem is of type G = K₁∨(sK₂ + tK₃), where s and t are non-negative integers and Kₘ is the complete graph on m vertices.
LA - eng
KW - (λ,μ)-graph; Friendship Theorem; -graph; friendship theorem
UR - http://eudml.org/doc/271073
ER -

References

top
  1. [1] J. Bondy, Kotzig's Conjecture on generalized friendship graphs - a survey, Annals of Discrete Mathematics 27 (1985) 351-366. Zbl0573.05036
  2. [2] P. Erdös, A. Rènyi and V. Sós, On a problem of graph theory, Studia Sci. Math 1 (1966) 215-235. Zbl0144.23302
  3. [3] R. Gera and J. Shen, Extensions of strongly regular graphs, Electronic J. Combin. 15 (2008) # N3 1-5. Zbl1158.05342
  4. [4] J. Hammersley, The friendship theorem and the love problem, in: Surveys in Combinatorics, London Math. Soc., Lecture Notes 82 (Cambridge University Press, Cambridge, 1989) 127-140. 
  5. [5] N. Limaye, D. Sarvate, P. Stanika and P. Young, Regular and strongly regular planar graphs, J. Combin. Math. Combin. Compt 54 (2005) 111-127. Zbl1084.05020
  6. [6] J. Longyear and T. Parsons, The friendship theorem, Indag. Math. 34 (1972) 257-262. Zbl0243.05006
  7. [7] E. van Dam and W. Haemers, Graphs with constant μ and μ̅, Discrete Math. 182 (1998) 293-307, doi: 10.1016/S0012-365X(97)00150-7. Zbl0901.05068
  8. [8] H. Wilf, The friendship theorem in combinatorial mathematics and its applications, Proc. Conf. Oxford, 1969 (Academic Press: London and New York, 1971) 307-309. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.