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).
$\begingroup$
$\endgroup$
3
-
$\begingroup$ is $c$ any constant? $\endgroup$– Inuyasha YagamiCommented May 2, 2023 at 17:30
-
$\begingroup$ you probably want to learn about (r,g)-cages $\endgroup$– JimNCommented 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. ♦Commented May 3, 2023 at 5:29
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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:
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.
-
$\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$ Commented 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. ♦Commented May 3, 2023 at 7:28