Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
4  
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 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 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 at 2:26
    
@QiaochuYuan: Great; thanks for checking! –  Lucia Mar 2 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 at 2:36

1 Answer 1

up vote 19 down vote accepted

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.

share|improve this answer
5  
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}$ –  Ricky Demer Mar 2 at 7:36
    
@RickyDemer: You're absolutely right! Nice observation. –  Lucia Mar 2 at 15:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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