Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-19T03:30:19.558Z Has data issue: false hasContentIssue false

Degrees of Vertices in a Friendship Graph

Published online by Cambridge University Press:  20 November 2018

Anton Kotzig*
Affiliation:
Centre de Recherches Mathématiques, Université de Montréal, Québec, Canada
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

A friendship graph is a graph in which every two distinct vertices have exactly one common adjacent vertex (called a neighbour). Finite friendship graphs have been characterized by Erdós, Rényi and Sós [2]: Each finite friendship graph Fn which consists of n edge disjoint triangles such that all n>1 triangles have one vertex in common (F1 is a triangle i.e. the complete graph with three vertices). Thus Fn has 2n+1 vertices, 2n of them being of degree two and the remaining one (the common vertex of n triangles if n>1) being of degree 2n.

Information

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 1975