ON $(△,1)$-GRAPHS

Abstract

Let $G=(V,E)$ be a graph and $\lambda$ a non-negative integer. A graph $G$ is called a $(\lambda ,1)$-{\em graph} if $(c0)$ $G$ is neither a complete graph no an edge-empty graph, $(c1)$ every edge in $G$ belongs to exactly $\lambda$ triangles, and $(c2)$ every two non-adjacent vertices in $G$ are the end-vertices of exactly one two-edge path in $G$. It turns out that there are infinitely many feasible 4-tuples $(v,d,\lambda ,1)$ with $\lambda \ge 1$. On the other hand (and this is our main result), there is no $(v,d,\lambda ,1)$-graphs with $\lambda \ge 1$. As a byproduct, we obtain a generalization of the classical Friendship Theorem.

11 pages, 8 figures major revision is needed