首页 | 本学科首页   官方微博 | 高级检索  
     


Graphs with maximum size and lower bounded girth
Authors:E. Abajo A. Diá  nez
Affiliation:
  • Departamento de Matemática Aplicada I, Universidad de Sevilla, Sevilla, Spain
  • Abstract:For integers n≥4 and νn+1, let ex(ν;{C3,…,Cn}) denote the maximum number of edges in a graph of order ν and girth at least n+1. The {C3,…,Cn}-free graphs with order ν and size ex(ν;{C3,…,Cn}) are called extremal graphs and denoted by EX(ν;{C3,…,Cn}). We prove that given an integer k≥0, for each n≥2log2(k+2) there exist extremal graphs with ν vertices, ν+k edges and minimum degree 1 or 2. Considering this idea we construct four infinite families of extremal graphs. We also see that minimal (r;g)-cages are the exclusive elements in EX(ν0(r,g);{C3,…,Cg−1}).
    Keywords:Extremal function   Extremal graphs   Forbidden cycles   Girth   Cages
    本文献已被 ScienceDirect 等数据库收录!
    设为首页 | 免责声明 | 关于勤云 | 加入收藏

    Copyright©北京勤云科技发展有限公司  京ICP备09084417号