14
$\begingroup$

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$:
          GraphCenter50
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$?


(Addendum 5Mar14.) Joe Malkevitch asked (personal communication):

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

$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – Lucia Mar 2 '14 at 2:19
  • $\begingroup$ @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? $\endgroup$ – Lucia Mar 2 '14 at 2:23
  • $\begingroup$ @Lucia: oh, my apologies. I thought you had drawn an edge from $A$ to $B$ for some reason. Yes, I think this works. $\endgroup$ – Qiaochu Yuan Mar 2 '14 at 2:26
  • $\begingroup$ @QiaochuYuan: Great; thanks for checking! $\endgroup$ – Lucia Mar 2 '14 at 2:27
  • $\begingroup$ @Lucia: Beautiful construction! I will accept that if you make it an answer. How short can the long paths of many vertices be? $\endgroup$ – Joseph O'Rourke Mar 2 '14 at 2:36
22
$\begingroup$

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.

$\endgroup$
  • 6
    $\begingroup$ 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}$ $\endgroup$ – user5810 Mar 2 '14 at 7:36
  • $\begingroup$ @RickyDemer: You're absolutely right! Nice observation. $\endgroup$ – Lucia Mar 2 '14 at 15:00

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.