10
$\begingroup$

I am wondering if the following pair of cospectral graphs was previously known.

The rhombic dodecahedron graph looks like this (graph6 string: 'M?????rrAiTOd_YO?'):rhombic dodecahedron

As far as I know, it was previously unknown whether it is determined by ts spectrum. On Wolfram Mathowrld, in the table describing properties of the graph, it simply has a "?" in the field for "determined by spectrum". However, I have found a cospectral (with respect to adjacency matrices) mate for this graph, which is displayed below (graph6 string: 'M?????rrAiTOX_eO?' ):mate

I checked in Sage and you cannot go from one to the other through Godsil-McKay switching (EDIT: I made a mistake here, you can get them from GM switching as @KrystalGuo points out below). They are also cospectral with respect to Laplacians, signless Laplacians, and normalized Laplacians. Though maybe this follows from adjacency cospectrality since they are biregular bipartite graphs? For what it is worth, both graphs are induced subgraphs of the Hoffman graph, which is the unique cospectral mate of the 4-cube. The 4-cube also contains the rhombic dodecahedron as an induced subgraph but not the cospectral mate. They are also both edge-transitive.

$\endgroup$
  • 1
    $\begingroup$ I don't even see why are they not isomorphic... $\endgroup$ – მამუკა ჯიბლაძე Apr 28 '17 at 6:33
  • 1
    $\begingroup$ @მამუკაჯიბლაძე Well one is planar and the other isn't, but that may be hard to see. The rhombic dodecahedron has radius 4, but the cospectral mate has radius 3. Also, the cospectral mate has pairs of vertices with the same neighborhood, but the rhombic dodecahedron does not. $\endgroup$ – David Roberson Apr 28 '17 at 9:21
  • 2
    $\begingroup$ For what it's worth, I just realized a nice description of the cospectral mate. You start with a K_4, subdivide every edge, then clone the vertices corresponding to the original vertices of the K_4, which is why you end up with vertices with the same neighborhood. $\endgroup$ – David Roberson Apr 28 '17 at 12:36
  • 5
    $\begingroup$ The two graphs are related by Godsil-McKay switching. The set $S = \{0,1,2,3\}$ is a switching set. For the first graph (graph6 string: 'M?????rrAiTOd_YO?'), each degree $3$ vertex is adjacent to none of the vertices of $S$ and each of the six degree $4$ vertex is adjacent to two of the vertices of $S$. When you do the Godsil-McKay switching on the rhombic dodecahedron graph with switching set $S$, you get a graph whose graph6 string is 'M????BBNDIJOX_eO?' and is isomorphic to the second graph you have provided. $\endgroup$ – Krystal Guo Apr 28 '17 at 15:01
  • 2
    $\begingroup$ Different construction: start with the 6 vertices of an octahedron in space. Both graphs are obtained by putting 8 "tripods" $K_{1,3}$ on those. For the first graph, each triangle gets one, for the second one, every other triangle (i.e. 4 triangles whose planes give a tetrahedron) gets 2. :-) $\endgroup$ – Wolfgang Apr 28 '17 at 17:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.