Here is a rough analysis to start things off. k=3 corresponds to a complete graph, and k=4 to a complete bipartite graph with the vertex set split as evenly as possible. (I don't see an easy proof of optimality, but I doubt one can cram more edges in. See Relationship between triangle free graphs and their minimum degree for why I think this.) k=5 and 6 seem a little tricky, so in what follows assume k large enough to pull the arguments through.

For any path outside of a given k cycle which connects two vertices of that cycle, that path has to be as long as the longest of the two paths in the cycle that connect those two vertices, otherwise the graph has girth less than k. Further, for k large (possibly k at least 5, and certainly at least 10) two k cycles have at most two links between them, and at most one if they share an edge. Here a link is an edge off of both cycles that shares a different vertex with each cycle.

Since the goal is to maximize the number of edges, I recommend partitioning the graph into disjoint cycles and adding as many links as possible. I suspect this will give a good upper bound when k*k is at least n. If l is n/k, this gives n + l^2 as a rough upper bound on the number of edges. The actual bound is likely smaller as linking all pairs of cycles may end up reducing the girth.

Here is a rough analysis to start things off. k=3 corresponds to a complete graph, and k=4 to a complete bipartite graph with the vertex set split as evenly as possible. (I don't see an easy proof of optimality, but I doubt one can cram more edges in. See Relationship between triangle free graphs and their minimum degree for why I think this.) k=5 and 6 seem a little tricky, so in what follows assume k large enough to pull the arguments through.

For any path outside of a given k cycle which connects two vertices of that cycle, that path has to be as long as the longest of the two paths in the cycle that connect those two vertices, otherwise the graph has girth less than k. Further, for k large (possibly k at least 5, and certainly at least 10) two k cycles have at most two links between them, and at most one if they share an edge. Here a link is an edge off of both cycles that shares a different vertex with each cycle.

Since the goal is to maximize the number of edges, I recommend partitioning the graph into disjoint cycles and adding as many links as possible. I suspect this will give a good upper bound when k*k is at least n. If l is n/k, this gives n + l^2 as a rough upper bound on the number of edges. The actual bound is likely smaller as linking all pairs of cycles may end up reducing the girth.

Here is a rough analysis to start things off. k=3 corresponds to a complete graph, and k=4 to a complete bipartite graph with the vertex set split as evenly as possible. (I don't see an easy proof of optimality, but I doubt one can cram more edges in. See Relationship between triangle free graphs and their minimum degree for why I think this.) k=5 and 6 seem a little tricky, so in what follows assume k large enough to pull the arguments through.

For any path outside of a given k cycle which connects two vertices of that cycle, that path has to be as long as the longest of the two paths in the cycle that connect those two vertices, otherwise the graph has girth less than k. Further, for k large (possibly k at least 5, and certainly at least 10) two k cycles have at most two links between them, and at most one if they share an edge. Here a link is an edge off of both cycles that shares a different vertex with each cycle.

Since the goal is to maximize the number of edges, I recommend partitioning the graph into disjoont cycles and adding as many links as possible. I suspect this will give a good upper bound when k*k is at least n. If l is n/k, this gives n + l^2 as a rough upper bound on the number of edges. The actual bound is likely smaller as linking all pairs of cycles may end up reducing the girth.

Here is a rough analysis to start things off. k=3 corresponds to a complete graph, and k=4 to a complete bipartite graph with the vertex set split as evenly as possible. (I don't see an easy proof of optimality, but I doubt one can cram more edges in. See Relationship between triangle free graphs and their minimum degree for why I think this.) k=5 and 6 seem a little tricky, so in what follows assume k large enough to pull the arguments through.

For any path outside of a given k cycle which connects two vertices of that cycle, that path has to be as long as the longest of the two paths in the cycle that connect those two vertices, otherwise the graph has girth less than k. Further, for k large (possibly k at least 5, and certainly at least 10) two k cycles have at most two links between them, and at most one if they share an edge. Here a link is an edge off of both cycles that shares a different vertex with each cycle.

Since the goal is to maximize the number of edges, I recommend partitioning the graph into disjoint cycles and adding as many links as possible. I suspect this will give a good upper bound when k*k is at least n. If l is n/k, this gives n + l^2 as a rough upper bound on the number of edges. The actual bound is likely smaller as linking all pairs of cycles may end up reducing the girth.