There are finitely many graphs with diameter $2$ and girth 5. What if the girth 5 assumption is relaxed? Apart from stars, are there finitely many triangle-free graphs with diameter $2$ and no K2,3 subgraph? This question is related to the existence of triangle-free strongly regular graphs, but allowing for a range of co-degrees gives the question a more extremal flavour. More generally, for fixed s and t, are there infinitely many twin-free triangle-free Ks,t-free graphs with diameter 2? This paper presents partial results regarding these questions, including computational results, potential Cayley-graph and probabilistic constructions.
No takes yet. Share an insight, caveat, or question.
Devillers et al. (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: