Prove that the connected circulant regular graphs of degree at least three contain all even cycles. The 2019 Stack Overflow Developer Survey Results Are In Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)a question about odd cycleCirculant Graph DefinitionProve that every minimal edge cut in a simple connected graph $G(V,E)$ is even, then $G(V,E)$ has no odd degree vertex.Prove that if G is a graph with no even cycles, then every cycle in G is an induced subgraph.Show that if any $k+1$ vertices of $k-$connected graph with at least 3 vertices span at least one-edge, then the graph is hamiltonian.Graph $G$ has k vertices of odd degree, prove there is $dfrack2$ non-closed trails that cover all the edges of the graph exactly once.$G$ is a simple undirected, regular, and planar graph with 9 vertices. Prove or disprove that $bar G$ must have a Hamiltonian cycle.Prove that a graph with at least one edge and all vertices of even degree must contain a cycle.Hamiltonian cubic graphs contain at least three hamilton cycles.let the girth of G is at least 2k. Prove that the diameter of Gis at least k.
Accepted by European university, rejected by all American ones I applied to? Possible reasons?
Why can I use a list index as an indexing variable in a for loop?
How do I design a circuit to convert a 100 mV and 50 Hz sine wave to a square wave?
Why doesn't shell automatically fix "useless use of cat"?
Is there a writing software that you can sort scenes like slides in PowerPoint?
Can a flute soloist sit?
"... to apply for a visa" or "... and applied for a visa"?
What can I do if neighbor is blocking my solar panels intentionally?
Simulating Exploding Dice
What to do when moving next to a bird sanctuary with a loosely-domesticated cat?
Is this wall load bearing? Blueprints and photos attached
Student Loan from years ago pops up and is taking my salary
Can the Right Ascension and Argument of Perigee of a spacecraft's orbit keep varying by themselves with time?
What other Star Trek series did the main TNG cast show up in?
Is 'stolen' appropriate word?
How did passengers keep warm on sail ships?
One-dimensional Japanese puzzle
Why can't devices on different VLANs, but on the same subnet, communicate?
How did the crowd guess the pentatonic scale in Bobby McFerrin's presentation?
How to politely respond to generic emails requesting a PhD/job in my lab? Without wasting too much time
Make it rain characters
How do spell lists change if the party levels up without taking a long rest?
Single author papers against my advisor's will?
Did the UK government pay "millions and millions of dollars" to try to snag Julian Assange?
Prove that the connected circulant regular graphs of degree at least three contain all even cycles.
The 2019 Stack Overflow Developer Survey Results Are In
Announcing the arrival of Valued Associate #679: Cesar Manara
Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)a question about odd cycleCirculant Graph DefinitionProve that every minimal edge cut in a simple connected graph $G(V,E)$ is even, then $G(V,E)$ has no odd degree vertex.Prove that if G is a graph with no even cycles, then every cycle in G is an induced subgraph.Show that if any $k+1$ vertices of $k-$connected graph with at least 3 vertices span at least one-edge, then the graph is hamiltonian.Graph $G$ has k vertices of odd degree, prove there is $dfrack2$ non-closed trails that cover all the edges of the graph exactly once.$G$ is a simple undirected, regular, and planar graph with 9 vertices. Prove or disprove that $bar G$ must have a Hamiltonian cycle.Prove that a graph with at least one edge and all vertices of even degree must contain a cycle.Hamiltonian cubic graphs contain at least three hamilton cycles.let the girth of G is at least 2k. Prove that the diameter of Gis at least k.
$begingroup$
This is the question I am trying to solve, but while researching about circulant graph I came across Paley's graph of order 13.
Now clearly when looking at this graph which is an example of circulant graph has a cycle of 13 length, which is odd, so we can disprove the above given statement.
There was also a proof I came across, which I could not gather much from, This is the link of the proof. In this they prove that it is true, for odd number of vertices in lemma 2.
I am very confused now, am I missing something, is there any other interpretation for this question, my interpretation is that if there is a cycle in the circulant graph, it must be of even length.
Any insights would be helpful.
graph-theory hamiltonian-path path-connected circulant-matrices
$endgroup$
add a comment |
$begingroup$
This is the question I am trying to solve, but while researching about circulant graph I came across Paley's graph of order 13.
Now clearly when looking at this graph which is an example of circulant graph has a cycle of 13 length, which is odd, so we can disprove the above given statement.
There was also a proof I came across, which I could not gather much from, This is the link of the proof. In this they prove that it is true, for odd number of vertices in lemma 2.
I am very confused now, am I missing something, is there any other interpretation for this question, my interpretation is that if there is a cycle in the circulant graph, it must be of even length.
Any insights would be helpful.
graph-theory hamiltonian-path path-connected circulant-matrices
$endgroup$
$begingroup$
So with further research, I understood that a circulant graph is edge-bipancyclic, which means that every edge lies in an even cycle, so could we maybe interpret it that way?
$endgroup$
– jackson jose
Mar 31 at 7:11
$begingroup$
Please could you clarify "contain all even cycles"? $K_4=Ci_4(1,2)$ is a connected circulant graph, has degree 3 and contains 3-cycles.
$endgroup$
– Rosie F
Mar 31 at 8:12
$begingroup$
@RosieF the question is answered, that "contains all even cycles" has been explained below.
$endgroup$
– jackson jose
Mar 31 at 17:36
add a comment |
$begingroup$
This is the question I am trying to solve, but while researching about circulant graph I came across Paley's graph of order 13.
Now clearly when looking at this graph which is an example of circulant graph has a cycle of 13 length, which is odd, so we can disprove the above given statement.
There was also a proof I came across, which I could not gather much from, This is the link of the proof. In this they prove that it is true, for odd number of vertices in lemma 2.
I am very confused now, am I missing something, is there any other interpretation for this question, my interpretation is that if there is a cycle in the circulant graph, it must be of even length.
Any insights would be helpful.
graph-theory hamiltonian-path path-connected circulant-matrices
$endgroup$
This is the question I am trying to solve, but while researching about circulant graph I came across Paley's graph of order 13.
Now clearly when looking at this graph which is an example of circulant graph has a cycle of 13 length, which is odd, so we can disprove the above given statement.
There was also a proof I came across, which I could not gather much from, This is the link of the proof. In this they prove that it is true, for odd number of vertices in lemma 2.
I am very confused now, am I missing something, is there any other interpretation for this question, my interpretation is that if there is a cycle in the circulant graph, it must be of even length.
Any insights would be helpful.
graph-theory hamiltonian-path path-connected circulant-matrices
graph-theory hamiltonian-path path-connected circulant-matrices
asked Mar 31 at 6:49
jackson josejackson jose
11
11
$begingroup$
So with further research, I understood that a circulant graph is edge-bipancyclic, which means that every edge lies in an even cycle, so could we maybe interpret it that way?
$endgroup$
– jackson jose
Mar 31 at 7:11
$begingroup$
Please could you clarify "contain all even cycles"? $K_4=Ci_4(1,2)$ is a connected circulant graph, has degree 3 and contains 3-cycles.
$endgroup$
– Rosie F
Mar 31 at 8:12
$begingroup$
@RosieF the question is answered, that "contains all even cycles" has been explained below.
$endgroup$
– jackson jose
Mar 31 at 17:36
add a comment |
$begingroup$
So with further research, I understood that a circulant graph is edge-bipancyclic, which means that every edge lies in an even cycle, so could we maybe interpret it that way?
$endgroup$
– jackson jose
Mar 31 at 7:11
$begingroup$
Please could you clarify "contain all even cycles"? $K_4=Ci_4(1,2)$ is a connected circulant graph, has degree 3 and contains 3-cycles.
$endgroup$
– Rosie F
Mar 31 at 8:12
$begingroup$
@RosieF the question is answered, that "contains all even cycles" has been explained below.
$endgroup$
– jackson jose
Mar 31 at 17:36
$begingroup$
So with further research, I understood that a circulant graph is edge-bipancyclic, which means that every edge lies in an even cycle, so could we maybe interpret it that way?
$endgroup$
– jackson jose
Mar 31 at 7:11
$begingroup$
So with further research, I understood that a circulant graph is edge-bipancyclic, which means that every edge lies in an even cycle, so could we maybe interpret it that way?
$endgroup$
– jackson jose
Mar 31 at 7:11
$begingroup$
Please could you clarify "contain all even cycles"? $K_4=Ci_4(1,2)$ is a connected circulant graph, has degree 3 and contains 3-cycles.
$endgroup$
– Rosie F
Mar 31 at 8:12
$begingroup$
Please could you clarify "contain all even cycles"? $K_4=Ci_4(1,2)$ is a connected circulant graph, has degree 3 and contains 3-cycles.
$endgroup$
– Rosie F
Mar 31 at 8:12
$begingroup$
@RosieF the question is answered, that "contains all even cycles" has been explained below.
$endgroup$
– jackson jose
Mar 31 at 17:36
$begingroup$
@RosieF the question is answered, that "contains all even cycles" has been explained below.
$endgroup$
– jackson jose
Mar 31 at 17:36
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The phrase "contains all even cycles" means that it contains every even cycle (obviously of length less than or equal to the circumference of the graph). On the other hand, "contains only even cycles" or "all cycles of the graph are even" would mean that it contains no odd cycles; that every cycle, if any, must be even.
In particular, look at the corollary to Theorem 1 in the paper you refer to: "Connected bipartite circulants contain all even and only even cycles" (emphasis mine). And in the next section, they discuss circulants containing cycles of all lengths.
$endgroup$
1
$begingroup$
Thanks, the part "all even cycles" confused me, I thought it meant all cycles are even, but that is not the case, now I understand. Thanks man.
$endgroup$
– jackson jose
Mar 31 at 17:24
$begingroup$
Can you please clear one more doubt I have? In the paper I referred, the lemma 1 used to prove theorem 1, it says in the first line, "clearly, a2 is odd", why is that so, why does a2 have to be odd?
$endgroup$
– jackson jose
Mar 31 at 17:49
$begingroup$
@jacksonjose In the statement of the lemma, it is assumed that "$a_2$ form[s] a Hamiltonian cycle", which means the value of the jump $a_2$ is such that $C = (1, 1 + a_2, 1 + 2a_2, ldots, 1 + (n - 1)a_2)$ (all $mod n$) is a cycle in the graph. It is also assumed that $n$ is even. This implies that $a_2$ must be odd – in fact $C$ is a cycle if and only if $gcd(a_2, n) = 1$. [In other words, $C$ forms a cycle if and only if $a_2$ is a generator in $(mathbb Z/nmathbb Z, +)$.]
$endgroup$
– M. Vinay
Apr 1 at 1:21
add a comment |
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3169118%2fprove-that-the-connected-circulant-regular-graphs-of-degree-at-least-three-conta%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The phrase "contains all even cycles" means that it contains every even cycle (obviously of length less than or equal to the circumference of the graph). On the other hand, "contains only even cycles" or "all cycles of the graph are even" would mean that it contains no odd cycles; that every cycle, if any, must be even.
In particular, look at the corollary to Theorem 1 in the paper you refer to: "Connected bipartite circulants contain all even and only even cycles" (emphasis mine). And in the next section, they discuss circulants containing cycles of all lengths.
$endgroup$
1
$begingroup$
Thanks, the part "all even cycles" confused me, I thought it meant all cycles are even, but that is not the case, now I understand. Thanks man.
$endgroup$
– jackson jose
Mar 31 at 17:24
$begingroup$
Can you please clear one more doubt I have? In the paper I referred, the lemma 1 used to prove theorem 1, it says in the first line, "clearly, a2 is odd", why is that so, why does a2 have to be odd?
$endgroup$
– jackson jose
Mar 31 at 17:49
$begingroup$
@jacksonjose In the statement of the lemma, it is assumed that "$a_2$ form[s] a Hamiltonian cycle", which means the value of the jump $a_2$ is such that $C = (1, 1 + a_2, 1 + 2a_2, ldots, 1 + (n - 1)a_2)$ (all $mod n$) is a cycle in the graph. It is also assumed that $n$ is even. This implies that $a_2$ must be odd – in fact $C$ is a cycle if and only if $gcd(a_2, n) = 1$. [In other words, $C$ forms a cycle if and only if $a_2$ is a generator in $(mathbb Z/nmathbb Z, +)$.]
$endgroup$
– M. Vinay
Apr 1 at 1:21
add a comment |
$begingroup$
The phrase "contains all even cycles" means that it contains every even cycle (obviously of length less than or equal to the circumference of the graph). On the other hand, "contains only even cycles" or "all cycles of the graph are even" would mean that it contains no odd cycles; that every cycle, if any, must be even.
In particular, look at the corollary to Theorem 1 in the paper you refer to: "Connected bipartite circulants contain all even and only even cycles" (emphasis mine). And in the next section, they discuss circulants containing cycles of all lengths.
$endgroup$
1
$begingroup$
Thanks, the part "all even cycles" confused me, I thought it meant all cycles are even, but that is not the case, now I understand. Thanks man.
$endgroup$
– jackson jose
Mar 31 at 17:24
$begingroup$
Can you please clear one more doubt I have? In the paper I referred, the lemma 1 used to prove theorem 1, it says in the first line, "clearly, a2 is odd", why is that so, why does a2 have to be odd?
$endgroup$
– jackson jose
Mar 31 at 17:49
$begingroup$
@jacksonjose In the statement of the lemma, it is assumed that "$a_2$ form[s] a Hamiltonian cycle", which means the value of the jump $a_2$ is such that $C = (1, 1 + a_2, 1 + 2a_2, ldots, 1 + (n - 1)a_2)$ (all $mod n$) is a cycle in the graph. It is also assumed that $n$ is even. This implies that $a_2$ must be odd – in fact $C$ is a cycle if and only if $gcd(a_2, n) = 1$. [In other words, $C$ forms a cycle if and only if $a_2$ is a generator in $(mathbb Z/nmathbb Z, +)$.]
$endgroup$
– M. Vinay
Apr 1 at 1:21
add a comment |
$begingroup$
The phrase "contains all even cycles" means that it contains every even cycle (obviously of length less than or equal to the circumference of the graph). On the other hand, "contains only even cycles" or "all cycles of the graph are even" would mean that it contains no odd cycles; that every cycle, if any, must be even.
In particular, look at the corollary to Theorem 1 in the paper you refer to: "Connected bipartite circulants contain all even and only even cycles" (emphasis mine). And in the next section, they discuss circulants containing cycles of all lengths.
$endgroup$
The phrase "contains all even cycles" means that it contains every even cycle (obviously of length less than or equal to the circumference of the graph). On the other hand, "contains only even cycles" or "all cycles of the graph are even" would mean that it contains no odd cycles; that every cycle, if any, must be even.
In particular, look at the corollary to Theorem 1 in the paper you refer to: "Connected bipartite circulants contain all even and only even cycles" (emphasis mine). And in the next section, they discuss circulants containing cycles of all lengths.
answered Mar 31 at 9:16
M. VinayM. Vinay
7,35822136
7,35822136
1
$begingroup$
Thanks, the part "all even cycles" confused me, I thought it meant all cycles are even, but that is not the case, now I understand. Thanks man.
$endgroup$
– jackson jose
Mar 31 at 17:24
$begingroup$
Can you please clear one more doubt I have? In the paper I referred, the lemma 1 used to prove theorem 1, it says in the first line, "clearly, a2 is odd", why is that so, why does a2 have to be odd?
$endgroup$
– jackson jose
Mar 31 at 17:49
$begingroup$
@jacksonjose In the statement of the lemma, it is assumed that "$a_2$ form[s] a Hamiltonian cycle", which means the value of the jump $a_2$ is such that $C = (1, 1 + a_2, 1 + 2a_2, ldots, 1 + (n - 1)a_2)$ (all $mod n$) is a cycle in the graph. It is also assumed that $n$ is even. This implies that $a_2$ must be odd – in fact $C$ is a cycle if and only if $gcd(a_2, n) = 1$. [In other words, $C$ forms a cycle if and only if $a_2$ is a generator in $(mathbb Z/nmathbb Z, +)$.]
$endgroup$
– M. Vinay
Apr 1 at 1:21
add a comment |
1
$begingroup$
Thanks, the part "all even cycles" confused me, I thought it meant all cycles are even, but that is not the case, now I understand. Thanks man.
$endgroup$
– jackson jose
Mar 31 at 17:24
$begingroup$
Can you please clear one more doubt I have? In the paper I referred, the lemma 1 used to prove theorem 1, it says in the first line, "clearly, a2 is odd", why is that so, why does a2 have to be odd?
$endgroup$
– jackson jose
Mar 31 at 17:49
$begingroup$
@jacksonjose In the statement of the lemma, it is assumed that "$a_2$ form[s] a Hamiltonian cycle", which means the value of the jump $a_2$ is such that $C = (1, 1 + a_2, 1 + 2a_2, ldots, 1 + (n - 1)a_2)$ (all $mod n$) is a cycle in the graph. It is also assumed that $n$ is even. This implies that $a_2$ must be odd – in fact $C$ is a cycle if and only if $gcd(a_2, n) = 1$. [In other words, $C$ forms a cycle if and only if $a_2$ is a generator in $(mathbb Z/nmathbb Z, +)$.]
$endgroup$
– M. Vinay
Apr 1 at 1:21
1
1
$begingroup$
Thanks, the part "all even cycles" confused me, I thought it meant all cycles are even, but that is not the case, now I understand. Thanks man.
$endgroup$
– jackson jose
Mar 31 at 17:24
$begingroup$
Thanks, the part "all even cycles" confused me, I thought it meant all cycles are even, but that is not the case, now I understand. Thanks man.
$endgroup$
– jackson jose
Mar 31 at 17:24
$begingroup$
Can you please clear one more doubt I have? In the paper I referred, the lemma 1 used to prove theorem 1, it says in the first line, "clearly, a2 is odd", why is that so, why does a2 have to be odd?
$endgroup$
– jackson jose
Mar 31 at 17:49
$begingroup$
Can you please clear one more doubt I have? In the paper I referred, the lemma 1 used to prove theorem 1, it says in the first line, "clearly, a2 is odd", why is that so, why does a2 have to be odd?
$endgroup$
– jackson jose
Mar 31 at 17:49
$begingroup$
@jacksonjose In the statement of the lemma, it is assumed that "$a_2$ form[s] a Hamiltonian cycle", which means the value of the jump $a_2$ is such that $C = (1, 1 + a_2, 1 + 2a_2, ldots, 1 + (n - 1)a_2)$ (all $mod n$) is a cycle in the graph. It is also assumed that $n$ is even. This implies that $a_2$ must be odd – in fact $C$ is a cycle if and only if $gcd(a_2, n) = 1$. [In other words, $C$ forms a cycle if and only if $a_2$ is a generator in $(mathbb Z/nmathbb Z, +)$.]
$endgroup$
– M. Vinay
Apr 1 at 1:21
$begingroup$
@jacksonjose In the statement of the lemma, it is assumed that "$a_2$ form[s] a Hamiltonian cycle", which means the value of the jump $a_2$ is such that $C = (1, 1 + a_2, 1 + 2a_2, ldots, 1 + (n - 1)a_2)$ (all $mod n$) is a cycle in the graph. It is also assumed that $n$ is even. This implies that $a_2$ must be odd – in fact $C$ is a cycle if and only if $gcd(a_2, n) = 1$. [In other words, $C$ forms a cycle if and only if $a_2$ is a generator in $(mathbb Z/nmathbb Z, +)$.]
$endgroup$
– M. Vinay
Apr 1 at 1:21
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3169118%2fprove-that-the-connected-circulant-regular-graphs-of-degree-at-least-three-conta%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
So with further research, I understood that a circulant graph is edge-bipancyclic, which means that every edge lies in an even cycle, so could we maybe interpret it that way?
$endgroup$
– jackson jose
Mar 31 at 7:11
$begingroup$
Please could you clarify "contain all even cycles"? $K_4=Ci_4(1,2)$ is a connected circulant graph, has degree 3 and contains 3-cycles.
$endgroup$
– Rosie F
Mar 31 at 8:12
$begingroup$
@RosieF the question is answered, that "contains all even cycles" has been explained below.
$endgroup$
– jackson jose
Mar 31 at 17:36