Scholarlink

The class of graphs with diameter 2 and girth 5 is finite (up to isomorphism). What if the girth 5 assumption is relaxed? Apart from stars, are there infinitely 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, and potential Cayley-graph and probabilistic constructions. Alice Devillers and Gordon Royle: Research of AD supported by Australian Research Council Discovery Project DP200100080. Nina Kamčev: Supported by the Croatian Science Foundation under the project number HRZZ-IP-2022–10-5116 (FANAP). Ian Wanless and David R. Wood: Research supported by the Australian Research Council.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Triangle-Free Graphs with Diameter 2

  • 章节

  • 发表日期：

    2025年

查看全文
  • Alice Devillers,
  • Nina Kamčev,
  • Brendan D. McKay,
  • Padraig Ó. Catháin,
  • Gordon Royle,
  • Geertrui Van de Voorde,
  • Ian M. Wanless,
  • David R. Wood

摘要

The class of graphs with diameter 2 and girth 5 is finite (up to isomorphism). What if the girth 5 assumption is relaxed? Apart from stars, are there infinitely 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, and potential Cayley-graph and probabilistic constructions. Alice Devillers and Gordon Royle: Research of AD supported by Australian Research Council Discovery Project DP200100080. Nina Kamčev: Supported by the Croatian Science Foundation under the project number HRZZ-IP-2022–10-5116 (FANAP). Ian Wanless and David R. Wood: Research supported by the Australian Research Council.