Which trees are link graphs? |
| |
Authors: | Andreas Blass Frank Harary Zevi Miller |
| |
Institution: | University of Michigan, Ann Arbor, Michigan 48109 USA;Department of Mathematics and Statistics, Miami University, Oxford, Ohio 45056 USA |
| |
Abstract: | 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 p≤9 to see which are link graphs. Group theoretic methods are used to obtain constructions of graphs G 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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|