### Mathematics Research Projects

## Project 19: The Center of a Plane
Graph

Let G be a connected graph. The eccentricity e(v) of a vertex
of G is the maximum distance any vertex of G can be from v. The
vertices of a graph of minimal eccentricity are the central vertices
of a graph. The graph induced in G by the central vertices of
G is called the center of G.

**Problem**

1. Can every path arise as the center of some plane graph?

2. Can every star arise as the center of some plane graph?

3. Can every caterpillar arise as the center of some plane graph?
(A caterpillar is a tree in which there is some path p in the
tree, and every other vertex of the tree is adjacent to some vertex
of p.)

4. Can every tree arise as the center of some plane graph?

5. Can every skirted tree arise as the center of some plane graph?
(A skirted tree is the graph obtained by taking a tree without
2-valent vertices, embedding it in the plane and passing a simple
closed curve through the 1-valent vertices of the the tree.)

6. What graphs can arise as the center of plane graphs?

Previous |
Home |
Glossary |
Next

**Joseph Malkevitch**

*Department of Mathematics and Computing*

York College (CUNY)

Jamaica, New York 11451-0001

email: malkevitch@york.cuny.edu

(Comments and results related to the project above are welcome.)

**Acknowledgements**

Some of this work was prepared with partial support from the National
Science Foundation (Grant Number: DUE 9555401) to the Long Island
Consortium for Interconnected Learning (administered by SUNY at
Stony Brook, Alan Tucker, Project Director).