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
    Commented 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
    Commented 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
    Commented Mar 2, 2014 at 2:26
  • $\begingroup$ @QiaochuYuan: Great; thanks for checking! $\endgroup$
    – Lucia
    Commented 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
    Commented 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
    Commented Mar 2, 2014 at 7:36
  • $\begingroup$ @RickyDemer: You're absolutely right! Nice observation. $\endgroup$
    – Lucia
    Commented Mar 2, 2014 at 15:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .