What does “Vertex-transitivity” tell us about an arbitrary graph?












2












$begingroup$


I know the formal definition, i.e. , for any arbitrary graph G,



$forall v_i,v_jin V(G), exists g in Auto(G) , s.t. g(v_i)=v_j$



But what does it mean in a broader sense?










share|cite|improve this question









$endgroup$








  • 3




    $begingroup$
    It means there is a pleasant symmetry to the graph. Consider the graph of a soccer ball, for example, where every vertex belongs to two hexagonal faces and a pentagonal face, and the vertices are interchangeable by spinning the ball.
    $endgroup$
    – Théophile
    Nov 25 '16 at 21:11










  • $begingroup$
    So back to our formal definition, what you said means that for each two vertices, I could find an automorphism,namely, a rotation from one vertex exactly toward the other? @Théophile
    $endgroup$
    – Ashkan Ranjbar
    Nov 25 '16 at 22:10










  • $begingroup$
    Yes, that's right. So it formalizes the idea of "you can't tell the difference between the vertices". An $n$-cycle is also vertex transitive: pick any $u,v in V$, and there is an obvious automorphism sending $u$ to $v$. To put it another way, there are no "special" vertices. A star, for example, where one central vertex $w$ is connected to a number of leaves, is not vertex transitive; you can easily distinguish $w$ from the leaves (which is an informal way of saying that no automorphism sends $w$ to a leaf).
    $endgroup$
    – Théophile
    Nov 26 '16 at 2:06










  • $begingroup$
    Compare also to edge transitivity, which is similar but (of course) applies to edges instead of vertices. A soccer ball is not edge transitive because there are two kinds of edges: either both endpoints are on the same pentagon, or they are on different pentagons. An $n$-cycle, on the other hand, is edge transitive.
    $endgroup$
    – Théophile
    Nov 26 '16 at 2:09
















2












$begingroup$


I know the formal definition, i.e. , for any arbitrary graph G,



$forall v_i,v_jin V(G), exists g in Auto(G) , s.t. g(v_i)=v_j$



But what does it mean in a broader sense?










share|cite|improve this question









$endgroup$








  • 3




    $begingroup$
    It means there is a pleasant symmetry to the graph. Consider the graph of a soccer ball, for example, where every vertex belongs to two hexagonal faces and a pentagonal face, and the vertices are interchangeable by spinning the ball.
    $endgroup$
    – Théophile
    Nov 25 '16 at 21:11










  • $begingroup$
    So back to our formal definition, what you said means that for each two vertices, I could find an automorphism,namely, a rotation from one vertex exactly toward the other? @Théophile
    $endgroup$
    – Ashkan Ranjbar
    Nov 25 '16 at 22:10










  • $begingroup$
    Yes, that's right. So it formalizes the idea of "you can't tell the difference between the vertices". An $n$-cycle is also vertex transitive: pick any $u,v in V$, and there is an obvious automorphism sending $u$ to $v$. To put it another way, there are no "special" vertices. A star, for example, where one central vertex $w$ is connected to a number of leaves, is not vertex transitive; you can easily distinguish $w$ from the leaves (which is an informal way of saying that no automorphism sends $w$ to a leaf).
    $endgroup$
    – Théophile
    Nov 26 '16 at 2:06










  • $begingroup$
    Compare also to edge transitivity, which is similar but (of course) applies to edges instead of vertices. A soccer ball is not edge transitive because there are two kinds of edges: either both endpoints are on the same pentagon, or they are on different pentagons. An $n$-cycle, on the other hand, is edge transitive.
    $endgroup$
    – Théophile
    Nov 26 '16 at 2:09














2












2








2


1



$begingroup$


I know the formal definition, i.e. , for any arbitrary graph G,



$forall v_i,v_jin V(G), exists g in Auto(G) , s.t. g(v_i)=v_j$



But what does it mean in a broader sense?










share|cite|improve this question









$endgroup$




I know the formal definition, i.e. , for any arbitrary graph G,



$forall v_i,v_jin V(G), exists g in Auto(G) , s.t. g(v_i)=v_j$



But what does it mean in a broader sense?







graph-theory






share|cite|improve this question













share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










asked Nov 25 '16 at 20:58









