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?

Improve this question
$\endgroup$
6
  • 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, 2014 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, 2014 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, 2014 at 2:26
  • $\begingroup$ @QiaochuYuan: Great; thanks for checking! $\endgroup$
    – Lucia
    Mar 2, 2014 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, 2014 at 2:36

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • 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, 2014 at 7:36
  • $\begingroup$ @RickyDemer: You're absolutely right! Nice observation. $\endgroup$
    – Lucia
    Mar 2, 2014 at 15:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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