Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419296 | Discrete Applied Mathematics | 2015 | 7 Pages |
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
E. Abajo, A. Diánez,