Ashkan RanjbarAshkan Ranjbar

11713




11713








  • 3




    $begingroup$
    It means there is a pleasant symmetry to the graph. Consider the graph of a soccer ball, for example, where every vertex belongs to two hexagonal faces and a pentagonal face, and the vertices are interchangeable by spinning the ball.
    $endgroup$
    – Théophile
    Nov 25 '16 at 21:11










  • $begingroup$
    So back to our formal definition, what you said means that for each two vertices, I could find an automorphism,namely, a rotation from one vertex exactly toward the other? @Théophile
    $endgroup$
    – Ashkan Ranjbar
    Nov 25 '16 at 22:10










  • $begingroup$
    Yes, that's right. So it formalizes the idea of "you can't tell the difference between the vertices". An $n$-cycle is also vertex transitive: pick any $u,v in V$, and there is an obvious automorphism sending $u$ to $v$. To put it another way, there are no "special" vertices. A star, for example, where one central vertex $w$ is connected to a number of leaves, is not vertex transitive; you can easily distinguish $w$ from the leaves (which is an informal way of saying that no automorphism sends $w$ to a leaf).
    $endgroup$
    – Théophile
    Nov 26 '16 at 2:06










  • $begingroup$
    Compare also to edge transitivity, which is similar but (of course) applies to edges instead of vertices. A soccer ball is not edge transitive because there are two kinds of edges: either both endpoints are on the same pentagon, or they are on different pentagons. An $n$-cycle, on the other hand, is edge transitive.
    $endgroup$
    – Théophile
    Nov 26 '16 at 2:09














  • 3




    $begingroup$
    It means there is a pleasant symmetry to the graph. Consider the graph of a soccer ball, for example, where every vertex belongs to two hexagonal faces and a pentagonal face, and the vertices are interchangeable by spinning the ball.
    $endgroup$
    – Théophile
    Nov 25 '16 at 21:11










  • $begingroup$
    So back to our formal definition, what you said means that for each two vertices, I could find an automorphism,namely, a rotation from one vertex exactly toward the other? @Théophile
    $endgroup$
    – Ashkan Ranjbar
    Nov 25 '16 at 22:10










  • $begingroup$
    Yes, that's right. So it formalizes the idea of "you can't tell the difference between the vertices". An $n$-cycle is also vertex transitive: pick any $u,v in V$, and there is an obvious automorphism sending $u$ to $v$. To put it another way, there are no "special" vertices. A star, for example, where one central vertex $w$ is connected to a number of leaves, is not vertex transitive; you can easily distinguish $w$ from the leaves (which is an informal way of saying that no automorphism sends $w$ to a leaf).
    $endgroup$
    – Théophile
    Nov 26 '16 at 2:06










  • $begingroup$
    Compare also to edge transitivity, which is similar but (of course) applies to edges instead of vertices. A soccer ball is not edge transitive because there are two kinds of edges: either both endpoints are on the same pentagon, or they are on different pentagons. An $n$-cycle, on the other hand, is edge transitive.
    $endgroup$
    – Théophile
    Nov 26 '16 at 2:09








3




3




$begingroup$
It means there is a pleasant symmetry to the graph. Consider the graph of a soccer ball, for example, where every vertex belongs to two hexagonal faces and a pentagonal face, and the vertices are interchangeable by spinning the ball.
$endgroup$
– Théophile
Nov 25 '16 at 21:11




$begingroup$
It means there is a pleasant symmetry to the graph. Consider the graph of a soccer ball, for example, where every vertex belongs to two hexagonal faces and a pentagonal face, and the vertices are interchangeable by spinning the ball.
$endgroup$
– Théophile
Nov 25 '16 at 21:11












$begingroup$
So back to our formal definition, what you said means that for each two vertices, I could find an automorphism,namely, a rotation from one vertex exactly toward the other? @Théophile
$endgroup$
– Ashkan Ranjbar
Nov 25 '16 at 22:10




$begingroup$
So back to our formal definition, what you said means that for each two vertices, I could find an automorphism,namely, a rotation from one vertex exactly toward the other? @Théophile
$endgroup$
– Ashkan Ranjbar
Nov 25 '16 at 22:10












