1
$\begingroup$

My name is Balchandar Reddy. I am a research scholar and am currently working on graph algorithms. I am looking to find a 4-regular graph that does not have small cycles. For example, I want to generate a 4-regular graph of size $O(k^c)$ that does not have any cycles of size $k$ or less ($k$ and $c$ are some positive integers, and $c$ is considerably small). I have thought of a cycle of size $O(k^c)$ to start with, and I can't quite figure out the other type of adjacency between the vertices (as all the vertices need to have another two vertices adjacent to them to make the graph 4-regular).

$\endgroup$
3
  • $\begingroup$ is $c$ any constant? $\endgroup$ May 2, 2023 at 17:30
  • $\begingroup$ you probably want to learn about (r,g)-cages $\endgroup$
    – JimN
    May 3, 2023 at 5:13
  • 1
    $\begingroup$ c must be a function of k? Are you sure? Then c is not a constant, and normally it should not be denoted with c, and that should be mentioned in the question. Please don't leave clarifications in the comments. Instead, revise the question so it reads well for someone who encounters it for the first time. Please ask only one question. I don't know what is meant by the 6-regular/3-regular question, but that should be asked separately, not tacked onto this question. I encourage you to edit your post to improve it. Thank you! $\endgroup$
    – D.W.
    May 3, 2023 at 5:29

1 Answer 1

2
$\begingroup$

When you say you want a graph without cycles of size $k$ (or less), you are asking for a graph with girth $k+1$. When restricting your interest to 4-regular graphs, since you are asking for an upper bound on the size of your graph, you would be interested in an $(r,g)$-cage, which is a $r$-regular graph of girth $g$ with as few vertices as possible.

In your case, you are asking about $(4,k+1)$-cages, and it seems you are asking if such things exist. It is known that $(r,g)$-cages exist for every $r \geq 2$ and $g \geq 3$. See: https://en.wikipedia.org/wiki/Cage_(graph_theory)

For example, the Robertson Graph:

enter image description here

is 4-regular and contains no cycles of size 4 or less and it is the smallest such graph with just 19 vertices.

See also: https://mathworld.wolfram.com/CageGraph.html for asymptotic upper and lower bounds for general $(r,g)$-cage sizes.

$\endgroup$
2
  • $\begingroup$ In my case, the upper bound on the number of vertices is exponential in $k$, which is not what i wanted. I need the graph size to be a polynomial function of $k$. $\endgroup$ May 3, 2023 at 6:54
  • 3
    $\begingroup$ @BalchandarReddy, it looks like there is an exponential lower bound, based on equation (1). Doesn't that answer your question? $\endgroup$
    – D.W.
    May 3, 2023 at 7:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.