Ufdjrw

How to write a chaotic neutral protagonist and prevent my readers from thinking they are evil?

I can't die. Who am I?

How to resolve: Reviewer #1 says remove section X vs. Reviewer #2 says expand section X

Having the player face themselves after the mid-game

What is better: yes / no radio, or simple checkbox?

What can I do if someone tampers with my SSH public key?

What ability score modifier does a javelin's damage use?

I reported the illegal activity of my boss to his boss. My boss found out. Now I am being punished. What should I do?

Recommendation letter by significant other if you worked with them professionally?

Do items de-spawn?

What will happen if my luggage gets delayed?

School performs periodic password audits. Is my password compromised?

Is it a Cyclops number? "Nobody" knows!

Why does Central Limit Theorem break down in my simulation?

Is this Paypal Github SDK reference really a dangerous site?

What problems would a superhuman have who's skin is constantly hot?

How to draw dashed arc of a circle behind pyramid?

Doesn't allowing a user mode program to access kernel space memory and execute the IN and OUT instructions defeat the purpose of having CPU modes?

Would an aboleth's Phantasmal Force lair action be affected by Counterspell, Dispel Magic, and/or Slow?

When Schnorr signatures are part of Bitcoin will it be possible validate each block with only one signature validation?

Why is there an extra space when I type "ls" in the Desktop directory?

Is divide-by-zero a security vulnerability?

Shifting between bemols (flats) and diesis (sharps)in the key signature

Help find my computational error for logarithms

Isomorphisms between regular graphs of same degree

How to show that all 2-terminal SP-graphs are O(log n)-outer-planarEnumerate all non-isomorphic graphs of a certain sizeTo detect isomorphic graphs Is it enough to check if they have the same number of same degree vertices?Enumerate all non-isomorphic graphs of size ncounterexample for this graph isomorphism algorithmFind all non-isomorphic graphs with a particular degree sequenceGenerating all directed acyclic graphs with constraintsGenerate all non-isomorphic bounded-degree rooted graphs of bounded radiusHow similar is the Goldwasser-Sipser Set Lower Bound Protocol to the Hashcash/Bitcoin Proof-of-Work?Proof that locality is sufficient in showing two graphs are isomorphic

2

$begingroup$

Are all $n$-vertex regular graphs of degree $d$ isomorphic?

Can someone provide an example of two non-isomorphic graphs $G_1$ and $G_2$ which are both regular with degree $d$ and have the same number of vertices (i.e., $|G_1| = |G_2|$)?

graph-theory graph-isomorphism

share|cite|improve this question

edited Mar 6 at 13:51

dkaeae

1,996721

asked Mar 6 at 9:38

Jim NewtonJim Newton

1107

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Yes indeed, but clearly regular graphs of degree 2 are not isomorphic to regular graphs of degree 3. So I'm asking about regular graphs of the same degree, if they have the same number of vertices, are they necessarily isomorphic?
  $endgroup$
  – Jim Newton
  Mar 6 at 12:37
  

  
  
  
  

add a comment | 

2

$begingroup$

Are all $n$-vertex regular graphs of degree $d$ isomorphic?

Can someone provide an example of two non-isomorphic graphs $G_1$ and $G_2$ which are both regular with degree $d$ and have the same number of vertices (i.e., $|G_1| = |G_2|$)?

graph-theory graph-isomorphism

share|cite|improve this question

edited Mar 6 at 13:51

dkaeae

1,996721

asked Mar 6 at 9:38

Jim NewtonJim Newton

1107

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Yes indeed, but clearly regular graphs of degree 2 are not isomorphic to regular graphs of degree 3. So I'm asking about regular graphs of the same degree, if they have the same number of vertices, are they necessarily isomorphic?
  $endgroup$
  – Jim Newton
  Mar 6 at 12:37
  

  
  
  
  

add a comment | 

$begingroup$

Are all $n$-vertex regular graphs of degree $d$ isomorphic?

Can someone provide an example of two non-isomorphic graphs $G_1$ and $G_2$ which are both regular with degree $d$ and have the same number of vertices (i.e., $|G_1| = |G_2|$)?