$begingroup$
Yes, that's right. So it formalizes the idea of "you can't tell the difference between the vertices". An $n$-cycle is also vertex transitive: pick any $u,v in V$, and there is an obvious automorphism sending $u$ to $v$. To put it another way, there are no "special" vertices. A star, for example, where one central vertex $w$ is connected to a number of leaves, is not vertex transitive; you can easily distinguish $w$ from the leaves (which is an informal way of saying that no automorphism sends $w$ to a leaf).
$endgroup$
– Théophile
Nov 26 '16 at 2:06




$begingroup$
Yes, that's right. So it formalizes the idea of "you can't tell the difference between the vertices". An $n$-cycle is also vertex transitive: pick any $u,v in V$, and there is an obvious automorphism sending $u$ to $v$. To put it another way, there are no "special" vertices. A star, for example, where one central vertex $w$ is connected to a number of leaves, is not vertex transitive; you can easily distinguish $w$ from the leaves (which is an informal way of saying that no automorphism sends $w$ to a leaf).
$endgroup$
– Théophile
Nov 26 '16 at 2:06












$begingroup$
Compare also to edge transitivity, which is similar but (of course) applies to edges instead of vertices. A soccer ball is not edge transitive because there are two kinds of edges: either both endpoints are on the same pentagon, or they are on different pentagons. An $n$-cycle, on the other hand, is edge transitive.
$endgroup$
– Théophile
Nov 26 '16 at 2:09




$begingroup$
Compare also to edge transitivity, which is similar but (of course) applies to edges instead of vertices. A soccer ball is not edge transitive because there are two kinds of edges: either both endpoints are on the same pentagon, or they are on different pentagons. An $n$-cycle, on the other hand, is edge transitive.
$endgroup$
– Théophile
Nov 26 '16 at 2:09










3 Answers
3






active

oldest

votes


















2












$begingroup$

If a graph $X=(V(X),E(X))$ is vertex transitive, then we can talk about some obvious things.




  • Graph $X$ is regular.(converse is not true Eg: Frucht Graph)

  • $Aut(X)$ is non-trivial.

  • Graph $X$ is symmetric.

  • Graph $X$ is locally similar, that means by looking at the vertices we can actually observe that locally they are same.


For example, Cayley Graph $X=(G,C)$ where $G$ is any group and $C$ is any subset of G which doesn't contain the identity and it's closed under inverse. Cayley graphs are regular and by construction, we can find a subgroup which is acting transitively on $X$.



Another important example is $J(5,2,0)$ Petersen graph. Here $S_5$ acts transitively on the vertex set{ which is nothing but the set of subsets of ${1,2,3,4,5}$ of size 2. }.






share|cite|improve this answer









