Isomorphisms between regular graphs of same degree












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











$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
    yesterday
















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











$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
    yesterday














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






graph-theory graph-isomorphism







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




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 yesterday









dkaeae

1,971721




1,971721










asked yesterday









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
    yesterday


















  • $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
    yesterday
















$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
yesterday




$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
yesterday










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 yesterday









          David RicherbyDavid Richerby

          67.9k15102193




          67.9k15102193























              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 yesterday

























                  answered yesterday









                  dkaeaedkaeae

                  1,971721




                  1,971721






























                      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

                      How to label and detect the document text images

                      Image
                      1 $begingroup$ This is what I mean as document text image: I want to label the texts in image as separate blocks and my model should detect these labels as classes. NOTE: This is how the end result should be like: The labels like Block 1, Block 2, Block 3,.. should be Logo, Title, Date,.. Others, etc. Work done: First approach : I tried to implement this method via Object Detection, it didn't work. It didn't even detect any text. Second approach : Then I tried it using PixelLink. As this model is build for scene text detection, it detected each and every text in the image. But this method can detect multiple lines of text if the threshold values are increased. But I have no idea how do I add labels to the text blocks. PIXEL_CLS_WEIGHT_all_ones = 'PIXEL_CLS_WEIGHT_all_ones' PIXEL_C
                      Read more

                      Vallis Paradisi

                      Image
                      Coordinata: .mw-parser-output .geo-default,.mw-parser-output .geo-dms,.mw-parser-output .geo-dec{display:inline}.mw-parser-output .geo-nondefault,.mw-parser-output .geo-multi-punct{display:none}.mw-parser-output .longitude,.mw-parser-output .latitude{white-space:nowrap} 33°03′S 71°37′W  /  33.05°S 71.617°W  / -33.05; -71.617 Vallis Paradisi Res apud Vicidata repertae: Civitas : Chilia Numerus incolarum : 296 655 Zona horaria : UTC-4 Situs interretialis Nomen officiale : Valparaíso Gubernium Consilium : municipal council of Valparaíso Geographia Superficies : 401 600 000 Metrum quadratum Coniunctiones urbium Urbes gemellae : Ovetum , Badalona , Santa Fe , Ora longa , Sciamhaevum , Quantunia , Callao , Bat Yam , Melaka , Novorossiysk , Busan , Corduba , Odessa , Rosario , Malacca , Barcino , Soteropolis , Franciscopolis (California) , Guanajuato, Silao Tabula aut despectus Despectus in portum sinumque et urbem Vallis Paradisi Vallis Para
                      Read more

                      Tabula Rosettana

                      Image
                      Tabula multilinguis Rosettana in Museo Britannico ostenditur. Tabula Rosettana, [1] etiam titulo OGIS 90 agnita, est stela decreto de rebus sacris in Aegypto anno 196 a.C.n. lato inscripta. Tabula iuxta Rosettam Aegypti, urbem in delta Nili et ad oram maris Mediterranei iacentem, anno 1799 a milite Francico reperta est. Inventio stelae, linguis duabus scripturisque tribus inscriptae, eruditis Instituti Aegypti statim nuntiata est; ibi enim iussu imperatoris Napoleonis eruditi omnium scientiarum (sub aegide Commissionis Scientiarum et Artium) properaverant cum expeditione Francica. Qua a Britannis mox debellata, tabula Rosettana Londinium missa hodie apud Museum Britannicum iacet. Textus Graecus cito lectus interpretationi textuum Aegyptiorum (in formis hieroglyphica et demotica expressorum) gradatim adiuvit. Denique textum plene interpretatus est Ioannes Franciscus Champollion. Ab opere eruditorum cumulativo coepit hodiernus scripturae hieroglyphicae linguaeque Aegyptiae a
                      Read more