Is there a name for a graph in which every vertex is both a central vertex and a peripheral vertex

133 Views Asked by At

Is there a name for a graph for which every vertex is simultaneously in the center and in the periphery of the graph?

If I'm not mistaken the graph representing the states of the Rubik's cube whose edges are the twists of the cube is such a graph. I.e., for such a graph there is no special state. I suppose the complete graph $K_n$ is such a graph as well.

1

There are 1 best solutions below

0
On

Such a graph is called a self-centered graph.

This is defined in the linked post as a graph whose diameter equals its radius; therefore the maximum eccentricity of any vertex equals the minimum eccentricity.

Note that the Rubik's cube graph has a much stronger property. It is vertex-transitive: there is an automorphism that maps any vertex to any other vertex. In a sense, no graph property can distinguish a vertex from any other. A self-centered graph is one where vertices cannot be distinguished by eccentricity alone, but there might still be other distinguishing characteristics.