# Is every graph the center of some other graph?

The center of a graph $G$ is the set of vertices that minimize the largest distance to vertices in $G$, e.g., in the graph below, that radius is $4$:

Define the center $C$ as the subgraph of $G$ induced by those vertices. I seek to learn constraints on $C$. Is it the case that every graph $C$ is the center of some graph $G$? Or are there constraints on the possible structures of $C$?

Is every plane graph the center of some other plane graph?

• How about the following construction: Introduce two new vertices $A$ and $B$. Connect all the vertices in $C$ to $A$; and connect all the vertices in $C$ to $B$. From $A$ draw a long line with many vertices on it (the line doesn't have any other edges to $C$), and similarly from $B$ draw a long line with many vertices on it (same number of vertices as the line from $A$). Now if I understand your question correctly, I think $C$ is the center of this new graph. – Lucia Mar 2 '14 at 2:19
• @QiaochuYuan: I thought it would take one more step to connect $A$ to the end of $B$, and so $A$ would not be in the center; and the same for $B$. Am I missing something? – Lucia Mar 2 '14 at 2:23
• @Lucia: oh, my apologies. I thought you had drawn an edge from $A$ to $B$ for some reason. Yes, I think this works. – Qiaochu Yuan Mar 2 '14 at 2:26
• @QiaochuYuan: Great; thanks for checking! – Lucia Mar 2 '14 at 2:27
• @Lucia: Beautiful construction! I will accept that if you make it an answer. How short can the long paths of many vertices be? – Joseph O'Rourke Mar 2 '14 at 2:36

I'm just copying my comment above, as it seems to answer the question. For any graph $C$ there exists a graph for which this is the center. Introduce two new vertices $A$ and $B$. Connect all the vertices in $C$ to $A$; and connect all the vertices in $C$ to $B$. From $A$ draw a long line with many vertices on it (the line doesn't have any other edges to $C$), and similarly from $B$ draw a long line with many vertices on it (same number of vertices as the line from $A$, and this number is larger than the maximum length between two vertices in $C$). Now the vertices in $C$ form the center of this new graph.
• You don't actually need "long line"s of vertices, you can just attach another vertex to each of A and B. $\hspace{.6 in}$ – user5810 Mar 2 '14 at 7:36