Zero-symmetric graph

<h2 id="examples">Examples</h2>
The smallest zero-symmetric graph is a nonplanar graph with 18 vertices.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a> Its <a href="/facts/LCF_notation/JQt8BMR8">LCF notation</a> is [5,−5]9. 
Among <a href="/facts/Planar_graph/plREagr9">planar graphs</a>, the <a href="/facts/Truncated_cuboctahedral_graph/nd2ltxcm">truncated cuboctahedral</a> and <a href="/facts/Truncated_icosidodecahedral_graph/d5v9VpFY">truncated icosidodecahedral graphs</a> are also zero-symmetric.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>
These examples are all <a href="/facts/Bipartite_graph/xWcXV9MB">bipartite graphs</a>. However, there exist larger examples of zero-symmetric graphs that are not bipartite.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>
These examples also have three different symmetry classes (orbits) of edges. However, there exist zero-symmetric graphs with only two orbits of edges.
The smallest such graph has 20 vertices, with <a href="/facts/LCF_notation/JQt8BMR8">LCF notation</a> [6,6,-6,-6]5.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>

<h2 id="properties">Properties</h2>
Every finite zero-symmetric graph is a <a href="/facts/Cayley_graph/QxoxNnys">Cayley graph</a>, a property that does not always hold for cubic vertex-transitive graphs more generally and that helps in the solution of <a href="/facts/Combinatorial_enumeration/AtqWU2bj">combinatorial enumeration</a> tasks concerning zero-symmetric graphs. There are 97687 zero-symmetric graphs on up to 1280 vertices. These graphs form 89% of the cubic Cayley graphs and 88% of all connected vertex-transitive cubic graphs on the same number of vertices.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a>

Unsolved problem in mathematics:
Does every finite zero-symmetric graph contain a <a href="/facts/Hamiltonian_cycle/MHjY2xoY">Hamiltonian cycle</a>?
<a href="/facts/List_of_unsolved_problems_in_mathematics/RroxGPpP">(more unsolved problems in mathematics)</a>

All known finite connected zero-symmetric graphs contain a <a href="/facts/Hamiltonian_cycle/MHjY2xoY">Hamiltonian cycle</a>, but it is unknown whether every finite connected zero-symmetric graph is necessarily Hamiltonian.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a> This is a special case of the <a href="/facts/Lov%C3%A1sz_conjecture/9oznzvAB">Lovász conjecture</a> that (with five known exceptions, none of which is zero-symmetric) every finite connected vertex-transitive graph and every finite Cayley graph is Hamiltonian.

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Semi-symmetric_graph/sDSNzytV">Semi-symmetric graph</a>, graphs that have symmetries between every two edges but not between every two vertices (reversing the roles of edges and vertices in the definition of zero-symmetric graphs)</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Coxeter, Harold Scott MacDonald; Frucht, Roberto; Powers, David L. (1981), Zero-symmetric graphs, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, ISBN 0-12-194580-4, MR 0658666 <a href="0-12-194580-4" target="_blank">0-12-194580-4</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Coxeter, Frucht & Powers (1981), p. ix. - Coxeter, Harold Scott MacDonald; Frucht, Roberto; Powers, David L. (1981), Zero-symmetric graphs, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, ISBN 0-12-194580-4, MR 0658666 <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0658666" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0658666</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Lauri, Josef; Scapellato, Raffaele (2003), Topics in Graph Automorphisms and Reconstruction, London Mathematical Society Student Texts, Cambridge University Press, p. 66, ISBN 9780521529037. <a href="9780521529037" target="_blank">9780521529037</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Coxeter, Frucht & Powers (1981), Figure 1.1, p. 5. - Coxeter, Harold Scott MacDonald; Frucht, Roberto; Powers, David L. (1981), Zero-symmetric graphs, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, ISBN 0-12-194580-4, MR 0658666 <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0658666" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0658666</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Coxeter, Frucht & Powers (1981), pp. 75 and 80. - Coxeter, Harold Scott MacDonald; Frucht, Roberto; Powers, David L. (1981), Zero-symmetric graphs, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, ISBN 0-12-194580-4, MR 0658666 <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0658666" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0658666</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Coxeter, Frucht & Powers (1981), p. 55. - Coxeter, Harold Scott MacDonald; Frucht, Roberto; Powers, David L. (1981), Zero-symmetric graphs, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, ISBN 0-12-194580-4, MR 0658666 <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0658666" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0658666</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Conder, Marston D. E.; Pisanski, Tomaž; Žitnik, Arjana (2017), "Vertex-transitive graphs and their arc-types", Ars Mathematica Contemporanea, 12 (2): 383–413, arXiv:1505.02029, doi:10.26493/1855-3974.1146.f96, MR 3646702 <a href="/wiki/Marston_Conder" target="_blank">/wiki/Marston_Conder</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Potočnik, Primož; Spiga, Pablo; Verret, Gabriel (2013), "Cubic vertex-transitive graphs on up to 1280 vertices", Journal of Symbolic Computation, 50: 465–477, arXiv:1201.5317, doi:10.1016/j.jsc.2012.09.002, MR 2996891. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Coxeter, Frucht & Powers (1981), p. 10. - Coxeter, Harold Scott MacDonald; Frucht, Roberto; Powers, David L. (1981), Zero-symmetric graphs, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, ISBN 0-12-194580-4, MR 0658666 <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0658666" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0658666</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
</ol>

Zero-symmetric graph open-in-new

Zero-symmetric graph