graph-theory graph-isomorphism

share|cite|improve this question

edited Mar 6 at 13:51

dkaeae

1,996721

asked Mar 6 at 9:38

Jim NewtonJim Newton

1107

$endgroup$

share|cite|improve this question

edited Mar 6 at 13:51

dkaeae

1,996721

asked Mar 6 at 9:38

Jim NewtonJim Newton

1107

share|cite|improve this question

edited Mar 6 at 13:51

dkaeae

1,996721

asked Mar 6 at 9:38

Jim NewtonJim Newton

1107

edited Mar 6 at 13:51

dkaeae

1,996721

edited Mar 6 at 13:51

dkaeae

1,996721

asked Mar 6 at 9:38

Jim NewtonJim Newton

1107

asked Mar 6 at 9:38

Jim NewtonJim Newton

1107

2 Answers
2

active

oldest

votes

4

$begingroup$

Playing around with a pencil and paper for a few minutes, it should be easy to come up with non-isomorphic $d$-regular graphs with the same number of vertices, for small $d$. For example, take two cycles of length $2n$ and connect chords across them in different ways.

However, there is a polynomial-time isomorphism algorithm for any class of graphs of bounded degree, which includes the $d$-regular graphs for any fixed $d$. It's due to Luks (Isomorphism of graphs of bounded valence can be tested in polynomial time, Journal of Computer and System Sciences 25(1):42–65, 1982) and uses a bunch of group theory.

share|cite|improve this answer

answered Mar 6 at 13:56

David RicherbyDavid Richerby

68.2k15103194

$endgroup$

add a comment | 

4

$begingroup$

Of course not.

Consider, for example, the cycle $C_6$ with six vertices and the graph obtained by the union of two copies of $C_3$. Then both are 2-regular, but they are obviously not isomorphic.

This is also the case if we restrict the question to connected graphs. Consider, for instance, the following two 3-regular graphs:

                                                

You can see they are not isomorphic because the second one contains cycles with six vertices that have chords; this is impossible in the first graph since it has precisely four six-cycles and you can see none of them have chords. (Or even easier: The second one has a five cycle, whereas the first one has only cycles with three, four, six, or more vertices.)

What you might be able to prove is that all 2-regular and connected graphs are isomorphic (see, e.g., this), but this is a big restriction compared to the original question.

share|cite|improve this answer

edited Mar 6 at 13:17

answered Mar 6 at 12:48

dkaeaedkaeae

1,996721

$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: "419"
;
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: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
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
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

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

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f105214%2fisomorphisms-between-regular-graphs-of-same-degree%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

4

$begingroup$

Playing around with a pencil and paper for a few minutes, it should be easy to come up with non-isomorphic $d$-regular graphs with the same number of vertices, for small $d$. For example, take two cycles of length $2n$ and connect chords across them in different ways.

However, there is a polynomial-time isomorphism algorithm for any class of graphs of bounded degree, which includes the $d$-regular graphs for any fixed $d$. It's due to Luks (Isomorphism of graphs of bounded valence can be tested in polynomial time, Journal of Computer and System Sciences 25(1):42–65, 1982) and uses a bunch of group theory.

share|cite|improve this answer

answered Mar 6 at 13:56

David RicherbyDavid Richerby

68.2k15103194

$endgroup$

add a comment | 

4

$begingroup$

Playing around with a pencil and paper for a few minutes, it should be easy to come up with non-isomorphic $d$-regular graphs with the same number of vertices, for small $d$. For example, take two cycles of length $2n$ and connect chords across them in different ways.

However, there is a polynomial-time isomorphism algorithm for any class of graphs of bounded degree, which includes the $d$-regular graphs for any fixed $d$. It's due to Luks (Isomorphism of graphs of bounded valence can be tested in polynomial time, Journal of Computer and System Sciences 25(1):42–65, 1982) and uses a bunch of group theory.

share|cite|improve this answer

answered Mar 6 at 13:56

