Skip to main content
MathOverflow

Return to Question

Removed deprecated (discrete-mathematics) tag - see the tag info: https://mathoverflow.net/tags/discrete-mathematics/info (if there are some other suitable tags, choose some of them instead)
Link
Martin Sleziak
Martin Sleziak
  • 4.7k
  • 4
  • 35
  • 40
Added question restricted to plane graphs.
Source Link
Joseph O'Rourke
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958

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?

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

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?

Source Link
Joseph O'Rourke
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958

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