4
$\begingroup$

Let us call a graph G $nice$ if for any vertex $v \in G$, the induced subgraph on the vertices adjacent to $v$ is exactly a cycle.

Is there anything that we can conclude about nice graphs? In particular, can we find a different (maybe simpler) but equivalent formulation for niceness?

  • 1
    Certainly, any triangulation of the sphere would satisfy this condition. Are there any such graphs which cannot be represented as a triangulation of the sphere?2012-09-06
  • 0
    @ThomasAndrews Here is an example of a nice graph that is not a triangulation of the sphere: http://www.graphclasses.org/images/g_co-3K2.gif.2012-09-06
  • 0
    @AustinMohr Isn't that just the octahedron graph? That looks clearly like a triangulation of a sphere.2012-09-06
  • 0
    @ThomasAndrews You are correct.2012-09-06
  • 0
    I think there are non-sphere examples, such as triangulations of a torus. I do think that you can show that a finite "nice" graph that is a triangulation of some compact 2-dimensional manifold.2012-09-07
  • 0
    @ThomasAndrews That is really helpful. Any ideas about how one would go about doing that?2012-09-07
  • 0
    The outline of the proof is to realize the triangles by taking a point and its neighbors. Since there is a loop amongst the neighbors, that gives you a set of triangles, and the interior of these triangles, when stitched together appropriately, become a 2D neighborhood. So you can basically stitch together a bunch of triangles to get a 2-manifold.2012-09-07

1 Answers 1