2
$\begingroup$

I'm investigating finite, simple graphs with the following property: For each degree $d$ of $G$, the subgraph induced on all vertices of degree $d$ is vertex transitive.

In particular, I'm interested in graphs that are not vertex transitive to begin with.

For example, consider the following graph.

Example graph

Since it has vertices of degree 4 and 5, it is not vertex transitive. But the subgraph induced on the four vertices of degree 4 is $C_4$, which is vertex transitive. Likewise, the subgraph induced on the four vertices of degree 5 is $K_4$, which is vertex transitive.

The house graph is a nonexample, as the subgraph induced on the three vertices of degree 2 gives $K_1 \cup K_2$, which is not vertex transitive.

My initial questions:

  1. Is there a name for this property?

  2. Is much known about graphs with this property?

I'm thinking this property might be similar to saying that for each degree $d$, all vertices of degree $d$ are in the same orbit under the automorphism group of $G$, but I haven't fleshed that out fully yet.

Thank you.

$\endgroup$
  • 2
    $\begingroup$ "I'm thinking this property might be similar to saying that for each degree $d$, all vertices of degree $d$ are in the same orbit under the automorphism group of $G$, but I haven't fleshed that out fully yet." -- they are, at least, not equivalent, as can be seen by starting with a triangle, adding one pendant edge to each vertex of the triangle, then subdividing one of the pendant edges. $\endgroup$ – Gregory J. Puleo Jan 27 '16 at 19:18
  • $\begingroup$ That's a useful example, thanks. $\endgroup$ – jamisans Jan 27 '16 at 19:40
  • 2
    $\begingroup$ You can also have graphs where the vertices of each valency induce a coclique, e.g., bipartite graphs. $\endgroup$ – Chris Godsil Jan 27 '16 at 20:33

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.