A friendship graph is a graph in which every two distinct vertices have exactly one common neighbor. All finite friendship graphs are known, each of them consists of triangles having a common vertex. We extend friendship graphs to two-graphs, a two-graph being an ordered pair G = (G0, G1) of edge-disjoint graphs G0 and G1 on the same vertex-set V(G0) =V(G1). One may think that the edges of G are colored with colors 0 and 1. In a friendship two-graph, every unordered pair of distinct vertices u, v is connected by a unique bicolored 2-path. Friendship two-graphs are solutions to the matrix equation AB + BA = J - I, where A and B are n*n symmetric 0-1 matrices of the same dimension, J is an n*n matrix with every entry being 1, and I is the identity n*n matrix.
We show that there are no finite friendship two-graph with minimum vertex degree at most two. However, we construct an infinite such graph, and the construction can be extended to an infinite family. Also, we find a finite friendship two-graph, and conjecture that it is unique.
DIMACS Home Page