The friendship problem on graphs

Mertzios, G.B.; Unger, W.

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
• Public URL: https://durham-repository.worktribe.com/output/1405566
• 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/