How to show that complement a of regular graph is a Hamiltonian graph? [closed]
$begingroup$
I have a regular graph G of degree k ≥ 1 (ie its every vertex is of degree k) with at least 2k+2 vertices. How do I show that complement of G is a Hamiltonian graph?
graph-theory hamiltonian-path
asked Dec 9 '18 at 16:00
PoulPoul
82
$endgroup$
closed as off-topic by Isaac Browne, Paul Frost, DRF, Cesareo, José Carlos Santos Dec 10 '18 at 0:23
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Isaac Browne, Paul Frost, DRF, Cesareo, José Carlos Santos
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
$begingroup$
I have a regular graph G of degree k ≥ 1 (ie its every vertex is of degree k) with at least 2k+2 vertices. How do I show that complement of G is a Hamiltonian graph?
graph-theory hamiltonian-path
asked Dec 9 '18 at 16:00
PoulPoul
82
$endgroup$
closed as off-topic by Isaac Browne, Paul Frost, DRF, Cesareo, José Carlos Santos Dec 10 '18 at 0:23
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Isaac Browne, Paul Frost, DRF, Cesareo, José Carlos Santos
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
$begingroup$
I have a regular graph G of degree k ≥ 1 (ie its every vertex is of degree k) with at least 2k+2 vertices. How do I show that complement of G is a Hamiltonian graph?
graph-theory hamiltonian-path
asked Dec 9 '18 at 16:00
PoulPoul
82
$endgroup$
I have a regular graph G of degree k ≥ 1 (ie its every vertex is of degree k) with at least 2k+2 vertices. How do I show that complement of G is a Hamiltonian graph?
graph-theory hamiltonian-path
graph-theory hamiltonian-path
asked Dec 9 '18 at 16:00
PoulPoul
82
asked Dec 9 '18 at 16:00
PoulPoul
82
asked Dec 9 '18 at 16:00
PoulPoul
82
asked Dec 9 '18 at 16:00
PoulPoul
82
asked Dec 9 '18 at 16:00
PoulPoul
82
82
closed as off-topic by Isaac Browne, Paul Frost, DRF, Cesareo, José Carlos Santos Dec 10 '18 at 0:23
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Isaac Browne, Paul Frost, DRF, Cesareo, José Carlos Santos
If this question can be reworded to fit the rules in the help center, please edit the question.
closed as off-topic by Isaac Browne, Paul Frost, DRF, Cesareo, José Carlos Santos Dec 10 '18 at 0:23
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Isaac Browne, Paul Frost, DRF, Cesareo, José Carlos Santos
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Indeed, let $n$ be the number of vertices of the graph. Since graph $G$ is $k$-regular, its complement
$overline{G}$ is $(n-1-k)$-regular. To apply Ore’s theorem it suffices to check that $2(n-1-k)ge n$ which holds iff $nge 2k+2$.
answered Dec 9 '18 at 16:17
Alex RavskyAlex Ravsky
41.5k32282
$endgroup$
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Indeed, let $n$ be the number of vertices of the graph. Since graph $G$ is $k$-regular, its complement
$overline{G}$ is $(n-1-k)$-regular. To apply Ore’s theorem it suffices to check that $2(n-1-k)ge n$ which holds iff $nge 2k+2$.
answered Dec 9 '18 at 16:17
Alex RavskyAlex Ravsky
41.5k32282
$endgroup$
add a comment |
$begingroup$
Indeed, let $n$ be the number of vertices of the graph. Since graph $G$ is $k$-regular, its complement
$overline{G}$ is $(n-1-k)$-regular. To apply Ore’s theorem it suffices to check that $2(n-1-k)ge n$ which holds iff $nge 2k+2$.
answered Dec 9 '18 at 16:17
Alex RavskyAlex Ravsky
41.5k32282
$endgroup$
add a comment |
$begingroup$
Indeed, let $n$ be the number of vertices of the graph. Since graph $G$ is $k$-regular, its complement
$overline{G}$ is $(n-1-k)$-regular. To apply Ore’s theorem it suffices to check that $2(n-1-k)ge n$ which holds iff $nge 2k+2$.
answered Dec 9 '18 at 16:17
Alex RavskyAlex Ravsky
41.5k32282
$endgroup$
Indeed, let $n$ be the number of vertices of the graph. Since graph $G$ is $k$-regular, its complement
$overline{G}$ is $(n-1-k)$-regular. To apply Ore’s theorem it suffices to check that $2(n-1-k)ge n$ which holds iff $nge 2k+2$.
answered Dec 9 '18 at 16:17
Alex RavskyAlex Ravsky
41.5k32282
edited Dec 9 '18 at 16:23
answered Dec 9 '18 at 16:17
Alex RavskyAlex Ravsky
41.5k32282
answered Dec 9 '18 at 16:17
Alex RavskyAlex Ravsky
41.5k32282
answered Dec 9 '18 at 16:17
Alex RavskyAlex Ravsky
41.5k32282
41.5k32282
add a comment |
add a comment |
