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).