A NEW CHARACTERIZATION OF THE PETERSEN GRAPH

摘要

A graph F is called a frame of a graph G if F is a graph of minimum order having the properly dial for every vertex x of G and every vertex y ol F, there exists an embedding of 0 in F as an induced subgraph with x at .V. The Petersen aranh has been characterized in a number of ways. We present a new charac-terization by showing the Petersen graph is the unique frame of the subdivision graph of the star Ki,.i.