Automorphisms, order and degree uniquely determine a regular graphThe existence and uniqueness of a strongly regular graph of order 100 and degree 22.Graph isomorphism and existence of nontrivial automorphismsGive an example of 2 non isomorphic regular tournament of the same orderWhy this graph has automorphism group is isomorphic to the cyclic group of order 4?Get degree distribution of a graph from its Adjacency matrixFinding Automorphisms of Irregular graph through Regular Sub-Graphs.Non-regular Expander graph ?!Prove that a regular graph of degree 5 cannot be decomposed into subgraphs, each isomorphic to a path of length sixAutomorphisms of cospectral k-regular graphsDegree of quotient graph of a regular graph
Is it true that good novels will automatically sell themselves on Amazon (and so on) and there is no need for one to waste time promoting?
Why does overlay work only on the first tcolorbox?
Planetary tidal locking causing asymetrical water distribution
Violin - Can double stops be played when the strings are not next to each other?
PTIJ: Who should I vote for? (21st Knesset Edition)
How do I hide Chekhov's Gun?
Does this sum go infinity?
Bacteria contamination inside a thermos bottle
Why does energy conservation give me the wrong answer in this inelastic collision problem?
I got the following comment from a reputed math journal. What does it mean?
How could a scammer know the apps on my phone / iTunes account?
How difficult is it to simply disable/disengage the MCAS on Boeing 737 Max 8 & 9 Aircraft?
Simplify an interface for flexibly applying rules to periods of time
Why is a white electrical wire connected to 2 black wires?
Math equation in non italic font
Have the tides ever turned twice on any open problem?
Equivalents to the present tense
Examples of transfinite towers
Are relativity and doppler effect related?
How to terminate ping <dest> &
New passport but visa is in old (lost) passport
How could an airship be repaired midflight?
Did Ender ever learn that he killed Stilson and/or Bonzo?
What did “the good wine” (τὸν καλὸν οἶνον) mean in John 2:10?
Automorphisms, order and degree uniquely determine a regular graph
The existence and uniqueness of a strongly regular graph of order 100 and degree 22.Graph isomorphism and existence of nontrivial automorphismsGive an example of 2 non isomorphic regular tournament of the same orderWhy this graph has automorphism group is isomorphic to the cyclic group of order 4?Get degree distribution of a graph from its Adjacency matrixFinding Automorphisms of Irregular graph through Regular Sub-Graphs.Non-regular Expander graph ?!Prove that a regular graph of degree 5 cannot be decomposed into subgraphs, each isomorphic to a path of length sixAutomorphisms of cospectral k-regular graphsDegree of quotient graph of a regular graph
$begingroup$
Does Automorphism group combined with the order and degree uniquely determine any regular graph? What about any (non-regular) graph?
I think yes, because the automorphism contain within them the adjacency relations, which, I think could be decoded given the order and degree of the graph. Are there any two graphs that have the same automorphism group, order and degree but are not isomorphic? Thanks beforehand.
combinatorics graph-theory automorphism-group cayley-graphs
asked Mar 12 at 9:25
vidyarthividyarthi
3,0341833
$endgroup$
add a comment |
$begingroup$
Does Automorphism group combined with the order and degree uniquely determine any regular graph? What about any (non-regular) graph?
I think yes, because the automorphism contain within them the adjacency relations, which, I think could be decoded given the order and degree of the graph. Are there any two graphs that have the same automorphism group, order and degree but are not isomorphic? Thanks beforehand.
combinatorics graph-theory automorphism-group cayley-graphs
asked Mar 12 at 9:25
vidyarthividyarthi
3,0341833
$endgroup$
add a comment |
$begingroup$
Does Automorphism group combined with the order and degree uniquely determine any regular graph? What about any (non-regular) graph?
I think yes, because the automorphism contain within them the adjacency relations, which, I think could be decoded given the order and degree of the graph. Are there any two graphs that have the same automorphism group, order and degree but are not isomorphic? Thanks beforehand.
combinatorics graph-theory automorphism-group cayley-graphs
asked Mar 12 at 9:25
vidyarthividyarthi
3,0341833
$endgroup$
Does Automorphism group combined with the order and degree uniquely determine any regular graph? What about any (non-regular) graph?
I think yes, because the automorphism contain within them the adjacency relations, which, I think could be decoded given the order and degree of the graph. Are there any two graphs that have the same automorphism group, order and degree but are not isomorphic? Thanks beforehand.
combinatorics graph-theory automorphism-group cayley-graphs
combinatorics graph-theory automorphism-group cayley-graphs
asked Mar 12 at 9:25
vidyarthividyarthi
3,0341833
asked Mar 12 at 9:25
vidyarthividyarthi
3,0341833
asked Mar 12 at 9:25
vidyarthividyarthi
3,0341833
asked Mar 12 at 9:25
vidyarthividyarthi
3,0341833
asked Mar 12 at 9:25
vidyarthividyarthi
3,0341833
3,0341833
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Non-regular? No. The two following graphs both have the same list of degrees ($3,2cdot 5, 1cdot 3$) and the same automorphism group (the trivial group):
$G_1$: Edges A-B, A-C-D, A-E-F-G-H-I.
$G_2$: Edges A-B, A-C-D-E, A-F-G-H-I.
In each case, an automorphism must fix the lone vertex of order 3, and send each chain heading away from that vertex to a chain of the same length. Within each groups, the chains have different lengths and must therefore each be fixed. Between the two groups, the list of chain lengths is different.
Regular? No. The two following groups have the same number of vertices ($19$), the same common degree ($4$), and the same automorphism group (dihedral):
$G_3$: The vertices are the integers mod $19$. There is an edge between $m$ and $n$ if and only if $m-nin -2,-1,1,2$ mod $19$. The triangles including $0$ are $0,1,2$, $-1,0,1$, and $-2,-1,0$, so edges $(k,k+1)$ are the only ones in two triangles each and can be distinguished from edges $(k,k+2)$.
$G_4$: The vertices are the integers mod $19$. There is an edge between $m$ and $n$ if and only if $m-nin -3,-1,1,3$ mod $19$. The quadrilaterals including $0$ are $(0,1,2,3)$, $(0,1,4,3)$, $(0,3,2,-1)$, $(0,1,2,-1)$, $(0,1,-2,-3)$, $(0,1,-2,-1)$, $(0,-1,-2,-3)$, and $(0,-1,-4,-3)$. Edges $(k,k+1)$ are in five quadrilaterals each, while edges $(k,k+3)$ are in three quadrilaterals each, so we can distinguish between them.
In each case, we can distinguish between edges of the type $(k,k+1)$ and the other type present. Each automorphism group must therefore be contained in the automorphism group of the subgraph of just those edges - which is the dihedral group $D_19$. A quick check verifies that everything in that dihedral group is in fact an automorphism of each of these groups, and we're done.
answered Mar 12 at 10:04
jmerryjmerry
14.4k1629
$endgroup$
$begingroup$
Thanks! The last two graphs were circulant graphs, right? So, is there any extra criterion required to uniquely determine the graph along the three parameters I mentioned?
$endgroup$
– vidyarthi
Mar 12 at 10:10
$begingroup$
Probably nothing practical. I just invented these examples off the top of my head. Oh, and there's nothing special about 19 there, other than being big enough. Anything greater than 12 definitely works.
$endgroup$
– jmerry
Mar 12 at 10:14
$begingroup$
But those two last graphs are circulant graphs. Anyways, so is there no criterion except perfect isomorphism to completely determine a graph, I mean is there no extra parameter except isomorphism that can be added to the parameters I gave to make it equivalent to isomorphism?
$endgroup$
– vidyarthi
Mar 12 at 10:18
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%2f3144864%2fautomorphisms-order-and-degree-uniquely-determine-a-regular-graph%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$
Non-regular? No. The two following graphs both have the same list of degrees ($3,2cdot 5, 1cdot 3$) and the same automorphism group (the trivial group):
$G_1$: Edges A-B, A-C-D, A-E-F-G-H-I.
$G_2$: Edges A-B, A-C-D-E, A-F-G-H-I.
In each case, an automorphism must fix the lone vertex of order 3, and send each chain heading away from that vertex to a chain of the same length. Within each groups, the chains have different lengths and must therefore each be fixed. Between the two groups, the list of chain lengths is different.
Regular? No. The two following groups have the same number of vertices ($19$), the same common degree ($4$), and the same automorphism group (dihedral):
$G_3$: The vertices are the integers mod $19$. There is an edge between $m$ and $n$ if and only if $m-nin -2,-1,1,2$ mod $19$. The triangles including $0$ are $0,1,2$, $-1,0,1$, and $-2,-1,0$, so edges $(k,k+1)$ are the only ones in two triangles each and can be distinguished from edges $(k,k+2)$.
$G_4$: The vertices are the integers mod $19$. There is an edge between $m$ and $n$ if and only if $m-nin -3,-1,1,3$ mod $19$. The quadrilaterals including $0$ are $(0,1,2,3)$, $(0,1,4,3)$, $(0,3,2,-1)$, $(0,1,2,-1)$, $(0,1,-2,-3)$, $(0,1,-2,-1)$, $(0,-1,-2,-3)$, and $(0,-1,-4,-3)$. Edges $(k,k+1)$ are in five quadrilaterals each, while edges $(k,k+3)$ are in three quadrilaterals each, so we can distinguish between them.
In each case, we can distinguish between edges of the type $(k,k+1)$ and the other type present. Each automorphism group must therefore be contained in the automorphism group of the subgraph of just those edges - which is the dihedral group $D_19$. A quick check verifies that everything in that dihedral group is in fact an automorphism of each of these groups, and we're done.
answered Mar 12 at 10:04
jmerryjmerry
14.4k1629
$endgroup$
$begingroup$
Thanks! The last two graphs were circulant graphs, right? So, is there any extra criterion required to uniquely determine the graph along the three parameters I mentioned?
$endgroup$
– vidyarthi
Mar 12 at 10:10
$begingroup$
Probably nothing practical. I just invented these examples off the top of my head. Oh, and there's nothing special about 19 there, other than being big enough. Anything greater than 12 definitely works.
$endgroup$
– jmerry
Mar 12 at 10:14
$begingroup$
But those two last graphs are circulant graphs. Anyways, so is there no criterion except perfect isomorphism to completely determine a graph, I mean is there no extra parameter except isomorphism that can be added to the parameters I gave to make it equivalent to isomorphism?
$endgroup$
– vidyarthi
Mar 12 at 10:18
add a comment |
$begingroup$
Non-regular? No. The two following graphs both have the same list of degrees ($3,2cdot 5, 1cdot 3$) and the same automorphism group (the trivial group):
$G_1$: Edges A-B, A-C-D, A-E-F-G-H-I.
$G_2$: Edges A-B, A-C-D-E, A-F-G-H-I.
In each case, an automorphism must fix the lone vertex of order 3, and send each chain heading away from that vertex to a chain of the same length. Within each groups, the chains have different lengths and must therefore each be fixed. Between the two groups, the list of chain lengths is different.
Regular? No. The two following groups have the same number of vertices ($19$), the same common degree ($4$), and the same automorphism group (dihedral):
$G_3$: The vertices are the integers mod $19$. There is an edge between $m$ and $n$ if and only if $m-nin -2,-1,1,2$ mod $19$. The triangles including $0$ are $0,1,2$, $-1,0,1$, and $-2,-1,0$, so edges $(k,k+1)$ are the only ones in two triangles each and can be distinguished from edges $(k,k+2)$.
$G_4$: The vertices are the integers mod $19$. There is an edge between $m$ and $n$ if and only if $m-nin -3,-1,1,3$ mod $19$. The quadrilaterals including $0$ are $(0,1,2,3)$, $(0,1,4,3)$, $(0,3,2,-1)$, $(0,1,2,-1)$, $(0,1,-2,-3)$, $(0,1,-2,-1)$, $(0,-1,-2,-3)$, and $(0,-1,-4,-3)$. Edges $(k,k+1)$ are in five quadrilaterals each, while edges $(k,k+3)$ are in three quadrilaterals each, so we can distinguish between them.
In each case, we can distinguish between edges of the type $(k,k+1)$ and the other type present. Each automorphism group must therefore be contained in the automorphism group of the subgraph of just those edges - which is the dihedral group $D_19$. A quick check verifies that everything in that dihedral group is in fact an automorphism of each of these groups, and we're done.
answered Mar 12 at 10:04
jmerryjmerry
14.4k1629
$endgroup$
$begingroup$
Thanks! The last two graphs were circulant graphs, right? So, is there any extra criterion required to uniquely determine the graph along the three parameters I mentioned?
$endgroup$
– vidyarthi
Mar 12 at 10:10
$begingroup$
Probably nothing practical. I just invented these examples off the top of my head. Oh, and there's nothing special about 19 there, other than being big enough. Anything greater than 12 definitely works.
$endgroup$
– jmerry
Mar 12 at 10:14
$begingroup$
But those two last graphs are circulant graphs. Anyways, so is there no criterion except perfect isomorphism to completely determine a graph, I mean is there no extra parameter except isomorphism that can be added to the parameters I gave to make it equivalent to isomorphism?
$endgroup$
– vidyarthi
Mar 12 at 10:18
add a comment |
$begingroup$
Non-regular? No. The two following graphs both have the same list of degrees ($3,2cdot 5, 1cdot 3$) and the same automorphism group (the trivial group):
$G_1$: Edges A-B, A-C-D, A-E-F-G-H-I.
$G_2$: Edges A-B, A-C-D-E, A-F-G-H-I.
In each case, an automorphism must fix the lone vertex of order 3, and send each chain heading away from that vertex to a chain of the same length. Within each groups, the chains have different lengths and must therefore each be fixed. Between the two groups, the list of chain lengths is different.
Regular? No. The two following groups have the same number of vertices ($19$), the same common degree ($4$), and the same automorphism group (dihedral):
$G_3$: The vertices are the integers mod $19$. There is an edge between $m$ and $n$ if and only if $m-nin -2,-1,1,2$ mod $19$. The triangles including $0$ are $0,1,2$, $-1,0,1$, and $-2,-1,0$, so edges $(k,k+1)$ are the only ones in two triangles each and can be distinguished from edges $(k,k+2)$.
$G_4$: The vertices are the integers mod $19$. There is an edge between $m$ and $n$ if and only if $m-nin -3,-1,1,3$ mod $19$. The quadrilaterals including $0$ are $(0,1,2,3)$, $(0,1,4,3)$, $(0,3,2,-1)$, $(0,1,2,-1)$, $(0,1,-2,-3)$, $(0,1,-2,-1)$, $(0,-1,-2,-3)$, and $(0,-1,-4,-3)$. Edges $(k,k+1)$ are in five quadrilaterals each, while edges $(k,k+3)$ are in three quadrilaterals each, so we can distinguish between them.
In each case, we can distinguish between edges of the type $(k,k+1)$ and the other type present. Each automorphism group must therefore be contained in the automorphism group of the subgraph of just those edges - which is the dihedral group $D_19$. A quick check verifies that everything in that dihedral group is in fact an automorphism of each of these groups, and we're done.
answered Mar 12 at 10:04
jmerryjmerry
14.4k1629
$endgroup$
Non-regular? No. The two following graphs both have the same list of degrees ($3,2cdot 5, 1cdot 3$) and the same automorphism group (the trivial group):
$G_1$: Edges A-B, A-C-D, A-E-F-G-H-I.
$G_2$: Edges A-B, A-C-D-E, A-F-G-H-I.
In each case, an automorphism must fix the lone vertex of order 3, and send each chain heading away from that vertex to a chain of the same length. Within each groups, the chains have different lengths and must therefore each be fixed. Between the two groups, the list of chain lengths is different.
Regular? No. The two following groups have the same number of vertices ($19$), the same common degree ($4$), and the same automorphism group (dihedral):
$G_3$: The vertices are the integers mod $19$. There is an edge between $m$ and $n$ if and only if $m-nin -2,-1,1,2$ mod $19$. The triangles including $0$ are $0,1,2$, $-1,0,1$, and $-2,-1,0$, so edges $(k,k+1)$ are the only ones in two triangles each and can be distinguished from edges $(k,k+2)$.
$G_4$: The vertices are the integers mod $19$. There is an edge between $m$ and $n$ if and only if $m-nin -3,-1,1,3$ mod $19$. The quadrilaterals including $0$ are $(0,1,2,3)$, $(0,1,4,3)$, $(0,3,2,-1)$, $(0,1,2,-1)$, $(0,1,-2,-3)$, $(0,1,-2,-1)$, $(0,-1,-2,-3)$, and $(0,-1,-4,-3)$. Edges $(k,k+1)$ are in five quadrilaterals each, while edges $(k,k+3)$ are in three quadrilaterals each, so we can distinguish between them.
In each case, we can distinguish between edges of the type $(k,k+1)$ and the other type present. Each automorphism group must therefore be contained in the automorphism group of the subgraph of just those edges - which is the dihedral group $D_19$. A quick check verifies that everything in that dihedral group is in fact an automorphism of each of these groups, and we're done.
answered Mar 12 at 10:04
jmerryjmerry
14.4k1629
answered Mar 12 at 10:04
jmerryjmerry
14.4k1629
answered Mar 12 at 10:04
jmerryjmerry
14.4k1629
answered Mar 12 at 10:04
jmerryjmerry
14.4k1629
14.4k1629
$begingroup$
Thanks! The last two graphs were circulant graphs, right? So, is there any extra criterion required to uniquely determine the graph along the three parameters I mentioned?
$endgroup$
– vidyarthi
Mar 12 at 10:10
$begingroup$
Probably nothing practical. I just invented these examples off the top of my head. Oh, and there's nothing special about 19 there, other than being big enough. Anything greater than 12 definitely works.
$endgroup$
– jmerry
Mar 12 at 10:14
$begingroup$
But those two last graphs are circulant graphs. Anyways, so is there no criterion except perfect isomorphism to completely determine a graph, I mean is there no extra parameter except isomorphism that can be added to the parameters I gave to make it equivalent to isomorphism?
$endgroup$
– vidyarthi
Mar 12 at 10:18
add a comment |
$begingroup$
Thanks! The last two graphs were circulant graphs, right? So, is there any extra criterion required to uniquely determine the graph along the three parameters I mentioned?
$endgroup$
– vidyarthi
Mar 12 at 10:10
$begingroup$
Probably nothing practical. I just invented these examples off the top of my head. Oh, and there's nothing special about 19 there, other than being big enough. Anything greater than 12 definitely works.
$endgroup$
– jmerry
Mar 12 at 10:14
$begingroup$
But those two last graphs are circulant graphs. Anyways, so is there no criterion except perfect isomorphism to completely determine a graph, I mean is there no extra parameter except isomorphism that can be added to the parameters I gave to make it equivalent to isomorphism?
$endgroup$
– vidyarthi
Mar 12 at 10:18
$begingroup$
Thanks! The last two graphs were circulant graphs, right? So, is there any extra criterion required to uniquely determine the graph along the three parameters I mentioned?
$endgroup$
– vidyarthi
Mar 12 at 10:10
$begingroup$
Thanks! The last two graphs were circulant graphs, right? So, is there any extra criterion required to uniquely determine the graph along the three parameters I mentioned?
$endgroup$
– vidyarthi
Mar 12 at 10:10
$begingroup$
Probably nothing practical. I just invented these examples off the top of my head. Oh, and there's nothing special about 19 there, other than being big enough. Anything greater than 12 definitely works.
$endgroup$
– jmerry
Mar 12 at 10:14
$begingroup$
Probably nothing practical. I just invented these examples off the top of my head. Oh, and there's nothing special about 19 there, other than being big enough. Anything greater than 12 definitely works.
$endgroup$
– jmerry
Mar 12 at 10:14
$begingroup$
But those two last graphs are circulant graphs. Anyways, so is there no criterion except perfect isomorphism to completely determine a graph, I mean is there no extra parameter except isomorphism that can be added to the parameters I gave to make it equivalent to isomorphism?
$endgroup$
– vidyarthi
Mar 12 at 10:18
$begingroup$
But those two last graphs are circulant graphs. Anyways, so is there no criterion except perfect isomorphism to completely determine a graph, I mean is there no extra parameter except isomorphism that can be added to the parameters I gave to make it equivalent to isomorphism?
$endgroup$
– vidyarthi
Mar 12 at 10:18
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%2f3144864%2fautomorphisms-order-and-degree-uniquely-determine-a-regular-graph%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
