2
$\begingroup$

My name is Balchandar Reddy. I am a research scholar and am currently working on graph algorithms. I am looking to find a 6-regular graph that does not have small 3-regular subgraphs. For example, I want to generate a 6-regular graph of size $poly(k)$ that does not have any 3-regular subgraphs of size $k$ or less ($k$ is some positive integer).

I have thought of a cycle of size $poly(n)$ to start with, and I am yet to figure out the other type of adjacency between the vertices (as all the vertices need to have another four vertices adjacent to them to make the graph 6-regular).

I have also considered having three sets of vertices, each of size $k^2$ and the adjacency is carefully defined between the sets such that no 3-regular subgraph of size at most $k$ is present. But, i can't quite prove it formally whether my graph does not have a 3-regular subgraph of size at most $k$.

Recently, I got to know about $(r,g)$-cages that will construct such kinds of graphs without having smaller cycles. Can we modify it in some way such that it works for 3-regular subgraphs as well?

$\endgroup$
1
  • 2
    $\begingroup$ This paper is relevant: sciencedirect.com/science/article/pii/0095895684900479 It shows that every 6-regular graph has a 3-regular subgraph. I'm not sure how many nodes are in the subgraph they construct, but it will give you a starting bound on the relationship between the size of the input graph and the size of the 3-regular subgraph you want to forbid. $\endgroup$
    – GMB
    May 3, 2023 at 17:26

1 Answer 1

8
$\begingroup$

6-regular Ramanujan graphs have girth (shortest cycle length) $\Omega(\log n)$, which means that their smallest 3-regular subgraphs do as well. However, the Moore bound on cages implies that every 3-regular subgraph has size at least exponential in its girth, which is therefore of the form $\Omega(n^c)$ for some $c$ with $0<c<1$. Turning this ratio around, if $k$ is the size of the smallest 3-regular subgraph in a 6-regular Ramanujan graph, the overall graph has size $O(k^{1/c})$, a polynomial.

$\endgroup$
3
  • $\begingroup$ That's not what I get when I plug in the girth of 6-regular LPS Ramanujan graphs into the Moore bound for 3-regular graphs. $\endgroup$ May 4, 2023 at 7:10
  • $\begingroup$ (Comment was in reply to a suggestion for what c is) $\endgroup$ May 8, 2023 at 5:07
  • $\begingroup$ I have the following questions on the Ramanujan graphs. 1) Can the construction of Ramanujan graphs be done in polynomial time? 2) Does the lower bound on the girth given also hold for bipartite Ramanujan graphs? 3) Can the construction of Bipartite Ramanujan graphs be done in polynomial time? $\endgroup$ May 24, 2023 at 9:47

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.