$endgroup$





















    2












    $begingroup$

    Its very similar to what homogeneity means in topological spaces.



    Basically it means that if I am sitting in one of the vertices and I want to tell Steve which vertex I am at while on the phone, I am gonna be totally screwed, because the graph looks the same from every vertex.






    share|cite|improve this answer











    $endgroup$





















      0












      $begingroup$

      Vertex transitive graphs are completely symmetric in the same way as the surface of a sphere is, every node has all the same properties as every other.



      Graphs can be used to show group structure, for example:



      diagram



      This shows a dihedral symmetry group. It is the direct/cartesian multiplication of two simpler (sub) groups.



      Note that (as a graph) it is also the direct multiplication of two vertex transitive graphs, and so it is also vertex transitive.



      Moving the identity element e on the above diagram and relabelling the rest of the graph doesn't change any of the resulting group structure, any of the groups properties/uses, abab is still e, it's all still the same object.






      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: "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
        });


        }
        });














        draft saved

        draft discarded


















        StackExchange.ready(
        function () {
        StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2030701%2fwhat-does-vertex-transitivity-tell-us-about-an-arbitrary-graph%23new-answer', 'question_page');
        }
        );

        Post as a guest















        Required, but never shown

























        3 Answers
        3






        active

        oldest

        votes








        3 Answers
        3






        active

        oldest

        votes









        active

        oldest

        votes






        active

        oldest

        votes









        2












        $begingroup$

        If a graph $X=(V(X),E(X))$ is vertex transitive, then we can talk about some obvious things.




        • Graph $X$ is regular.(converse is not true Eg: Frucht Graph)

        • $Aut(X)$ is non-trivial.

        • Graph $X$ is symmetric.

        • Graph $X$ is locally similar, that means by looking at the vertices we can actually observe that locally they are same.


        For example, Cayley Graph $X=(G,C)$ where $G$ is any group and $C$ is any subset of G which doesn't contain the identity and it's closed under inverse. Cayley graphs are regular and by construction, we can find a subgroup which is acting transitively on $X$.



        Another important example is $J(5,2,0)$ Petersen graph. Here $S_5$ acts transitively on the vertex set{ which is nothing but the set of subsets of ${1,2,3,4,5}$ of size 2. }.






        share|cite|improve this answer









        $endgroup$


















          2












          $begingroup$

          If a graph $X=(V(X),E(X))$ is vertex transitive, then we can talk about some obvious things.




          • Graph $X$ is regular.(converse is not true Eg: Frucht Graph)

          • $Aut(X)$ is non-trivial.

          • Graph $X$ is symmetric.

          • Graph $X$ is locally similar, that means by looking at the vertices we can actually observe that locally they are same.


          For example, Cayley Graph $X=(G,C)$ where $G$ is any group and $C$ is any subset of G which doesn't contain the identity and it's closed under inverse. Cayley graphs are regular and by construction, we can find a subgroup which is acting transitively on $X$.



          Another important example is $J(5,2,0)$ Petersen graph. Here $S_5$ acts transitively on the vertex set{ which is nothing but the set of subsets of ${1,2,3,4,5}$ of size 2. }.






          share|cite|improve this answer









          $endgroup$
















            2












            2








            2





            $begingroup$

            If a graph $X=(V(X),E(X))$ is vertex transitive, then we can talk about some obvious things.




            • Graph $X$ is regular.(converse is not true Eg: Frucht Graph)

            • $Aut(X)$ is non-trivial.

            • Graph $X$ is symmetric.

            • Graph $X$ is locally similar, that means by looking at the vertices we can actually observe that locally they are same.


            For example, Cayley Graph $X=(G,C)$ where $G$ is any group and $C$ is any subset of G which doesn't contain the identity and it's closed under inverse. Cayley graphs are regular and by construction, we can find a subgroup which is acting transitively on $X$.



            Another important example is $J(5,2,0)$ Petersen graph. Here $S_5$ acts transitively on the vertex set{ which is nothing but the set of subsets of ${1,2,3,4,5}$ of size 2. }.






            share|cite|improve this answer









            $endgroup$



            If a graph $X=(V(X),E(X))$ is vertex transitive, then we can talk about some obvious things.




            • Graph $X$ is regular.(converse is not true Eg: Frucht Graph)

            • $Aut(X)$ is non-trivial.

            • Graph $X$ is symmetric.

            • Graph $X$ is locally similar, that means by looking at the vertices we can actually observe that locally they are same.


            For example, Cayley Graph $X=(G,C)$ where $G$ is any group and $C$ is any subset of G which doesn't contain the identity and it's closed under inverse. Cayley graphs are regular and by construction, we can find a subgroup which is acting transitively on $X$.



            Another important example is $J(5,2,0)$ Petersen graph. Here $S_5$ acts transitively on the vertex set{ which is nothing but the set of subsets of ${1,2,3,4,5}$ of size 2. }.







            share|cite|improve this answer












            share|cite|improve this answer



            share|cite|improve this answer










            answered Nov 26 '16 at 3:38









            Ashwin KoodathilAshwin Koodathil

            667




            667























                2












                $begingroup$

                Its very similar to what homogeneity means in topological spaces.



                Basically it means that if I am sitting in one of the vertices and I want to tell Steve which vertex I am at while on the phone, I am gonna be totally screwed, because the graph looks the same from every vertex.






                share|cite|improve this answer











                $endgroup$


















                  2












                  $begingroup$

                  Its very similar to what homogeneity means in topological spaces.



                  Basically it means that if I am sitting in one of the vertices and I want to tell Steve which vertex I am at while on the phone, I am gonna be totally screwed, because the graph looks the same from every vertex.






                  share|cite|improve this answer











                  $endgroup$
















                    2












                    2








                    2





                    $begingroup$

                    Its very similar to what homogeneity means in topological spaces.



                    Basically it means that if I am sitting in one of the vertices and I want to tell Steve which vertex I am at while on the phone, I am gonna be totally screwed, because the graph looks the same from every vertex.






                    share|cite|improve this answer











                    $endgroup$



                    Its very similar to what homogeneity means in topological spaces.



                    Basically it means that if I am sitting in one of the vertices and I want to tell Steve which vertex I am at while on the phone, I am gonna be totally screwed, because the graph looks the same from every vertex.







                    share|cite|improve this answer














                    share|cite|improve this answer



                    share|cite|improve this answer








                    edited Jan 26 at 22:39

























                    answered Nov 26 '16 at 3:42









                    Jorge Fernández HidalgoJorge Fernández Hidalgo

                    76.8k1394195




                    76.8k1394195























                        0












                        $begingroup$

                        Vertex transitive graphs are completely symmetric in the same way as the surface of a sphere is, every node has all the same properties as every other.



                        Graphs can be used to show group structure, for example:



                        diagram



                        This shows a dihedral symmetry group. It is the direct/cartesian multiplication of two simpler (sub) groups.



                        Note that (as a graph) it is also the direct multiplication of two vertex transitive graphs, and so it is also vertex transitive.



                        Moving the identity element e on the above diagram and relabelling the rest of the graph doesn't change any of the resulting group structure, any of the groups properties/uses, abab is still e, it's all still the same object.






                        share|cite|improve this answer











                        $endgroup$


















                          0












                          $begingroup$

                          Vertex transitive graphs are completely symmetric in the same way as the surface of a sphere is, every node has all the same properties as every other.



                          Graphs can be used to show group structure, for example:



                          diagram



                          This shows a dihedral symmetry group. It is the direct/cartesian multiplication of two simpler (sub) groups.



                          Note that (as a graph) it is also the direct multiplication of two vertex transitive graphs, and so it is also vertex transitive.



                          Moving the identity element e on the above diagram and relabelling the rest of the graph doesn't change any of the resulting group structure, any of the groups properties/uses, abab is still e, it's all still the same object.






                          share|cite|improve this answer











                          $endgroup$
















                            0












                            0








                            0





                            $begingroup$

                            Vertex transitive graphs are completely symmetric in the same way as the surface of a sphere is, every node has all the same properties as every other.



                            Graphs can be used to show group structure, for example:



                            diagram



                            This shows a dihedral symmetry group. It is the direct/cartesian multiplication of two simpler (sub) groups.



                            Note that (as a graph) it is also the direct multiplication of two vertex transitive graphs, and so it is also vertex transitive.



                            Moving the identity element e on the above diagram and relabelling the rest of the graph doesn't change any of the resulting group structure, any of the groups properties/uses, abab is still e, it's all still the same object.






                            share|cite|improve this answer











                            $endgroup$



                            Vertex transitive graphs are completely symmetric in the same way as the surface of a sphere is, every node has all the same properties as every other.



                            Graphs can be used to show group structure, for example:



                            diagram



                            This shows a dihedral symmetry group. It is the direct/cartesian multiplication of two simpler (sub) groups.



                            Note that (as a graph) it is also the direct multiplication of two vertex transitive graphs, and so it is also vertex transitive.



                            Moving the identity element e on the above diagram and relabelling the rest of the graph doesn't change any of the resulting group structure, any of the groups properties/uses, abab is still e, it's all still the same object.







                            share|cite|improve this answer














                            share|cite|improve this answer



                            share|cite|improve this answer








                            edited Jan 27 at 10:25

























                            answered Jan 26 at 18:30









                            alan2herealan2here

                            519219




                            519219






























                                draft saved

                                draft discarded




















































                                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.




                                draft saved


                                draft discarded














                                StackExchange.ready(
                                function () {
                                StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2030701%2fwhat-does-vertex-transitivity-tell-us-about-an-arbitrary-graph%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

                                MongoDB - Not Authorized To Execute Command

                                How to fix TextFormField cause rebuild widget in Flutter

                                in spring boot 2.1 many test slices are not allowed anymore due to multiple @BootstrapWith