Counting techniques to find all nonisomorphic graphs with six vertices, all having degree $2.$
$begingroup$
First of all, the graphs considered are undirected & parallel edges and loops are allowed.
My attempt : By handshaking lemma, $$text{Sum of degrees of all vertices} = 2 (text{Number of edges})$$
Thus we get $frac {2+2+2+2+2+2}{2}=text{Number of edges}=6.$
Therefore we have to find all nonisomorphic graphs with six vertices and six edges.
Then I formed six cases based on number of cycles in such nonisomorphic graphs. Each case was then divided into subcases where we count graphs with number of loops and parallel edges in it.
My question is whether there exist other counting techniques in
such scenario?
combinatorics discrete-mathematics graph-theory graph-isomorphism
asked Oct 26 '17 at 9:02
Error 404Error 404
3,84321336
$endgroup$
add a comment |
$begingroup$
First of all, the graphs considered are undirected & parallel edges and loops are allowed.
My attempt : By handshaking lemma, $$text{Sum of degrees of all vertices} = 2 (text{Number of edges})$$
Thus we get $frac {2+2+2+2+2+2}{2}=text{Number of edges}=6.$
Therefore we have to find all nonisomorphic graphs with six vertices and six edges.
Then I formed six cases based on number of cycles in such nonisomorphic graphs. Each case was then divided into subcases where we count graphs with number of loops and parallel edges in it.
My question is whether there exist other counting techniques in
such scenario?
combinatorics discrete-mathematics graph-theory graph-isomorphism
asked Oct 26 '17 at 9:02
Error 404Error 404
3,84321336
$endgroup$
add a comment |
$begingroup$
First of all, the graphs considered are undirected & parallel edges and loops are allowed.
My attempt : By handshaking lemma, $$text{Sum of degrees of all vertices} = 2 (text{Number of edges})$$
Thus we get $frac {2+2+2+2+2+2}{2}=text{Number of edges}=6.$
Therefore we have to find all nonisomorphic graphs with six vertices and six edges.
Then I formed six cases based on number of cycles in such nonisomorphic graphs. Each case was then divided into subcases where we count graphs with number of loops and parallel edges in it.
My question is whether there exist other counting techniques in
such scenario?
combinatorics discrete-mathematics graph-theory graph-isomorphism
asked Oct 26 '17 at 9:02
Error 404Error 404
3,84321336
$endgroup$
First of all, the graphs considered are undirected & parallel edges and loops are allowed.
My attempt : By handshaking lemma, $$text{Sum of degrees of all vertices} = 2 (text{Number of edges})$$
Thus we get $frac {2+2+2+2+2+2}{2}=text{Number of edges}=6.$
Therefore we have to find all nonisomorphic graphs with six vertices and six edges.
Then I formed six cases based on number of cycles in such nonisomorphic graphs. Each case was then divided into subcases where we count graphs with number of loops and parallel edges in it.
My question is whether there exist other counting techniques in
such scenario?
combinatorics discrete-mathematics graph-theory graph-isomorphism
combinatorics discrete-mathematics graph-theory graph-isomorphism
asked Oct 26 '17 at 9:02
Error 404Error 404
3,84321336
asked Oct 26 '17 at 9:02
Error 404Error 404
3,84321336
asked Oct 26 '17 at 9:02
Error 404Error 404
3,84321336
asked Oct 26 '17 at 9:02
Error 404Error 404
3,84321336
asked Oct 26 '17 at 9:02
Error 404Error 404
3,84321336
3,84321336
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Each one of those isomorphism classes can be represented as an integer partition of 6, that is, a way of writing positive numbers which add up to 6, where the order doesn't matter. For example your 3(i), 3(ii) and 3(iii) correspond to $2 + 2 + 2, 4 + 1 + 1$ and $3 + 2 + 1$ respectively. There is a well-understood theory of integer partitions which would allow you to, for example, compute the number of partitions of some large integer $n$ without having to explicitly write them out, and therefore to compute the number of nonisomorphic graphs with $n$ vertices all having degree 2. (In the $n = 6$ case that theory is probably overkill.)
answered Oct 26 '17 at 14:36
Michael LugoMichael Lugo
18k33576
$endgroup$
$begingroup$
Great! Isn't it that the number of integer partitions we are making of 6 in a particular case (for example case-3 as you said) are actually number of connected components of the graph in that case?
$endgroup$
– Error 404
Oct 28 '17 at 5:31
add a comment |
$begingroup$
An alternative approach is given by Riddell's formula, which transforms the generating function for the number of connected graphs of $n$ vertices with property $P$ into the generating function for the number of graphs of $n$ vertices whose connected components have property $P$.
Here you appear to be working with unlabelled graphs, so the number of connected graphs of $n$ vertices with the property that each vertex has degree $2$ is $1$ (for $n ge 1$ given your convention on loops), and we work with ordinary generating functions. We have1 g.f. $A(x) = x + x^2 + x^3 + ldots = frac{x}{1-x}$ for connected graphs. Then we get g.f. for all graphs of $expleft(sum_{k=1}^infty frac{A(x^k)}{k} right) = expleft(sum_{k=1}^infty frac{x^k}{k(1-x^k)} right)$.
This is even more overkill as an approach than going directly to the partition function, although it winds up in the same place, as witness the mention of the above generating function in OEIS A000041.
1 I'm brushing under the carpet some technicalities around graphs with $0$ vertices.
answered Oct 26 '17 at 15:08
Peter TaylorPeter Taylor
8,92212341
$endgroup$
$begingroup$
Interesting! +1
$endgroup$
– Error 404
Oct 28 '17 at 5:33
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
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%2f2490502%2fcounting-techniques-to-find-all-nonisomorphic-graphs-with-six-vertices-all-havi%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Each one of those isomorphism classes can be represented as an integer partition of 6, that is, a way of writing positive numbers which add up to 6, where the order doesn't matter. For example your 3(i), 3(ii) and 3(iii) correspond to $2 + 2 + 2, 4 + 1 + 1$ and $3 + 2 + 1$ respectively. There is a well-understood theory of integer partitions which would allow you to, for example, compute the number of partitions of some large integer $n$ without having to explicitly write them out, and therefore to compute the number of nonisomorphic graphs with $n$ vertices all having degree 2. (In the $n = 6$ case that theory is probably overkill.)
answered Oct 26 '17 at 14:36
Michael LugoMichael Lugo
18k33576
$endgroup$
$begingroup$
Great! Isn't it that the number of integer partitions we are making of 6 in a particular case (for example case-3 as you said) are actually number of connected components of the graph in that case?
$endgroup$
– Error 404
Oct 28 '17 at 5:31
add a comment |
$begingroup$
Each one of those isomorphism classes can be represented as an integer partition of 6, that is, a way of writing positive numbers which add up to 6, where the order doesn't matter. For example your 3(i), 3(ii) and 3(iii) correspond to $2 + 2 + 2, 4 + 1 + 1$ and $3 + 2 + 1$ respectively. There is a well-understood theory of integer partitions which would allow you to, for example, compute the number of partitions of some large integer $n$ without having to explicitly write them out, and therefore to compute the number of nonisomorphic graphs with $n$ vertices all having degree 2. (In the $n = 6$ case that theory is probably overkill.)
answered Oct 26 '17 at 14:36
Michael LugoMichael Lugo
18k33576
$endgroup$
$begingroup$
Great! Isn't it that the number of integer partitions we are making of 6 in a particular case (for example case-3 as you said) are actually number of connected components of the graph in that case?
$endgroup$
– Error 404
Oct 28 '17 at 5:31
add a comment |
$begingroup$
Each one of those isomorphism classes can be represented as an integer partition of 6, that is, a way of writing positive numbers which add up to 6, where the order doesn't matter. For example your 3(i), 3(ii) and 3(iii) correspond to $2 + 2 + 2, 4 + 1 + 1$ and $3 + 2 + 1$ respectively. There is a well-understood theory of integer partitions which would allow you to, for example, compute the number of partitions of some large integer $n$ without having to explicitly write them out, and therefore to compute the number of nonisomorphic graphs with $n$ vertices all having degree 2. (In the $n = 6$ case that theory is probably overkill.)
answered Oct 26 '17 at 14:36
Michael LugoMichael Lugo
18k33576
$endgroup$
Each one of those isomorphism classes can be represented as an integer partition of 6, that is, a way of writing positive numbers which add up to 6, where the order doesn't matter. For example your 3(i), 3(ii) and 3(iii) correspond to $2 + 2 + 2, 4 + 1 + 1$ and $3 + 2 + 1$ respectively. There is a well-understood theory of integer partitions which would allow you to, for example, compute the number of partitions of some large integer $n$ without having to explicitly write them out, and therefore to compute the number of nonisomorphic graphs with $n$ vertices all having degree 2. (In the $n = 6$ case that theory is probably overkill.)
answered Oct 26 '17 at 14:36
Michael LugoMichael Lugo
18k33576
answered Oct 26 '17 at 14:36
Michael LugoMichael Lugo
18k33576
answered Oct 26 '17 at 14:36
Michael LugoMichael Lugo
18k33576
answered Oct 26 '17 at 14:36
Michael LugoMichael Lugo
18k33576
18k33576
$begingroup$
Great! Isn't it that the number of integer partitions we are making of 6 in a particular case (for example case-3 as you said) are actually number of connected components of the graph in that case?
$endgroup$
– Error 404
Oct 28 '17 at 5:31
add a comment |
$begingroup$
Great! Isn't it that the number of integer partitions we are making of 6 in a particular case (for example case-3 as you said) are actually number of connected components of the graph in that case?
$endgroup$
– Error 404
Oct 28 '17 at 5:31
$begingroup$
Great! Isn't it that the number of integer partitions we are making of 6 in a particular case (for example case-3 as you said) are actually number of connected components of the graph in that case?
$endgroup$
– Error 404
Oct 28 '17 at 5:31
$begingroup$
Great! Isn't it that the number of integer partitions we are making of 6 in a particular case (for example case-3 as you said) are actually number of connected components of the graph in that case?
$endgroup$
– Error 404
Oct 28 '17 at 5:31
add a comment |
$begingroup$
An alternative approach is given by Riddell's formula, which transforms the generating function for the number of connected graphs of $n$ vertices with property $P$ into the generating function for the number of graphs of $n$ vertices whose connected components have property $P$.
Here you appear to be working with unlabelled graphs, so the number of connected graphs of $n$ vertices with the property that each vertex has degree $2$ is $1$ (for $n ge 1$ given your convention on loops), and we work with ordinary generating functions. We have1 g.f. $A(x) = x + x^2 + x^3 + ldots = frac{x}{1-x}$ for connected graphs. Then we get g.f. for all graphs of $expleft(sum_{k=1}^infty frac{A(x^k)}{k} right) = expleft(sum_{k=1}^infty frac{x^k}{k(1-x^k)} right)$.
This is even more overkill as an approach than going directly to the partition function, although it winds up in the same place, as witness the mention of the above generating function in OEIS A000041.
1 I'm brushing under the carpet some technicalities around graphs with $0$ vertices.
answered Oct 26 '17 at 15:08
Peter TaylorPeter Taylor
8,92212341
$endgroup$
$begingroup$
Interesting! +1
$endgroup$
– Error 404
Oct 28 '17 at 5:33
add a comment |
$begingroup$
An alternative approach is given by Riddell's formula, which transforms the generating function for the number of connected graphs of $n$ vertices with property $P$ into the generating function for the number of graphs of $n$ vertices whose connected components have property $P$.
Here you appear to be working with unlabelled graphs, so the number of connected graphs of $n$ vertices with the property that each vertex has degree $2$ is $1$ (for $n ge 1$ given your convention on loops), and we work with ordinary generating functions. We have1 g.f. $A(x) = x + x^2 + x^3 + ldots = frac{x}{1-x}$ for connected graphs. Then we get g.f. for all graphs of $expleft(sum_{k=1}^infty frac{A(x^k)}{k} right) = expleft(sum_{k=1}^infty frac{x^k}{k(1-x^k)} right)$.
This is even more overkill as an approach than going directly to the partition function, although it winds up in the same place, as witness the mention of the above generating function in OEIS A000041.
1 I'm brushing under the carpet some technicalities around graphs with $0$ vertices.
answered Oct 26 '17 at 15:08
Peter TaylorPeter Taylor
8,92212341
$endgroup$
$begingroup$
Interesting! +1
$endgroup$
– Error 404
Oct 28 '17 at 5:33
add a comment |
$begingroup$
An alternative approach is given by Riddell's formula, which transforms the generating function for the number of connected graphs of $n$ vertices with property $P$ into the generating function for the number of graphs of $n$ vertices whose connected components have property $P$.
Here you appear to be working with unlabelled graphs, so the number of connected graphs of $n$ vertices with the property that each vertex has degree $2$ is $1$ (for $n ge 1$ given your convention on loops), and we work with ordinary generating functions. We have1 g.f. $A(x) = x + x^2 + x^3 + ldots = frac{x}{1-x}$ for connected graphs. Then we get g.f. for all graphs of $expleft(sum_{k=1}^infty frac{A(x^k)}{k} right) = expleft(sum_{k=1}^infty frac{x^k}{k(1-x^k)} right)$.
This is even more overkill as an approach than going directly to the partition function, although it winds up in the same place, as witness the mention of the above generating function in OEIS A000041.
1 I'm brushing under the carpet some technicalities around graphs with $0$ vertices.
answered Oct 26 '17 at 15:08
Peter TaylorPeter Taylor
8,92212341
$endgroup$
An alternative approach is given by Riddell's formula, which transforms the generating function for the number of connected graphs of $n$ vertices with property $P$ into the generating function for the number of graphs of $n$ vertices whose connected components have property $P$.
Here you appear to be working with unlabelled graphs, so the number of connected graphs of $n$ vertices with the property that each vertex has degree $2$ is $1$ (for $n ge 1$ given your convention on loops), and we work with ordinary generating functions. We have1 g.f. $A(x) = x + x^2 + x^3 + ldots = frac{x}{1-x}$ for connected graphs. Then we get g.f. for all graphs of $expleft(sum_{k=1}^infty frac{A(x^k)}{k} right) = expleft(sum_{k=1}^infty frac{x^k}{k(1-x^k)} right)$.
This is even more overkill as an approach than going directly to the partition function, although it winds up in the same place, as witness the mention of the above generating function in OEIS A000041.
1 I'm brushing under the carpet some technicalities around graphs with $0$ vertices.
answered Oct 26 '17 at 15:08
Peter TaylorPeter Taylor
8,92212341
answered Oct 26 '17 at 15:08
Peter TaylorPeter Taylor
8,92212341
answered Oct 26 '17 at 15:08
Peter TaylorPeter Taylor
8,92212341
answered Oct 26 '17 at 15:08
Peter TaylorPeter Taylor
8,92212341
8,92212341
$begingroup$
Interesting! +1
$endgroup$
– Error 404
Oct 28 '17 at 5:33
add a comment |
$begingroup$
Interesting! +1
$endgroup$
– Error 404
Oct 28 '17 at 5:33
$begingroup$
Interesting! +1
$endgroup$
– Error 404
Oct 28 '17 at 5:33
$begingroup$
Interesting! +1
$endgroup$
– Error 404
Oct 28 '17 at 5:33
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%2f2490502%2fcounting-techniques-to-find-all-nonisomorphic-graphs-with-six-vertices-all-havi%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
