Extremal even-cycle-free subgraphs of the complete transposition graphs

作者：

Highlights：

• We obtain the upper bounds for the number of edges in even-cycle-free subgraphs of the complete transposition graphs, which are a family of bipartite and arctransitive graphs.

• A family of new auxiliary graphs related to the complete transposition graphs are constructed and used in order to obtain the upper bounds.

• A new Ramsey-type result for the complete transposition graphs is obtained.

摘要

•We obtain the upper bounds for the number of edges in even-cycle-free subgraphs of the complete transposition graphs, which are a family of bipartite and arctransitive graphs.•A family of new auxiliary graphs related to the complete transposition graphs are constructed and used in order to obtain the upper bounds.•A new Ramsey-type result for the complete transposition graphs is obtained.

论文关键词：Turán number,Even-cycle-free subgraph,Complete transposition graph,Ramsey-type problem

论文评审过程：Received 26 November 2020, Revised 12 March 2021, Accepted 19 March 2021, Available online 13 April 2021, Version of Record 13 April 2021.

论文官网地址：https://doi.org/10.1016/j.amc.2021.126223