Logo image
Examples of diameter-2 graphs with no triangle or K2,t
Journal article   Peer reviewed

Examples of diameter-2 graphs with no triangle or K2,t

Sean Eberhard, Vladislav Taranchuk and Craig Timmons
The Australasian journal of combinatorics, Vol.94, pp.235-242
02/01/2026

Abstract

Mathematics Physical Sciences Science & Technology
For each t >= 1 let W-t denote the class of graphs other than stars that have diameter 2 and contain neither a triangle nor a K-2,K-t. The famous Hoffman-Singleton Theorem implies that W-2 is finite. Recently Wood suggested the study of W-t for t > 2 and conjectured that W-t is finite for all t >= 2. In this note we show that (1) W-3 is infinite, (2) W-5 contains infinitely many regular graphs, and (3) W-7 contains infinitely many Cayley graphs. Our W-3 and W-5 examples are based on so-called crooked graphs, first constructed by de Caen, Mathon, and Moorhouse. Our W-7 examples are Cayley graphs with vertex set F-p(2) for prime p equivalent to 11 (mod 12). We also highlight the surprising fact that crooked graphs themselves provide an infinite family of graphs which imply that ex(n, {C-3, K-2,K-3}) = (1/root 2 + o(1))n(3/2) for an infinite, albeit sparse, set of n's.

Metrics

1 Record Views

Details

Logo image