{"id":1760,"date":"2015-10-15T01:00:15","date_gmt":"2015-10-15T01:00:15","guid":{"rendered":"http:\/\/blogs.ams.org\/visualinsight\/?p=1760"},"modified":"2016-03-29T19:46:29","modified_gmt":"2016-03-29T19:46:29","slug":"harries-graph","status":"publish","type":"post","link":"https:\/\/blogs.ams.org\/visualinsight\/2015\/10\/15\/harries-graph\/","title":{"rendered":"Harries Graph"},"content":{"rendered":"
\n
\"Harries<\/a>

Harries Graph – Koko90<\/p><\/div>\n<\/div>\n

This is the Harries graph<\/a>. It is a graph with the minimum number of vertices such that each vertex is connected to 3 others and every cycle has length at least 10. Such graphs are called (3,10)-cages<\/b>. <\/p>\n

There are just three (3,10)-cages. We have already mentioned one:<\/p>\n

• Balaban 10-cage<\/a>, Visual Insight<\/i>.<\/p>\n

The Harries graph has a closer resemblance to the third (3,10)-cage, the Harries-Wong graph<\/a>:<\/p>\n

\"Harries--Wong<\/a>

Harries–Wong Graph – Koko90<\/p><\/div><\/div>\n

Namely, the Harries graph and Harries–Wong graph are ‘isospectral’. Any simple graph<\/a> has an adjacency matrix<\/a>, a square matrix \\(A\\) where \\(A_{ij}\\) is the number of edges from the \\(i\\)th node to the \\(j\\)th node. Two graphs with same number of nodes are isospectral<\/b> if their adjacency matrices have the same eigenvalues, counted with multiplicity. <\/p>\n

We can also associate an operator to a graph called the graph Laplacian<\/a>, a discretized version of the ordinary Laplacian. Two simple graphs are isospectral iff their graph Laplacians have the same eigenvalues, counted with multiplicity. For more details, see:<\/p>\n

• Spectral graph theory<\/a>, Wikipedia<\/i>.<\/p>\n

• Andries E. Brouwer and Willem H. Haemers Spectra of Graphs<\/i><\/a>, Springer, Berlin, 2011.<\/p>\n

The layout for these pictures come from here:<\/p>\n

• T. Pisanski, M. Boben, D. Maru, A. Orbani and A. Graovac, The 10-cages and derived configurations, Discrete Mathematics<\/i> 275<\/b> (2004), 265–276.<\/p>\n

The picture of the Harries graph was created by Koko90<\/a> and put it on Wikicommons<\/a> under a Creative Commons Attribution-Share Alike 3.0 Unported license<\/a>. Koko90 also created the picture of the Harries–Wong graph and put it on Wikicommons<\/a> under the same license.<\/p>\n

\n

Visual Insight<\/i> is a place to share striking images that help explain advanced topics in mathematics. I\u2019m always looking for truly beautiful images, so if you know about one, please drop a comment here<\/a> and let me know!<\/p>\n

<\/div>","protected":false},"excerpt":{"rendered":"

This is the Harries graph<\/a>. It is a graph with the minimum number of vertices such that each vertex is connected to 3 others and every cycle has length at least 10. Such graphs are called (3,10)-cages<\/b>. <\/p>\n

<\/div>\n","protected":false},"author":66,"featured_media":1761,"comment_status":"open","ping_status":"closed","sticky":true,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[21,22,2],"tags":[],"class_list":["post-1760","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-combinatorics","category-graphs","category-images-library"],"jetpack_featured_media_url":"https:\/\/blogs.ams.org\/visualinsight\/files\/2015\/07\/harries_graph.png","jetpack_shortlink":"https:\/\/wp.me\/p42Vmc-so","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/posts\/1760","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/users\/66"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/comments?post=1760"}],"version-history":[{"count":13,"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/posts\/1760\/revisions"}],"predecessor-version":[{"id":2501,"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/posts\/1760\/revisions\/2501"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/media\/1761"}],"wp:attachment":[{"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/media?parent=1760"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/categories?post=1760"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/tags?post=1760"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}