Isomorphisms between regular graphs of same degreeHow 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

After Brexit, will the EU recognize British passports that are valid for more than ten years?

Is there a math expression equivalent to the conditional ternary operator?

Short story about an infectious indestructible metal bar?

Why does a car's steering wheel get lighter with increasing speed

Why do we call complex numbers “numbers” but we don’t consider 2-vectors numbers?

Book where society has been split into 2 with a wall down the middle where one side embraced high tech whereas other side were totally against tech

Having the player face themselves after the mid-game

Why restrict private health insurance?

How do you make a gun that shoots melee weapons and/or swords?

I am the light that shines in the dark

A running toilet that stops itself

How to install "rounded" brake pads

Why aren't there more Gauls like Obelix?

Should we avoid writing fiction about historical events without extensive research?

Why would /etc/passwd be used every time someone executes `ls -l` command?

Does the US political system, in principle, allow for a no-party system?

Is it appropriate to ask a former professor to order a library book for me through ILL?

Limpar string com Regex

Can multiple states demand income tax from an LLC?

An Undercover Army

Use Mercury as quenching liquid for swords?

Is "cogitate" used appropriately in "I cogitate that success relies on hard work"?

Who has more? Ireland or Iceland?

Ultrafilters as a double dual



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|$)?










share|cite|improve this question











$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
    2 days ago















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|$)?










share|cite|improve this question











$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
    2 days ago













2












2








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|$)?










share|cite|improve this question











$endgroup$




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















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited 2 days ago









dkaeae

1,981721




1,981721










asked 2 days ago









Jim NewtonJim Newton

1107




1107











  • $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
    2 days ago
















  • $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
    2 days ago















$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
2 days ago




$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
2 days ago










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









$endgroup$




















    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











    $endgroup$












      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


















      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















      Required, but never shown

























      2 Answers
      2






      active

      oldest

      votes








      2 Answers
      2






      active

      oldest

      votes









      active

      oldest

      votes






      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









      $endgroup$

















        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









        $endgroup$















          4












          4








          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









          $endgroup$



          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












          share|cite|improve this answer



          share|cite|improve this answer










          answered 2 days ago









          David RicherbyDavid Richerby

          68k15102193




          68k15102193





















              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











              $endgroup$

















                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











                $endgroup$















                  4












                  4








                  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











                  $endgroup$



                  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














                  share|cite|improve this answer



                  share|cite|improve this answer








                  edited 2 days ago

























                  answered 2 days ago









                  dkaeaedkaeae

                  1,981721




                  1,981721



























                      draft saved

                      draft discarded
















































                      Thanks for contributing an answer to Computer Science 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.




                      draft saved


                      draft discarded














                      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















                      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







                      Popular posts from this blog

                      Identity Server 4 is not redirecting to Angular app after login2019 Community Moderator ElectionIdentity Server 4 and dockerIdentityserver implicit flow unauthorized_clientIdentityServer Hybrid Flow - Access Token is null after user successful loginIdentity Server to MVC client : Page Redirect After loginLogin with Steam OpenId(oidc-client-js)Identity Server 4+.NET Core 2.0 + IdentityIdentityServer4 post-login redirect not working in Edge browserCall to IdentityServer4 generates System.NullReferenceException: Object reference not set to an instance of an objectIdentityServer4 without HTTPS not workingHow to get Authorization code from identity server without login form

                      2005 Ahvaz unrest Contents Background Causes Casualties Aftermath See also References Navigation menue"At Least 10 Are Killed by Bombs in Iran""Iran"Archived"Arab-Iranians in Iran to make April 15 'Day of Fury'"State of Mind, State of Order: Reactions to Ethnic Unrest in the Islamic Republic of Iran.10.1111/j.1754-9469.2008.00028.x"Iran hangs Arab separatists"Iran Overview from ArchivedConstitution of the Islamic Republic of Iran"Tehran puzzled by forged 'riots' letter""Iran and its minorities: Down in the second class""Iran: Handling Of Ahvaz Unrest Could End With Televised Confessions""Bombings Rock Iran Ahead of Election""Five die in Iran ethnic clashes""Iran: Need for restraint as anniversary of unrest in Khuzestan approaches"Archived"Iranian Sunni protesters killed in clashes with security forces"Archived

                      Can't initialize raids on a new ASUS Prime B360M-A motherboard2019 Community Moderator ElectionSimilar to RAID config yet more like mirroring solution?Can't get motherboard serial numberWhy does the BIOS entry point start with a WBINVD instruction?UEFI performance Asus Maximus V Extreme