Search results

The contractibility number (also known as the Hadwiger number) of a connected graph G, Z(G), is defined as the maximum order of a connected graph onto which G is contractible. An elementary proof is given of a theorem of Ore about this invariant. Also, the extremal problem of finding the maximum Z(G) over all graphs G of a given order and regularity degree is solved.

The link of a vertex v of a graph G is the subgraph induced by all vertices adjacent to v. If all the links of G are isomorphic to L, then G has constant link and L is called a link graph. We investigate the trees of order pG with constant link L for certain trees L. Necessary conditions are derived for the existence of a graph having a given graph L as its constant link. These conditions show that many trees are not link graphs. An example is given to show that a connected graph with constant link need not be point symmetric.