How much graph instances that have only three degree vertices.
up vote
0
down vote
favorite
For one of my algorithms, i'm looking to know what are the graphs that have only three degree vertex.
For example here is the first graph i know, that have this property:
graph example with only 3 degree vetices
Are they other graph instances that have this criterion?
Thank you.
graph-theory
asked Nov 16 at 13:06
zak zak
1033
add a comment |
up vote
0
down vote
favorite
For one of my algorithms, i'm looking to know what are the graphs that have only three degree vertex.
For example here is the first graph i know, that have this property:
graph example with only 3 degree vetices
Are they other graph instances that have this criterion?
Thank you.
graph-theory
asked Nov 16 at 13:06
zak zak
1033
They are called "cubic graphs" and there is tons of literature about them.
– Michal Adamaszek
Nov 16 at 13:34
@MichalAdamaszek thank you, i will google that word.
– zak zak
Nov 16 at 15:29
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
For one of my algorithms, i'm looking to know what are the graphs that have only three degree vertex.
For example here is the first graph i know, that have this property:
graph example with only 3 degree vetices
Are they other graph instances that have this criterion?
Thank you.
graph-theory
asked Nov 16 at 13:06
zak zak
1033
For one of my algorithms, i'm looking to know what are the graphs that have only three degree vertex.
For example here is the first graph i know, that have this property:
graph example with only 3 degree vetices
Are they other graph instances that have this criterion?
Thank you.
graph-theory
graph-theory
asked Nov 16 at 13:06
zak zak
1033
asked Nov 16 at 13:06
zak zak
1033
asked Nov 16 at 13:06
zak zak
1033
asked Nov 16 at 13:06
zak zak
1033
asked Nov 16 at 13:06
zak zak
1033
1033
They are called "cubic graphs" and there is tons of literature about them.
– Michal Adamaszek
Nov 16 at 13:34
@MichalAdamaszek thank you, i will google that word.
– zak zak
Nov 16 at 15:29
add a comment |
They are called "cubic graphs" and there is tons of literature about them.
– Michal Adamaszek
Nov 16 at 13:34
@MichalAdamaszek thank you, i will google that word.
– zak zak
Nov 16 at 15:29
They are called "cubic graphs" and there is tons of literature about them.
– Michal Adamaszek
Nov 16 at 13:34
They are called "cubic graphs" and there is tons of literature about them.
– Michal Adamaszek
Nov 16 at 13:34
@MichalAdamaszek thank you, i will google that word.
– zak zak
Nov 16 at 15:29
@MichalAdamaszek thank you, i will google that word.
– zak zak
Nov 16 at 15:29
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
accepted
If such a graph has $V$ vertices and $E$ edges then
$2E = 3V$
so $V$ must be a multiple of $2$ and $E$ must be a multiple of $3$.
Draw two cyclic graphs, each with $n$ vertices. Each vertex has degree $2$. Now create a one-to-one mapping between the vertices in one cycle and the vertices in the other cycle. Add edges linking each vertex in one cycle to the corresponding vertex in the other cycle. Now you have a graph with $2n$ vertices and $3n$ edges where each vertex has degree $3$.
answered Nov 16 at 13:51
gandalf61
7,207623
Thank you, so there is an infinity of graph instances with that criterion.
– zak zak
Nov 16 at 15:44
Yes, that is correct.
– gandalf61
Nov 16 at 15:58
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
accepted
If such a graph has $V$ vertices and $E$ edges then
$2E = 3V$
so $V$ must be a multiple of $2$ and $E$ must be a multiple of $3$.
Draw two cyclic graphs, each with $n$ vertices. Each vertex has degree $2$. Now create a one-to-one mapping between the vertices in one cycle and the vertices in the other cycle. Add edges linking each vertex in one cycle to the corresponding vertex in the other cycle. Now you have a graph with $2n$ vertices and $3n$ edges where each vertex has degree $3$.
answered Nov 16 at 13:51
gandalf61
7,207623
Thank you, so there is an infinity of graph instances with that criterion.
– zak zak
Nov 16 at 15:44
Yes, that is correct.
– gandalf61
Nov 16 at 15:58
add a comment |
up vote
0
down vote
accepted
If such a graph has $V$ vertices and $E$ edges then
$2E = 3V$
so $V$ must be a multiple of $2$ and $E$ must be a multiple of $3$.
Draw two cyclic graphs, each with $n$ vertices. Each vertex has degree $2$. Now create a one-to-one mapping between the vertices in one cycle and the vertices in the other cycle. Add edges linking each vertex in one cycle to the corresponding vertex in the other cycle. Now you have a graph with $2n$ vertices and $3n$ edges where each vertex has degree $3$.
answered Nov 16 at 13:51
gandalf61
7,207623
Thank you, so there is an infinity of graph instances with that criterion.
– zak zak
Nov 16 at 15:44
Yes, that is correct.
– gandalf61
Nov 16 at 15:58
add a comment |
up vote
0
down vote
accepted
up vote
0
down vote
accepted
If such a graph has $V$ vertices and $E$ edges then
$2E = 3V$
so $V$ must be a multiple of $2$ and $E$ must be a multiple of $3$.
Draw two cyclic graphs, each with $n$ vertices. Each vertex has degree $2$. Now create a one-to-one mapping between the vertices in one cycle and the vertices in the other cycle. Add edges linking each vertex in one cycle to the corresponding vertex in the other cycle. Now you have a graph with $2n$ vertices and $3n$ edges where each vertex has degree $3$.
answered Nov 16 at 13:51
gandalf61
7,207623
If such a graph has $V$ vertices and $E$ edges then
$2E = 3V$
so $V$ must be a multiple of $2$ and $E$ must be a multiple of $3$.
Draw two cyclic graphs, each with $n$ vertices. Each vertex has degree $2$. Now create a one-to-one mapping between the vertices in one cycle and the vertices in the other cycle. Add edges linking each vertex in one cycle to the corresponding vertex in the other cycle. Now you have a graph with $2n$ vertices and $3n$ edges where each vertex has degree $3$.
answered Nov 16 at 13:51
gandalf61
7,207623
answered Nov 16 at 13:51
gandalf61
7,207623
answered Nov 16 at 13:51
gandalf61
7,207623
answered Nov 16 at 13:51
gandalf61
7,207623
7,207623
Thank you, so there is an infinity of graph instances with that criterion.
– zak zak
Nov 16 at 15:44
Yes, that is correct.
– gandalf61
Nov 16 at 15:58
add a comment |
Thank you, so there is an infinity of graph instances with that criterion.
– zak zak
Nov 16 at 15:44
Yes, that is correct.
– gandalf61
Nov 16 at 15:58
Thank you, so there is an infinity of graph instances with that criterion.
– zak zak
Nov 16 at 15:44
Thank you, so there is an infinity of graph instances with that criterion.
– zak zak
Nov 16 at 15:44
Yes, that is correct.
– gandalf61
Nov 16 at 15:58
Yes, that is correct.
– gandalf61
Nov 16 at 15:58
add a comment |
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%2f3001118%2fhow-much-graph-instances-that-have-only-three-degree-vertices%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
They are called "cubic graphs" and there is tons of literature about them.
– Michal Adamaszek
Nov 16 at 13:34
@MichalAdamaszek thank you, i will google that word.
– zak zak
Nov 16 at 15:29