Suppose I have a strongly $k-regular$ graph $G$, of size $v$, where every vertex is $N>0$ $n-cycles$, for $at least$ one value of $n$ that divides $v$. Can we cut edges from $G$ in such a way that we're left with a graph of $v/n$ disconnected components, where each component is an $n-cycle$ for at least one value of $n$?

I've made some edits to the original questions to improve conditions and clarity

| cite | improve this question | | | | |
  • $\begingroup$ "same number of n-cycles" had better be nonzero . . . $\endgroup$ – Noam D. Elkies Mar 4 '16 at 4:12
  • $\begingroup$ It's not that $n \geq 1$ (that's automatic for a cycle, even $n \geq 3$ assuming no loops or multiple edges), but that there exists some nonzero $N$ such that each vertex is in $N$ cycles of length $n$. $\endgroup$ – Noam D. Elkies Mar 4 '16 at 4:16
  • $\begingroup$ A simple counterexample is to take a complete graph or other vertex-transitive graph so that the number of vertices is not divisible by $n$. $\endgroup$ – Douglas Zare Mar 4 '16 at 4:31
  • $\begingroup$ What if we add the condition that n must divide v, then is there a way to guarantee it's possible? $\endgroup$ – Kristaps John Balodis Mar 4 '16 at 5:13
  • $\begingroup$ That's not enough. There are still easy counterexamples. $\endgroup$ – Douglas Zare Mar 4 '16 at 5:25

It is not true.

Take a non-bipartite cubic graph with no 3-cycles. Let $G$ be its line-graph. Then every vertex of $G$ lies on exactly two 3-cycles but there is no collection of disjoint 3-cycles covering every vertex.

| cite | improve this answer | | | | |
  • $\begingroup$ Ok, but that just shows you can't do it for 3-cycles. So for example, the Peterson graph is non-bipartite, cubic, and contains no 3-cycles. However there is a collection of disjoint 5-cycles that cover every vertex. $\endgroup$ – Kristaps John Balodis Mar 4 '16 at 5:23
  • $\begingroup$ But, as your question is phrased, the number $n$ is fixed --- so this is really a counterexample... $\endgroup$ – Ilya Bogdanov Mar 4 '16 at 10:55
  • $\begingroup$ @Kristaps : One counterexample is enough to disprove a conjecture. I think it would be a miracle if this conjecture is true for any particular cycle length. In fact much the same construction works. Take an $n$-regular non-bipartite graph of high girth, subdivide each edge, delete the original vertices, connect the (new) neighbours of each deleted vertex in an $n$-cycle. $\endgroup$ – Brendan McKay Mar 4 '16 at 11:00
  • $\begingroup$ I've made an edit now, so the question asks that if we know every vertex is in the same non-zero number of at least one length of cycle, then can we show that there is at least one n that divides n that allows us to get the construction. $\endgroup$ – Kristaps John Balodis Mar 4 '16 at 14:58

I use some non-standard terms here:

My answer will not address your theorem specifically, but instead I want to ask: when does there exist a $n$-uniformly cyclic vertex subdecomposition of a graph?

First we will define a vertex decomposition of a graph. This is a term that is in relation to the regular decomposition of graphs:

A decomposition $\mathfrak{G} := \{ (v_i \subset V,s_i \subset E) \}$ of a graph $G=(V,E)$ is a family of edge induced subgraphs such that $$ \bigcup^{n} s_i = E$$ and the $s_i$ are pairwise disjoint.

A vertex decomposition $\mathfrak{V} := \{ (v_i \subset V,s_i \subset E) \}$ of a graph $G=(V,E)$ is a family of vertex induced subgraphs such that $$ \bigcup^{n} v_i = V$$ and the $v_i$ are pairwise disjoint. (I c

A vertex subdecomposition $\mathfrak{S}$ of $\mathfrak{V}$ is a family of subgraphs of $\mathfrak{V}$ such that $$ \bigcup^{n}_{\mathfrak{S}} v_i = V $$.

We are looking for specific vertex subdecompositions of graphs. Specifically, we want to know when is every element in $\mathfrak{S}$ a cycle of degree $n$. We call this a $n$-uniformly cyclic vertex subdecomposition because the cycles are of uniform degree $n$.

An important consequence of the fact that the vertex decomposition is a family of vertex induced subgraphs that do not share vertices is that any vertex decomposition will be a disjoint graph, as we desire.

Your conjuncture is equivalent to the conjuncture that: There exist an $n$-uniformly cyclic vertex subdecomposition $\mathfrak{S}$ of a graph $G$ if $G$ is $k-regular$, $n|v$ (where $v = |V|$), and every vertex of the graph is in $N>0$ $n$-cycles.

We know that if there exists a vertex decomposition $\mathfrak{V}$ of $G$ where every $v_i$ has equal cardinality and if for every $g_i \in\mathfrak{V}$ there is an $n$-cycle with is a spanning subgraph $g_i$ then there exist an $n$-uniformly cyclic vertex subdecomposition $\mathfrak{S}$ of a graph $G$. Therefore it is sufficient to show that a given graph $G$ has a vertex decomposition $\mathfrak{V}$ of $G$ where every $v_i$ has equal cardinality and if for every $g_i \in\mathfrak{V}$ there is an $n$-cycle with is a spanning subgraph $g_i$.

The first condition is easily met if $n|v$ since we can construct a vertex decomposition where all $g_i$ have equal carnality by simply partitioning the vertices into $\frac{v}{n}$ partitions, where each one will have $n$ vertices. Further, there are $\binom{v}{n}$ such partitions.

Now we must figure out when one of those partitions has the property that every $g_i$ has a spanning subgraph which is an $n$-cycle. This is equivalent to the subgraph having a hamoltonian cycle since they all have degree n. This is also equivalent to the graph $G$ being $2$-factorable, and every $2$-factor having cardinality $n$. Since a graph can be $2$-factored if and only if it is a $K$-regular graph, where $K$ is even, then we know that the following condition must also be true: $G$ is $K$-regular, where $K$ is even.

So, we have a few necessary conditions, but no sufficient conditions:

If there exists $n$-uniformly cyclic vertex subdecomposition of $G$, then $n|v$, and $G$ is $K$-regular.

| cite | improve this answer | | | | |
  • $\begingroup$ It looks like disjoint unions of complete graphs can satisfy your extra condition. $\endgroup$ – Douglas Zare Mar 4 '16 at 13:49
  • $\begingroup$ I deleted comments where I had miscalculated the number of cycles through a vertex in a complete graph. Anyway, here is a possible source of counterexamples: Take a disjoint union of two complete graphs on $v/2$ vertices so that $n$ is not a factor of $v/2$ but $n$ is a factor of $v$. For example, take $v=2004$ and $n=4$. There are many $4$-cycles through each vertex, $1001 \times 1000 \times 999$ but since the connected components can't be decomposed into $4$-cycles, the whole graph can't. I doubt connectedness alone fixes this, but the question is too much of a moving target now. $\endgroup$ – Douglas Zare Mar 4 '16 at 23:19
  • $\begingroup$ That is an interesting case, and I think that perhaps the regularity and the connectedness might remedy it, but I honestly have no clue. How do you calculate the number of four cycles through each vertex? $\endgroup$ – Juan Sebastian Lozano Mar 4 '16 at 23:25

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