Article ID Journal Published Year Pages File Type
419296 Discrete Applied Mathematics 2015 7 Pages PDF
Abstract

For integers s≥8s≥8 and s+1≤n≤⌊25(s−1)8⌋, we determine the exact value of the function ex(n;{C3,…,Cs})ex(n;{C3,…,Cs}), that represents the maximum number of edges in a {C3,…,Cs}{C3,…,Cs}-free graph of order nn. This result was already known when 3≤s≤73≤s≤7. To do that, for 1≤k≤51≤k≤5, we provide a family of graphs  Hsk such that e(Hsk)−n(Hsk)=k and with the property that Hsk reaches girth  s+1s+1 with the minimum number of vertices. Also, we determine an infinity family of solutions of the problem ex(n;{C3,…,Cs})=n+6ex(n;{C3,…,Cs})=n+6.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,