Mixing
How many 2-edge-colourings of $K_n$ are there?
$begingroup$
I'm writing a paper on Ramsey Theory and it would be interesting and useful to know the number of essentially different 2-edge-colourings of $K_n$ there are. By that I mean the number of essentially different maps $chi:E(K_n)to{1,2}$.
Of course, $2^{binom{n}{2}-1}$ is an (almost trivial) upper bound but, having calculated by hand for a few small values of $n$, this is obviously far too high.
I have found quoted values for $n=16$ and $n=17$ but that's pretty much it. I assume, therefore, that it is known for all smaller values, too, and that would be more than adequate for my purposes. Does anyone know of an explicit formula or "good" bound, or where I could find such a thing?
graph-theory ramsey-theory
edited Feb 25 '13 at 17:37
Diego Silvera
1,2001326
asked Feb 25 '13 at 17:35
ClumClum
815
$endgroup$
add a comment |
$begingroup$
I'm writing a paper on Ramsey Theory and it would be interesting and useful to know the number of essentially different 2-edge-colourings of $K_n$ there are. By that I mean the number of essentially different maps $chi:E(K_n)to{1,2}$.
Of course, $2^{binom{n}{2}-1}$ is an (almost trivial) upper bound but, having calculated by hand for a few small values of $n$, this is obviously far too high.
I have found quoted values for $n=16$ and $n=17$ but that's pretty much it. I assume, therefore, that it is known for all smaller values, too, and that would be more than adequate for my purposes. Does anyone know of an explicit formula or "good" bound, or where I could find such a thing?
graph-theory ramsey-theory
edited Feb 25 '13 at 17:37
Diego Silvera
1,2001326
asked Feb 25 '13 at 17:35
ClumClum
815
$endgroup$
$begingroup$
I haven't thought about this carefully--I'm at the dentist--but it seems to me that it might be easy to apply the Pólya-Burnside-Redfield-Cauchy-Frobenius counting lemma here, since the symmetry group of $K_n$ is so especially simple.
$endgroup$
– MJD
Feb 25 '13 at 17:42
1
$begingroup$
I do not see how this question can be answered until you explain what you mean by "essentially different".
$endgroup$
– Chris Godsil
Feb 25 '13 at 19:58
$begingroup$
Apologies. Two colourings would be "essentially the same" if a relabelling of the vertices of one would give the other, or if they were the same but with the colours switched. (I hesitate to say isomorphic for some reason but that's pretty much what I mean). For example, for a graph of any order, there is only one "essentially different" map that gives colour 1 to precisely one edge and colour 2 to all others.
$endgroup$
– Clum
Feb 25 '13 at 20:56
add a comment |
$begingroup$
I'm writing a paper on Ramsey Theory and it would be interesting and useful to know the number of essentially different 2-edge-colourings of $K_n$ there are. By that I mean the number of essentially different maps $chi:E(K_n)to{1,2}$.
Of course, $2^{binom{n}{2}-1}$ is an (almost trivial) upper bound but, having calculated by hand for a few small values of $n$, this is obviously far too high.
I have found quoted values for $n=16$ and $n=17$ but that's pretty much it. I assume, therefore, that it is known for all smaller values, too, and that would be more than adequate for my purposes. Does anyone know of an explicit formula or "good" bound, or where I could find such a thing?
graph-theory ramsey-theory
edited Feb 25 '13 at 17:37
Diego Silvera
1,2001326
asked Feb 25 '13 at 17:35
ClumClum
815
$endgroup$
I'm writing a paper on Ramsey Theory and it would be interesting and useful to know the number of essentially different 2-edge-colourings of $K_n$ there are. By that I mean the number of essentially different maps $chi:E(K_n)to{1,2}$.
Of course, $2^{binom{n}{2}-1}$ is an (almost trivial) upper bound but, having calculated by hand for a few small values of $n$, this is obviously far too high.
I have found quoted values for $n=16$ and $n=17$ but that's pretty much it. I assume, therefore, that it is known for all smaller values, too, and that would be more than adequate for my purposes. Does anyone know of an explicit formula or "good" bound, or where I could find such a thing?
graph-theory ramsey-theory
graph-theory ramsey-theory
edited Feb 25 '13 at 17:37
Diego Silvera
1,2001326
asked Feb 25 '13 at 17:35
ClumClum
815
edited Feb 25 '13 at 17:37
Diego Silvera
1,2001326
asked Feb 25 '13 at 17:35
ClumClum
815
edited Feb 25 '13 at 17:37
Diego Silvera
1,2001326
edited Feb 25 '13 at 17:37
Diego Silvera
1,2001326
edited Feb 25 '13 at 17:37
Diego Silvera
1,2001326
1,2001326
asked Feb 25 '13 at 17:35
ClumClum
815
asked Feb 25 '13 at 17:35
ClumClum
815
asked Feb 25 '13 at 17:35
ClumClum
815
815
$begingroup$
I haven't thought about this carefully--I'm at the dentist--but it seems to me that it might be easy to apply the Pólya-Burnside-Redfield-Cauchy-Frobenius counting lemma here, since the symmetry group of $K_n$ is so especially simple.
$endgroup$
– MJD
Feb 25 '13 at 17:42
1
$begingroup$
I do not see how this question can be answered until you explain what you mean by "essentially different".
$endgroup$
– Chris Godsil
Feb 25 '13 at 19:58
$begingroup$
Apologies. Two colourings would be "essentially the same" if a relabelling of the vertices of one would give the other, or if they were the same but with the colours switched. (I hesitate to say isomorphic for some reason but that's pretty much what I mean). For example, for a graph of any order, there is only one "essentially different" map that gives colour 1 to precisely one edge and colour 2 to all others.
$endgroup$
– Clum
Feb 25 '13 at 20:56
add a comment |
$begingroup$
I haven't thought about this carefully--I'm at the dentist--but it seems to me that it might be easy to apply the Pólya-Burnside-Redfield-Cauchy-Frobenius counting lemma here, since the symmetry group of $K_n$ is so especially simple.
$endgroup$
– MJD
Feb 25 '13 at 17:42
1
$begingroup$
I do not see how this question can be answered until you explain what you mean by "essentially different".
$endgroup$
– Chris Godsil
Feb 25 '13 at 19:58
$begingroup$
Apologies. Two colourings would be "essentially the same" if a relabelling of the vertices of one would give the other, or if they were the same but with the colours switched. (I hesitate to say isomorphic for some reason but that's pretty much what I mean). For example, for a graph of any order, there is only one "essentially different" map that gives colour 1 to precisely one edge and colour 2 to all others.
$endgroup$
– Clum
Feb 25 '13 at 20:56
$begingroup$
I haven't thought about this carefully--I'm at the dentist--but it seems to me that it might be easy to apply the Pólya-Burnside-Redfield-Cauchy-Frobenius counting lemma here, since the symmetry group of $K_n$ is so especially simple.
$endgroup$
– MJD
Feb 25 '13 at 17:42
$begingroup$
I haven't thought about this carefully--I'm at the dentist--but it seems to me that it might be easy to apply the Pólya-Burnside-Redfield-Cauchy-Frobenius counting lemma here, since the symmetry group of $K_n$ is so especially simple.
$endgroup$
– MJD
Feb 25 '13 at 17:42
1
1
$begingroup$
I do not see how this question can be answered until you explain what you mean by "essentially different".
$endgroup$
– Chris Godsil
Feb 25 '13 at 19:58
$begingroup$
I do not see how this question can be answered until you explain what you mean by "essentially different".
$endgroup$
– Chris Godsil
Feb 25 '13 at 19:58
$begingroup$
Apologies. Two colourings would be "essentially the same" if a relabelling of the vertices of one would give the other, or if they were the same but with the colours switched. (I hesitate to say isomorphic for some reason but that's pretty much what I mean). For example, for a graph of any order, there is only one "essentially different" map that gives colour 1 to precisely one edge and colour 2 to all others.
$endgroup$
– Clum
Feb 25 '13 at 20:56
$begingroup$
Apologies. Two colourings would be "essentially the same" if a relabelling of the vertices of one would give the other, or if they were the same but with the colours switched. (I hesitate to say isomorphic for some reason but that's pretty much what I mean). For example, for a graph of any order, there is only one "essentially different" map that gives colour 1 to precisely one edge and colour 2 to all others.
$endgroup$
– Clum
Feb 25 '13 at 20:56
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
I have not yet had time to read the Clapham paper, but I can perhaps be of use with a related statistic, the number of non-isomorphic graphs on $n$ nodes. There is a wealth of data on this at the OEIS, sequence A000088. Your two colors essentially represent edges being switched on and off, so this is the same statistic.
As you can see from the OEIS entry this is a classic computation, and extremely straightforward. Compute the cycle index of the edge permutation group induced by the $n!$ permutations of the vertex permutation group, substitute with $x+y$ for edges being on and off, and sum the coefficients to get the count of non-isomorphic graphs. The cycle index of the vertex permutation group can be computed with a trick that goes back to Lovasz:
$$ Z(S_0) = 1 quad text{and} quad Z(S_n) = frac{1}{n} sum_{l=1}^n a_l Z(S_{n-l}).$$
Now to turn a vertex permutation into an edge permutation the cycle structure of the former is sufficient, yielding a reduced complexity without which we'd be out of luck. Simply examine and enumerate all possible pairs of vertices and imagine them moving in parallel (i.e., forming an edge) along their respective cycles until the starting configuration is reached. This happens after $operatorname{LCM}(l_1, l_2)$ steps assuming $l_{1,2}$ are the lengths of the two cycles of the vertex permutation. There are two cases when the two vertices lie on the same cycle, depending on whether the length is even or odd. In the former case there are $l/2$ pairs that return to their origin after $l/2$ steps and the rest take $l$ steps, where $l$ is the length of the cycle. Finally there is some overcounting to take into consideration, as every cycle in the edge permutation is overcounted by a factor equal to its length. That is all.
Here is a list of values to peruse.
01 1
02 2
03 4
04 11
05 34
06 156
07 1044
08 12346
09 274668
10 12005168
11 1018997864
12 165091172592
13 50502031367952
14 29054155657235488
15 31426485969804308768
16 64001015704527557894928
17 245935864153532932683719776
18 1787577725145611700547878190848
19 24637809253125004524383007491432768
20 645490122795799841856164638490742749440
21 32220272899808983433502244253755283616097664
22 3070846483094144300637568517187105410586657814272
23 559946939699792080597976380819462179812276348458981632
24 195704906302078447922174862416726256004122075267063365754368
25 131331393569895519432161548405816890146389214706146483380458576384
26 169487618400693135671278778610295749756246061427513800357039083537927168
27 421260006519643885757174107650953992882782878952295704539600450662355704738816
28 2019295999678571395728328980890810345860807065053566265347514137546665672316696821760
29 18691352722478956041683441055221773100906878077027397169675907651818104181986752359177684992
30 334494316309257669249439569928080028956631479935393064329967834887217734534880582749030521599504384
The Maple code to compute these is as follows.
with(numtheory);
with(group):
with(combinat):
pet_cycleind_symm :=
proc(n)
option remember;
if n=0 then return 1; fi;
expand(1/n*
add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;
pet_flatten_term :=
proc(varp)
local terml, d, cf, v;
terml := ;
cf := varp;
for v in indets(varp) do
d := degree(varp, v);
terml := [op(terml), seq(v, k=1..d)];
cf := cf/v^d;
od;
[cf, terml];
end;
pet_cycleind_edg :=
proc(n)
option remember;
local s, t, res, cycs, l1, l2, flat, u, v;
if n=0 then return 1; fi;
s := 0:
for t in pet_cycleind_symm(n) do
flat := pet_flatten_term(t);
cycs := flat[2]; res := 1;
for u to nops(cycs) do
for v from u+1 to nops(cycs) do
l1 := op(1, cycs[u]); l2 := op(1, cycs[v]);
res := res * a[lcm(l1, l2)]^(l1*l2/lcm(l1, l2));
od;
od;
for u to nops(cycs) do
l1 := op(1, cycs[u]);
if type(l1, odd) then
# a[l1]^(1/2*l1*(l1-1)/l1);
res := res*a[l1]^(1/2*(l1-1));
else
# a[l1/2]^(l1/2/(l1/2))*a[l1]^(1/2*l1*(l1-2)/l1)
res := res*a[l1/2]*a[l1]^(1/2*(l1-2));
fi;
od;
s := s + flat[1]*res;
od;
s;
end;
pet_varinto_cind :=
proc(poly, ind)
local subs1, subsl, polyvars, indvars, v, pot;
polyvars := indets(poly);
indvars := indets(ind);
subsl := ;
for v in indvars do
pot := op(1, v);
subs1 :=
[seq(polyvars[k]=polyvars[k]^pot,
k=1..nops(polyvars))];
subsl := [op(subsl), v=subs(subs1, poly)];
od;
subs(subsl, ind);
end;
gf :=
proc(n)
option remember;
local gf;
gf := pet_varinto_cind(1+z, pet_cycleind_edg(n));
expand(gf);
end;
v :=
proc(n)
option remember;
local cind;
cind := pet_cycleind_edg(n);
subs([seq(v=2, v in indets(cind))], cind);
end;
A similar computation can be used to count the number of binary relations on a set of $n$ elements and is documented at this MSE link. This MSE link II shows how to enumerate graphs that permit self-loops.
Addendum Jan 11 2017. There is an optimized version of the above which is twice as fast at the following MSE link. Note that we should use Burnside if we only seek the count of these graphs rather than the classification by the number of edges.
answered Feb 26 '13 at 3:25
Marko RiedelMarko Riedel
40.8k340110
$endgroup$
$begingroup$
Thank you for this. I had not thought to formulate the question in terms of non-isomorphic graphs on $n$ vertices, although it seems so obvious now. Of course, for $nge2$, this number is out by one from the figure I'm looking for because the empty graph is the same as the complete graph for my purposes.
$endgroup$
– Clum
Mar 19 '13 at 13:23
$begingroup$
On further reflection, this statistic actually gives roughly twice the number of colourings, by symmetry. I'm going to sit and work out the precise relation.
$endgroup$
– Clum
Mar 19 '13 at 13:58
$begingroup$
Here is another example where we use the Lovasz formula to calculate the cycle index of the symmetric group.
$endgroup$
– Marko Riedel
Oct 28 '13 at 11:46
$begingroup$
This example shows how to enumerate graphs with colored edges when there is in addition to the edge permutation group a group acting on the colors, further reducing the number of equivalence classes.
$endgroup$
– Marko Riedel
Dec 18 '13 at 11:02
add a comment |
$begingroup$
If you google on something like "clapham easier self-complementary graphs",
you'll be lead to a paper which enumerates self-complementary graphs. The number of isomorphism classes of graphs on $n$ vertices plus the number of isomorphism classes of self-complementary graphs is twice the number you are asking for.
Note that this enumeration was first carried out by R. C. Read; you'll find the citation in Clapham's paper.
edited Jan 11 '17 at 6:00
bof
52.5k558121
answered Feb 25 '13 at 22:26
Chris GodsilChris Godsil
11.7k21635
$endgroup$
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%2f314103%2fhow-many-2-edge-colourings-of-k-n-are-there%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$
I have not yet had time to read the Clapham paper, but I can perhaps be of use with a related statistic, the number of non-isomorphic graphs on $n$ nodes. There is a wealth of data on this at the OEIS, sequence A000088. Your two colors essentially represent edges being switched on and off, so this is the same statistic.
As you can see from the OEIS entry this is a classic computation, and extremely straightforward. Compute the cycle index of the edge permutation group induced by the $n!$ permutations of the vertex permutation group, substitute with $x+y$ for edges being on and off, and sum the coefficients to get the count of non-isomorphic graphs. The cycle index of the vertex permutation group can be computed with a trick that goes back to Lovasz:
$$ Z(S_0) = 1 quad text{and} quad Z(S_n) = frac{1}{n} sum_{l=1}^n a_l Z(S_{n-l}).$$
Now to turn a vertex permutation into an edge permutation the cycle structure of the former is sufficient, yielding a reduced complexity without which we'd be out of luck. Simply examine and enumerate all possible pairs of vertices and imagine them moving in parallel (i.e., forming an edge) along their respective cycles until the starting configuration is reached. This happens after $operatorname{LCM}(l_1, l_2)$ steps assuming $l_{1,2}$ are the lengths of the two cycles of the vertex permutation. There are two cases when the two vertices lie on the same cycle, depending on whether the length is even or odd. In the former case there are $l/2$ pairs that return to their origin after $l/2$ steps and the rest take $l$ steps, where $l$ is the length of the cycle. Finally there is some overcounting to take into consideration, as every cycle in the edge permutation is overcounted by a factor equal to its length. That is all.
Here is a list of values to peruse.
01 1
02 2
03 4
04 11
05 34
06 156
07 1044
08 12346
09 274668
10 12005168
11 1018997864
12 165091172592
13 50502031367952
14 29054155657235488
15 31426485969804308768
16 64001015704527557894928
17 245935864153532932683719776
18 1787577725145611700547878190848
19 24637809253125004524383007491432768
20 645490122795799841856164638490742749440
21 32220272899808983433502244253755283616097664
22 3070846483094144300637568517187105410586657814272
23 559946939699792080597976380819462179812276348458981632
24 195704906302078447922174862416726256004122075267063365754368
25 131331393569895519432161548405816890146389214706146483380458576384
26 169487618400693135671278778610295749756246061427513800357039083537927168
27 421260006519643885757174107650953992882782878952295704539600450662355704738816
28 2019295999678571395728328980890810345860807065053566265347514137546665672316696821760
29 18691352722478956041683441055221773100906878077027397169675907651818104181986752359177684992
30 334494316309257669249439569928080028956631479935393064329967834887217734534880582749030521599504384
The Maple code to compute these is as follows.
with(numtheory);
with(group):
with(combinat):
pet_cycleind_symm :=
proc(n)
option remember;
if n=0 then return 1; fi;
expand(1/n*
add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;
pet_flatten_term :=
proc(varp)
local terml, d, cf, v;
terml := ;
cf := varp;
for v in indets(varp) do
d := degree(varp, v);
terml := [op(terml), seq(v, k=1..d)];
cf := cf/v^d;
od;
[cf, terml];
end;
pet_cycleind_edg :=
proc(n)
option remember;
local s, t, res, cycs, l1, l2, flat, u, v;
if n=0 then return 1; fi;
s := 0:
for t in pet_cycleind_symm(n) do
flat := pet_flatten_term(t);
cycs := flat[2]; res := 1;
for u to nops(cycs) do
for v from u+1 to nops(cycs) do
l1 := op(1, cycs[u]); l2 := op(1, cycs[v]);
res := res * a[lcm(l1, l2)]^(l1*l2/lcm(l1, l2));
od;
od;
for u to nops(cycs) do
l1 := op(1, cycs[u]);
if type(l1, odd) then
# a[l1]^(1/2*l1*(l1-1)/l1);
res := res*a[l1]^(1/2*(l1-1));
else
# a[l1/2]^(l1/2/(l1/2))*a[l1]^(1/2*l1*(l1-2)/l1)
res := res*a[l1/2]*a[l1]^(1/2*(l1-2));
fi;
od;
s := s + flat[1]*res;
od;
s;
end;
pet_varinto_cind :=
proc(poly, ind)
local subs1, subsl, polyvars, indvars, v, pot;
polyvars := indets(poly);
indvars := indets(ind);
subsl := ;
for v in indvars do
pot := op(1, v);
subs1 :=
[seq(polyvars[k]=polyvars[k]^pot,
k=1..nops(polyvars))];
subsl := [op(subsl), v=subs(subs1, poly)];
od;
subs(subsl, ind);
end;
gf :=
proc(n)
option remember;
local gf;
gf := pet_varinto_cind(1+z, pet_cycleind_edg(n));
expand(gf);
end;
v :=
proc(n)
option remember;
local cind;
cind := pet_cycleind_edg(n);
subs([seq(v=2, v in indets(cind))], cind);
end;
A similar computation can be used to count the number of binary relations on a set of $n$ elements and is documented at this MSE link. This MSE link II shows how to enumerate graphs that permit self-loops.
Addendum Jan 11 2017. There is an optimized version of the above which is twice as fast at the following MSE link. Note that we should use Burnside if we only seek the count of these graphs rather than the classification by the number of edges.
answered Feb 26 '13 at 3:25
Marko RiedelMarko Riedel
40.8k340110
$endgroup$
$begingroup$
Thank you for this. I had not thought to formulate the question in terms of non-isomorphic graphs on $n$ vertices, although it seems so obvious now. Of course, for $nge2$, this number is out by one from the figure I'm looking for because the empty graph is the same as the complete graph for my purposes.
$endgroup$
– Clum
Mar 19 '13 at 13:23
$begingroup$
On further reflection, this statistic actually gives roughly twice the number of colourings, by symmetry. I'm going to sit and work out the precise relation.
$endgroup$
– Clum
Mar 19 '13 at 13:58
$begingroup$
Here is another example where we use the Lovasz formula to calculate the cycle index of the symmetric group.
$endgroup$
– Marko Riedel
Oct 28 '13 at 11:46
$begingroup$
This example shows how to enumerate graphs with colored edges when there is in addition to the edge permutation group a group acting on the colors, further reducing the number of equivalence classes.
$endgroup$
– Marko Riedel
Dec 18 '13 at 11:02
add a comment |
$begingroup$
I have not yet had time to read the Clapham paper, but I can perhaps be of use with a related statistic, the number of non-isomorphic graphs on $n$ nodes. There is a wealth of data on this at the OEIS, sequence A000088. Your two colors essentially represent edges being switched on and off, so this is the same statistic.
As you can see from the OEIS entry this is a classic computation, and extremely straightforward. Compute the cycle index of the edge permutation group induced by the $n!$ permutations of the vertex permutation group, substitute with $x+y$ for edges being on and off, and sum the coefficients to get the count of non-isomorphic graphs. The cycle index of the vertex permutation group can be computed with a trick that goes back to Lovasz:
$$ Z(S_0) = 1 quad text{and} quad Z(S_n) = frac{1}{n} sum_{l=1}^n a_l Z(S_{n-l}).$$
Now to turn a vertex permutation into an edge permutation the cycle structure of the former is sufficient, yielding a reduced complexity without which we'd be out of luck. Simply examine and enumerate all possible pairs of vertices and imagine them moving in parallel (i.e., forming an edge) along their respective cycles until the starting configuration is reached. This happens after $operatorname{LCM}(l_1, l_2)$ steps assuming $l_{1,2}$ are the lengths of the two cycles of the vertex permutation. There are two cases when the two vertices lie on the same cycle, depending on whether the length is even or odd. In the former case there are $l/2$ pairs that return to their origin after $l/2$ steps and the rest take $l$ steps, where $l$ is the length of the cycle. Finally there is some overcounting to take into consideration, as every cycle in the edge permutation is overcounted by a factor equal to its length. That is all.
Here is a list of values to peruse.
01 1
02 2
03 4
04 11
05 34
06 156
07 1044
08 12346
09 274668
10 12005168
11 1018997864
12 165091172592
13 50502031367952
14 29054155657235488
15 31426485969804308768
16 64001015704527557894928
17 245935864153532932683719776
18 1787577725145611700547878190848
19 24637809253125004524383007491432768
20 645490122795799841856164638490742749440
21 32220272899808983433502244253755283616097664
22 3070846483094144300637568517187105410586657814272
23 559946939699792080597976380819462179812276348458981632
24 195704906302078447922174862416726256004122075267063365754368
25 131331393569895519432161548405816890146389214706146483380458576384
26 169487618400693135671278778610295749756246061427513800357039083537927168
27 421260006519643885757174107650953992882782878952295704539600450662355704738816
28 2019295999678571395728328980890810345860807065053566265347514137546665672316696821760
29 18691352722478956041683441055221773100906878077027397169675907651818104181986752359177684992
30 334494316309257669249439569928080028956631479935393064329967834887217734534880582749030521599504384
The Maple code to compute these is as follows.
with(numtheory);
with(group):
with(combinat):
pet_cycleind_symm :=
proc(n)
option remember;
if n=0 then return 1; fi;
expand(1/n*
add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;
pet_flatten_term :=
proc(varp)
local terml, d, cf, v;
terml := ;
cf := varp;
for v in indets(varp) do
d := degree(varp, v);
terml := [op(terml), seq(v, k=1..d)];
cf := cf/v^d;
od;
[cf, terml];
end;
pet_cycleind_edg :=
proc(n)
option remember;
local s, t, res, cycs, l1, l2, flat, u, v;
if n=0 then return 1; fi;
s := 0:
for t in pet_cycleind_symm(n) do
flat := pet_flatten_term(t);
cycs := flat[2]; res := 1;
for u to nops(cycs) do
for v from u+1 to nops(cycs) do
l1 := op(1, cycs[u]); l2 := op(1, cycs[v]);
res := res * a[lcm(l1, l2)]^(l1*l2/lcm(l1, l2));
od;
od;
for u to nops(cycs) do
l1 := op(1, cycs[u]);
if type(l1, odd) then
# a[l1]^(1/2*l1*(l1-1)/l1);
res := res*a[l1]^(1/2*(l1-1));
else
# a[l1/2]^(l1/2/(l1/2))*a[l1]^(1/2*l1*(l1-2)/l1)
res := res*a[l1/2]*a[l1]^(1/2*(l1-2));
fi;
od;
s := s + flat[1]*res;
od;
s;
end;
pet_varinto_cind :=
proc(poly, ind)
local subs1, subsl, polyvars, indvars, v, pot;
polyvars := indets(poly);
indvars := indets(ind);
subsl := ;
for v in indvars do
pot := op(1, v);
subs1 :=
[seq(polyvars[k]=polyvars[k]^pot,
k=1..nops(polyvars))];
subsl := [op(subsl), v=subs(subs1, poly)];
od;
subs(subsl, ind);
end;
gf :=
proc(n)
option remember;
local gf;
gf := pet_varinto_cind(1+z, pet_cycleind_edg(n));
expand(gf);
end;
v :=
proc(n)
option remember;
local cind;
cind := pet_cycleind_edg(n);
subs([seq(v=2, v in indets(cind))], cind);
end;
A similar computation can be used to count the number of binary relations on a set of $n$ elements and is documented at this MSE link. This MSE link II shows how to enumerate graphs that permit self-loops.
Addendum Jan 11 2017. There is an optimized version of the above which is twice as fast at the following MSE link. Note that we should use Burnside if we only seek the count of these graphs rather than the classification by the number of edges.
answered Feb 26 '13 at 3:25
Marko RiedelMarko Riedel
40.8k340110
$endgroup$
$begingroup$
Thank you for this. I had not thought to formulate the question in terms of non-isomorphic graphs on $n$ vertices, although it seems so obvious now. Of course, for $nge2$, this number is out by one from the figure I'm looking for because the empty graph is the same as the complete graph for my purposes.
$endgroup$
– Clum
Mar 19 '13 at 13:23
$begingroup$
On further reflection, this statistic actually gives roughly twice the number of colourings, by symmetry. I'm going to sit and work out the precise relation.
$endgroup$
– Clum
Mar 19 '13 at 13:58
$begingroup$
Here is another example where we use the Lovasz formula to calculate the cycle index of the symmetric group.
$endgroup$
– Marko Riedel
Oct 28 '13 at 11:46
$begingroup$
This example shows how to enumerate graphs with colored edges when there is in addition to the edge permutation group a group acting on the colors, further reducing the number of equivalence classes.
$endgroup$
– Marko Riedel
Dec 18 '13 at 11:02
add a comment |
$begingroup$
I have not yet had time to read the Clapham paper, but I can perhaps be of use with a related statistic, the number of non-isomorphic graphs on $n$ nodes. There is a wealth of data on this at the OEIS, sequence A000088. Your two colors essentially represent edges being switched on and off, so this is the same statistic.
As you can see from the OEIS entry this is a classic computation, and extremely straightforward. Compute the cycle index of the edge permutation group induced by the $n!$ permutations of the vertex permutation group, substitute with $x+y$ for edges being on and off, and sum the coefficients to get the count of non-isomorphic graphs. The cycle index of the vertex permutation group can be computed with a trick that goes back to Lovasz:
$$ Z(S_0) = 1 quad text{and} quad Z(S_n) = frac{1}{n} sum_{l=1}^n a_l Z(S_{n-l}).$$
Now to turn a vertex permutation into an edge permutation the cycle structure of the former is sufficient, yielding a reduced complexity without which we'd be out of luck. Simply examine and enumerate all possible pairs of vertices and imagine them moving in parallel (i.e., forming an edge) along their respective cycles until the starting configuration is reached. This happens after $operatorname{LCM}(l_1, l_2)$ steps assuming $l_{1,2}$ are the lengths of the two cycles of the vertex permutation. There are two cases when the two vertices lie on the same cycle, depending on whether the length is even or odd. In the former case there are $l/2$ pairs that return to their origin after $l/2$ steps and the rest take $l$ steps, where $l$ is the length of the cycle. Finally there is some overcounting to take into consideration, as every cycle in the edge permutation is overcounted by a factor equal to its length. That is all.
Here is a list of values to peruse.
01 1
02 2
03 4
04 11
05 34
06 156
07 1044
08 12346
09 274668
10 12005168
11 1018997864
12 165091172592
13 50502031367952
14 29054155657235488
15 31426485969804308768
16 64001015704527557894928
17 245935864153532932683719776
18 1787577725145611700547878190848
19 24637809253125004524383007491432768
20 645490122795799841856164638490742749440
21 32220272899808983433502244253755283616097664
22 3070846483094144300637568517187105410586657814272
23 559946939699792080597976380819462179812276348458981632
24 195704906302078447922174862416726256004122075267063365754368
25 131331393569895519432161548405816890146389214706146483380458576384
26 169487618400693135671278778610295749756246061427513800357039083537927168
27 421260006519643885757174107650953992882782878952295704539600450662355704738816
28 2019295999678571395728328980890810345860807065053566265347514137546665672316696821760
29 18691352722478956041683441055221773100906878077027397169675907651818104181986752359177684992
30 334494316309257669249439569928080028956631479935393064329967834887217734534880582749030521599504384
The Maple code to compute these is as follows.
with(numtheory);
with(group):
with(combinat):
pet_cycleind_symm :=
proc(n)
option remember;
if n=0 then return 1; fi;
expand(1/n*
add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;
pet_flatten_term :=
proc(varp)
local terml, d, cf, v;
terml := ;
cf := varp;
for v in indets(varp) do
d := degree(varp, v);
terml := [op(terml), seq(v, k=1..d)];
cf := cf/v^d;
od;
[cf, terml];
end;
pet_cycleind_edg :=
proc(n)
option remember;
local s, t, res, cycs, l1, l2, flat, u, v;
if n=0 then return 1; fi;
s := 0:
for t in pet_cycleind_symm(n) do
flat := pet_flatten_term(t);
cycs := flat[2]; res := 1;
for u to nops(cycs) do
for v from u+1 to nops(cycs) do
l1 := op(1, cycs[u]); l2 := op(1, cycs[v]);
res := res * a[lcm(l1, l2)]^(l1*l2/lcm(l1, l2));
od;
od;
for u to nops(cycs) do
l1 := op(1, cycs[u]);
if type(l1, odd) then
# a[l1]^(1/2*l1*(l1-1)/l1);
res := res*a[l1]^(1/2*(l1-1));
else
# a[l1/2]^(l1/2/(l1/2))*a[l1]^(1/2*l1*(l1-2)/l1)
res := res*a[l1/2]*a[l1]^(1/2*(l1-2));
fi;
od;
s := s + flat[1]*res;
od;
s;
end;
pet_varinto_cind :=
proc(poly, ind)
local subs1, subsl, polyvars, indvars, v, pot;
polyvars := indets(poly);
indvars := indets(ind);
subsl := ;
for v in indvars do
pot := op(1, v);
subs1 :=
[seq(polyvars[k]=polyvars[k]^pot,
k=1..nops(polyvars))];
subsl := [op(subsl), v=subs(subs1, poly)];
od;
subs(subsl, ind);
end;
gf :=
proc(n)
option remember;
local gf;
gf := pet_varinto_cind(1+z, pet_cycleind_edg(n));
expand(gf);
end;
v :=
proc(n)
option remember;
local cind;
cind := pet_cycleind_edg(n);
subs([seq(v=2, v in indets(cind))], cind);
end;
A similar computation can be used to count the number of binary relations on a set of $n$ elements and is documented at this MSE link. This MSE link II shows how to enumerate graphs that permit self-loops.
Addendum Jan 11 2017. There is an optimized version of the above which is twice as fast at the following MSE link. Note that we should use Burnside if we only seek the count of these graphs rather than the classification by the number of edges.
answered Feb 26 '13 at 3:25
Marko RiedelMarko Riedel
40.8k340110
$endgroup$
I have not yet had time to read the Clapham paper, but I can perhaps be of use with a related statistic, the number of non-isomorphic graphs on $n$ nodes. There is a wealth of data on this at the OEIS, sequence A000088. Your two colors essentially represent edges being switched on and off, so this is the same statistic.
As you can see from the OEIS entry this is a classic computation, and extremely straightforward. Compute the cycle index of the edge permutation group induced by the $n!$ permutations of the vertex permutation group, substitute with $x+y$ for edges being on and off, and sum the coefficients to get the count of non-isomorphic graphs. The cycle index of the vertex permutation group can be computed with a trick that goes back to Lovasz:
$$ Z(S_0) = 1 quad text{and} quad Z(S_n) = frac{1}{n} sum_{l=1}^n a_l Z(S_{n-l}).$$
Now to turn a vertex permutation into an edge permutation the cycle structure of the former is sufficient, yielding a reduced complexity without which we'd be out of luck. Simply examine and enumerate all possible pairs of vertices and imagine them moving in parallel (i.e., forming an edge) along their respective cycles until the starting configuration is reached. This happens after $operatorname{LCM}(l_1, l_2)$ steps assuming $l_{1,2}$ are the lengths of the two cycles of the vertex permutation. There are two cases when the two vertices lie on the same cycle, depending on whether the length is even or odd. In the former case there are $l/2$ pairs that return to their origin after $l/2$ steps and the rest take $l$ steps, where $l$ is the length of the cycle. Finally there is some overcounting to take into consideration, as every cycle in the edge permutation is overcounted by a factor equal to its length. That is all.
Here is a list of values to peruse.
01 1
02 2
03 4
04 11
05 34
06 156
07 1044
08 12346
09 274668
10 12005168
11 1018997864
12 165091172592
13 50502031367952
14 29054155657235488
15 31426485969804308768
16 64001015704527557894928
17 245935864153532932683719776
18 1787577725145611700547878190848
19 24637809253125004524383007491432768
20 645490122795799841856164638490742749440
21 32220272899808983433502244253755283616097664
22 3070846483094144300637568517187105410586657814272
23 559946939699792080597976380819462179812276348458981632
24 195704906302078447922174862416726256004122075267063365754368
25 131331393569895519432161548405816890146389214706146483380458576384
26 169487618400693135671278778610295749756246061427513800357039083537927168
27 421260006519643885757174107650953992882782878952295704539600450662355704738816
28 2019295999678571395728328980890810345860807065053566265347514137546665672316696821760
29 18691352722478956041683441055221773100906878077027397169675907651818104181986752359177684992
30 334494316309257669249439569928080028956631479935393064329967834887217734534880582749030521599504384
The Maple code to compute these is as follows.
with(numtheory);
with(group):
with(combinat):
pet_cycleind_symm :=
proc(n)
option remember;
if n=0 then return 1; fi;
expand(1/n*
add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;
pet_flatten_term :=
proc(varp)
local terml, d, cf, v;
terml := ;
cf := varp;
for v in indets(varp) do
d := degree(varp, v);
terml := [op(terml), seq(v, k=1..d)];
cf := cf/v^d;
od;
[cf, terml];
end;
pet_cycleind_edg :=
proc(n)
option remember;
local s, t, res, cycs, l1, l2, flat, u, v;
if n=0 then return 1; fi;
s := 0:
for t in pet_cycleind_symm(n) do
flat := pet_flatten_term(t);
cycs := flat[2]; res := 1;
for u to nops(cycs) do
for v from u+1 to nops(cycs) do
l1 := op(1, cycs[u]); l2 := op(1, cycs[v]);
res := res * a[lcm(l1, l2)]^(l1*l2/lcm(l1, l2));
od;
od;
for u to nops(cycs) do
l1 := op(1, cycs[u]);
if type(l1, odd) then
# a[l1]^(1/2*l1*(l1-1)/l1);
res := res*a[l1]^(1/2*(l1-1));
else
# a[l1/2]^(l1/2/(l1/2))*a[l1]^(1/2*l1*(l1-2)/l1)
res := res*a[l1/2]*a[l1]^(1/2*(l1-2));
fi;
od;
s := s + flat[1]*res;
od;
s;
end;
pet_varinto_cind :=
proc(poly, ind)
local subs1, subsl, polyvars, indvars, v, pot;
polyvars := indets(poly);
indvars := indets(ind);
subsl := ;
for v in indvars do
pot := op(1, v);
subs1 :=
[seq(polyvars[k]=polyvars[k]^pot,
k=1..nops(polyvars))];
subsl := [op(subsl), v=subs(subs1, poly)];
od;
subs(subsl, ind);
end;
gf :=
proc(n)
option remember;
local gf;
gf := pet_varinto_cind(1+z, pet_cycleind_edg(n));
expand(gf);
end;
v :=
proc(n)
option remember;
local cind;
cind := pet_cycleind_edg(n);
subs([seq(v=2, v in indets(cind))], cind);
end;
A similar computation can be used to count the number of binary relations on a set of $n$ elements and is documented at this MSE link. This MSE link II shows how to enumerate graphs that permit self-loops.
Addendum Jan 11 2017. There is an optimized version of the above which is twice as fast at the following MSE link. Note that we should use Burnside if we only seek the count of these graphs rather than the classification by the number of edges.
answered Feb 26 '13 at 3:25
Marko RiedelMarko Riedel
40.8k340110
edited Jan 26 at 18:41
answered Feb 26 '13 at 3:25
Marko RiedelMarko Riedel
40.8k340110
answered Feb 26 '13 at 3:25
Marko RiedelMarko Riedel
40.8k340110
answered Feb 26 '13 at 3:25
Marko RiedelMarko Riedel
40.8k340110
40.8k340110
$begingroup$
Thank you for this. I had not thought to formulate the question in terms of non-isomorphic graphs on $n$ vertices, although it seems so obvious now. Of course, for $nge2$, this number is out by one from the figure I'm looking for because the empty graph is the same as the complete graph for my purposes.
$endgroup$
– Clum
Mar 19 '13 at 13:23
$begingroup$
On further reflection, this statistic actually gives roughly twice the number of colourings, by symmetry. I'm going to sit and work out the precise relation.
$endgroup$
– Clum
Mar 19 '13 at 13:58
$begingroup$
Here is another example where we use the Lovasz formula to calculate the cycle index of the symmetric group.
$endgroup$
– Marko Riedel
Oct 28 '13 at 11:46
$begingroup$
This example shows how to enumerate graphs with colored edges when there is in addition to the edge permutation group a group acting on the colors, further reducing the number of equivalence classes.
$endgroup$
– Marko Riedel
Dec 18 '13 at 11:02
add a comment |
$begingroup$
Thank you for this. I had not thought to formulate the question in terms of non-isomorphic graphs on $n$ vertices, although it seems so obvious now. Of course, for $nge2$, this number is out by one from the figure I'm looking for because the empty graph is the same as the complete graph for my purposes.
$endgroup$
– Clum
Mar 19 '13 at 13:23
$begingroup$
On further reflection, this statistic actually gives roughly twice the number of colourings, by symmetry. I'm going to sit and work out the precise relation.
$endgroup$
– Clum
Mar 19 '13 at 13:58
$begingroup$
Here is another example where we use the Lovasz formula to calculate the cycle index of the symmetric group.
$endgroup$
– Marko Riedel
Oct 28 '13 at 11:46
$begingroup$
This example shows how to enumerate graphs with colored edges when there is in addition to the edge permutation group a group acting on the colors, further reducing the number of equivalence classes.
$endgroup$
– Marko Riedel
Dec 18 '13 at 11:02
$begingroup$
Thank you for this. I had not thought to formulate the question in terms of non-isomorphic graphs on $n$ vertices, although it seems so obvious now. Of course, for $nge2$, this number is out by one from the figure I'm looking for because the empty graph is the same as the complete graph for my purposes.
$endgroup$
– Clum
Mar 19 '13 at 13:23
$begingroup$
Thank you for this. I had not thought to formulate the question in terms of non-isomorphic graphs on $n$ vertices, although it seems so obvious now. Of course, for $nge2$, this number is out by one from the figure I'm looking for because the empty graph is the same as the complete graph for my purposes.
$endgroup$
– Clum
Mar 19 '13 at 13:23
$begingroup$
On further reflection, this statistic actually gives roughly twice the number of colourings, by symmetry. I'm going to sit and work out the precise relation.
$endgroup$
– Clum
Mar 19 '13 at 13:58
$begingroup$
On further reflection, this statistic actually gives roughly twice the number of colourings, by symmetry. I'm going to sit and work out the precise relation.
$endgroup$
– Clum
Mar 19 '13 at 13:58
$begingroup$
Here is another example where we use the Lovasz formula to calculate the cycle index of the symmetric group.
$endgroup$
– Marko Riedel
Oct 28 '13 at 11:46
$begingroup$
Here is another example where we use the Lovasz formula to calculate the cycle index of the symmetric group.
$endgroup$
– Marko Riedel
Oct 28 '13 at 11:46
$begingroup$
This example shows how to enumerate graphs with colored edges when there is in addition to the edge permutation group a group acting on the colors, further reducing the number of equivalence classes.
$endgroup$
– Marko Riedel
Dec 18 '13 at 11:02
$begingroup$
This example shows how to enumerate graphs with colored edges when there is in addition to the edge permutation group a group acting on the colors, further reducing the number of equivalence classes.
$endgroup$
– Marko Riedel
Dec 18 '13 at 11:02
add a comment |
$begingroup$
If you google on something like "clapham easier self-complementary graphs",
you'll be lead to a paper which enumerates self-complementary graphs. The number of isomorphism classes of graphs on $n$ vertices plus the number of isomorphism classes of self-complementary graphs is twice the number you are asking for.
Note that this enumeration was first carried out by R. C. Read; you'll find the citation in Clapham's paper.
edited Jan 11 '17 at 6:00
bof
52.5k558121
answered Feb 25 '13 at 22:26
Chris GodsilChris Godsil
11.7k21635
$endgroup$
add a comment |
$begingroup$
If you google on something like "clapham easier self-complementary graphs",
you'll be lead to a paper which enumerates self-complementary graphs. The number of isomorphism classes of graphs on $n$ vertices plus the number of isomorphism classes of self-complementary graphs is twice the number you are asking for.
Note that this enumeration was first carried out by R. C. Read; you'll find the citation in Clapham's paper.
edited Jan 11 '17 at 6:00
bof
52.5k558121
answered Feb 25 '13 at 22:26
Chris GodsilChris Godsil
11.7k21635
$endgroup$
add a comment |
$begingroup$
If you google on something like "clapham easier self-complementary graphs",
you'll be lead to a paper which enumerates self-complementary graphs. The number of isomorphism classes of graphs on $n$ vertices plus the number of isomorphism classes of self-complementary graphs is twice the number you are asking for.
Note that this enumeration was first carried out by R. C. Read; you'll find the citation in Clapham's paper.
edited Jan 11 '17 at 6:00
bof
52.5k558121
answered Feb 25 '13 at 22:26
Chris GodsilChris Godsil
11.7k21635
$endgroup$
If you google on something like "clapham easier self-complementary graphs",
you'll be lead to a paper which enumerates self-complementary graphs. The number of isomorphism classes of graphs on $n$ vertices plus the number of isomorphism classes of self-complementary graphs is twice the number you are asking for.
Note that this enumeration was first carried out by R. C. Read; you'll find the citation in Clapham's paper.
edited Jan 11 '17 at 6:00
bof
52.5k558121
answered Feb 25 '13 at 22:26
Chris GodsilChris Godsil
11.7k21635
edited Jan 11 '17 at 6:00
bof
52.5k558121
edited Jan 11 '17 at 6:00
bof
52.5k558121
edited Jan 11 '17 at 6:00
bof
52.5k558121
52.5k558121
answered Feb 25 '13 at 22:26
Chris GodsilChris Godsil
11.7k21635
answered Feb 25 '13 at 22:26
Chris GodsilChris Godsil
11.7k21635
answered Feb 25 '13 at 22:26
Chris GodsilChris Godsil
11.7k21635
11.7k21635
add a comment |
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%2f314103%2fhow-many-2-edge-colourings-of-k-n-are-there%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$
I haven't thought about this carefully--I'm at the dentist--but it seems to me that it might be easy to apply the Pólya-Burnside-Redfield-Cauchy-Frobenius counting lemma here, since the symmetry group of $K_n$ is so especially simple.
$endgroup$
– MJD
Feb 25 '13 at 17:42
1
$begingroup$
I do not see how this question can be answered until you explain what you mean by "essentially different".
$endgroup$
– Chris Godsil
Feb 25 '13 at 19:58
$begingroup$
Apologies. Two colourings would be "essentially the same" if a relabelling of the vertices of one would give the other, or if they were the same but with the colours switched. (I hesitate to say isomorphic for some reason but that's pretty much what I mean). For example, for a graph of any order, there is only one "essentially different" map that gives colour 1 to precisely one edge and colour 2 to all others.
$endgroup$
– Clum
Feb 25 '13 at 20:56