David RicherbyDavid Richerby

68.2k15103194

$endgroup$

add a comment | 

$begingroup$

Playing around with a pencil and paper for a few minutes, it should be easy to come up with non-isomorphic $d$-regular graphs with the same number of vertices, for small $d$. For example, take two cycles of length $2n$ and connect chords across them in different ways.

However, there is a polynomial-time isomorphism algorithm for any class of graphs of bounded degree, which includes the $d$-regular graphs for any fixed $d$. It's due to Luks (Isomorphism of graphs of bounded valence can be tested in polynomial time, Journal of Computer and System Sciences 25(1):42–65, 1982) and uses a bunch of group theory.

share|cite|improve this answer

answered Mar 6 at 13:56

David RicherbyDavid Richerby

68.2k15103194

$endgroup$

share|cite|improve this answer

answered Mar 6 at 13:56

David RicherbyDavid Richerby

68.2k15103194

answered Mar 6 at 13:56

David RicherbyDavid Richerby

68.2k15103194

answered Mar 6 at 13:56

David RicherbyDavid Richerby

68.2k15103194

4

$begingroup$

Of course not.

Consider, for example, the cycle $C_6$ with six vertices and the graph obtained by the union of two copies of $C_3$. Then both are 2-regular, but they are obviously not isomorphic.

This is also the case if we restrict the question to connected graphs. Consider, for instance, the following two 3-regular graphs:

                                                

You can see they are not isomorphic because the second one contains cycles with six vertices that have chords; this is impossible in the first graph since it has precisely four six-cycles and you can see none of them have chords. (Or even easier: The second one has a five cycle, whereas the first one has only cycles with three, four, six, or more vertices.)

What you might be able to prove is that all 2-regular and connected graphs are isomorphic (see, e.g., this), but this is a big restriction compared to the original question.

share|cite|improve this answer

edited Mar 6 at 13:17

answered Mar 6 at 12:48

dkaeaedkaeae

1,996721

$endgroup$

add a comment | 

4

$begingroup$

Of course not.

Consider, for example, the cycle $C_6$ with six vertices and the graph obtained by the union of two copies of $C_3$. Then both are 2-regular, but they are obviously not isomorphic.

This is also the case if we restrict the question to connected graphs. Consider, for instance, the following two 3-regular graphs:

                                                

You can see they are not isomorphic because the second one contains cycles with six vertices that have chords; this is impossible in the first graph since it has precisely four six-cycles and you can see none of them have chords. (Or even easier: The second one has a five cycle, whereas the first one has only cycles with three, four, six, or more vertices.)

What you might be able to prove is that all 2-regular and connected graphs are isomorphic (see, e.g., this), but this is a big restriction compared to the original question.

share|cite|improve this answer

edited Mar 6 at 13:17

answered Mar 6 at 12:48

dkaeaedkaeae

1,996721

$endgroup$

add a comment | 

$begingroup$

Of course not.

Consider, for example, the cycle $C_6$ with six vertices and the graph obtained by the union of two copies of $C_3$. Then both are 2-regular, but they are obviously not isomorphic.

This is also the case if we restrict the question to connected graphs. Consider, for instance, the following two 3-regular graphs:

                                                

You can see they are not isomorphic because the second one contains cycles with six vertices that have chords; this is impossible in the first graph since it has precisely four six-cycles and you can see none of them have chords. (Or even easier: The second one has a five cycle, whereas the first one has only cycles with three, four, six, or more vertices.)

What you might be able to prove is that all 2-regular and connected graphs are isomorphic (see, e.g., this), but this is a big restriction compared to the original question.

share|cite|improve this answer

edited Mar 6 at 13:17

answered Mar 6 at 12:48

dkaeaedkaeae

1,996721

$endgroup$

share|cite|improve this answer

edited Mar 6 at 13:17

answered Mar 6 at 12:48

dkaeaedkaeae

1,996721

answered Mar 6 at 12:48

dkaeaedkaeae

1,996721

answered Mar 6 at 12:48

dkaeaedkaeae

1,996721