1
$\begingroup$

I am trying to solve:

Given $n, k$, find maximum $m$ such that there exists a graph on $n$ nodes, $m$ edges such that every edge is part of a minimal $k$-cycle.

I only care about the asymptotic value of $m$, and I don't care about log factors (so the answer will look like $m = \tilde O(n^c)$). This problem has applications to certain distance approximation algorithms in computer science.

Thanks!

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ What do you mean by a minimal $k$-cycle? $\endgroup$
    – Seva
    Commented Feb 11, 2014 at 9:13
  • $\begingroup$ I think a graph of girth k on n vertices is wanted. Also, for large k, any two such cycles have at most two links between them. Here a link is an edge off of both cycles that has a vertex on each cycle. $\endgroup$
    – The Masked Avenger
    Commented Feb 11, 2014 at 16:33
  • $\begingroup$ By minimal $k$-cycle, I mean that no proper subset of the $k$ vertices forms a cycle. Another way of phrasing this question is "every edge belongs to a cycle, and the graph has girth $k$." $\endgroup$
    – GMB
    Commented Feb 11, 2014 at 21:17
  • $\begingroup$ @GMB These are not equivalent definitions! One can construct a graph, such that every edge is in a chordless k-cycle (no proper subset of these $k$ vertices form a cycle) but the graph contains a triangle. $\endgroup$
    – Daniel Soltész
    Commented Feb 11, 2014 at 21:51
  • $\begingroup$ I think it is also intended that for every edge, that edge belongs to a cycle, and the minimum of the girths of all cycles containing that edge is k, and this holds for all edges. $\endgroup$
    – The Masked Avenger
    Commented Feb 11, 2014 at 23:14

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ This construction leads to a recurrence for a nice lower bound. Namely, view each k cycle as a point and each pair of links as an edge, and use a graph of girth k/2 and l points as a guide for linking the cycles. I would look over someone else's analysis using this idea with attribution. $\endgroup$
    – The Masked Avenger
    Commented Feb 11, 2014 at 17:09
  • $\begingroup$ If you want to do more research, girth and cages are search terms I suggest. The Petersen graph should clue you in on why k=5 and 6 will require a different analysis. $\endgroup$
    – The Masked Avenger
    Commented Feb 11, 2014 at 19:19
  • $\begingroup$ If by minimal cycles the OP means just induced ones, then the $k=4$ case has a better example, namely $K_{2,2,2,\dots,2}$ (or $K_{2,2,\dots,2,3}$ if $n$ is odd). OTOH, if a graph of girth $k$ is needed, then the optimality of a complete bipartite graph is confirmed by Turan's theorem. $\endgroup$
    – Ilya Bogdanov
    Commented Sep 17, 2016 at 17:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .