On even-cycle-free subgraphs of the doubled Johnson graphs

作者：

Highlights：

• We obtain the upper bounds for the number of edges in even cycle free subgraphs of the doubled Johnson graphs, which are well studied subgraphs of the famous hypercube graphs.

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

• A new Ramsey type result for doubled Odd graphs is obtained.

摘要

•We obtain the upper bounds for the number of edges in even cycle free subgraphs of the doubled Johnson graphs, which are well studied subgraphs of the famous hypercube graphs.•A family of new auxiliary graphs related to doubled Johnson graphs are constructed and used in order to obtain the upper bounds.•A new Ramsey type result for doubled Odd graphs is obtained.

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

论文评审过程：Received 9 June 2020, Revised 23 October 2020, Accepted 25 October 2020, Available online 17 March 2021, Version of Record 17 March 2021.

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