The friendship problem on graphs

Mertzios, G.B.; Unger, W.

The friendship problem on graphs

Mertzios, G.B.; Unger, W.

Authors

Dr George Mertzios george.mertzios@durham.ac.uk
Associate Professor

W. Unger

Abstract

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.

Citation

Mertzios, G., & Unger, W. (2016). The friendship problem on graphs. Journal of Multiple-Valued Logic and Soft Computing, 27(2-3), 275-285

Journal Article Type	Article
Acceptance Date	Oct 3, 2014
Online Publication Date	Aug 1, 2016
Publication Date	Aug 1, 2016
Deposit Date	Sep 1, 2016
Publicly Available Date	Jul 1, 2017
Journal	Journal of Multiple-Valued Logic and Soft Computing
Print ISSN	1542-3980
Electronic ISSN	1542-3999
Publisher	Old City Publishing
Peer Reviewed	Peer Reviewed
Volume	27
Issue	2-3
Pages	275-285
Publisher URL	http://www.oldcitypublishing.com/journals/mvlsc-home/mvlsc-issue-contents/mvlsc-volume-27-number-2-3-2016/mvlsc-27-2-3-p-275-285/