摘 要: | A graph G is said to be embeddable into a graph H,if there is an isomorphism of G into asubgraph of H.It is shown in this paper that every unicycle or tree which is neither a path nor K_(1,3)embeds in its n-th iterated line graph for n≥1 or 2,3,and that every other connected graph thatembeds in its n-th iterated line graph may be constructed from such an embedded unicycle or tree ina natural way A special kind of embedding of graph into its n-th iterated line graph,called incidenceembedding,is studied.Moreover,it is shown that for every positive integer k,there exists a graph Gsuch that (?)(G)=k,where (?)(G) is the least n≥1 for which G embeds in L~n(G).
|