Publication details for Dr George MertziosMertzios, G.B. & Unger, W. (2016). The friendship problem on graphs. Journal of Multiple-Valued Logic and Soft Computing 27(2-3): 275-285.
- Publication type: Journal Article
- ISSN/ISBN: 1542-3980, 1542-3999
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
Author(s) from Durham
In this paper we provide a purely combinatorial proof of the Friendship Theorem, which has been first proven by P. Erdős et al. by using also algebraic methods. Moreover, we generalize this theorem in a natural way, assuming that every pair of nodes occupies l ≥ 2 common neighbors. We prove that every graph, which satisfies this generalized l-friendship condition, is a regular graph.