ACTA MATHEMATICA UNIVERSITATIS COMENIANAE

Vol. 61,   2   (1992)
pp.   237-241

CENTERS IN ITERATED LINE GRAPHS
M. KNOR, L. NIEPEL and L. SOLTES


Abstract.  For a graph $G$ such that $L^2(G)$ is not empty, we construct a supergraph $H$ such that $C(L^i(H))=L^i(G)$ for all $i$, $0\le i\le 2$. Here $L^i(G)$ denotes the $i$-iterated line graph of $G$ and $C(G)$ denotes the subgraph of $G$ induced by central nodes. This result is, in a sense, best possible since we provide an infinite class of graphs $G$ such that $L^i(G)\ne C(L^i(H))$ for any graph $H\supseteq G$ and all $i\ge 3$.

AMS subject classification.  05C12
Keywords

Download:     Adobe PDF     Compressed Postscript      

Acta Mathematica Universitatis Comenianae
Institute of Applied Mathematics
Faculty of Mathematics, Physics and Informatics
Comenius University
842 48 Bratislava, Slovak Republic  

Telephone: + 421-2-60295111 Fax: + 421-2-65425882  
e-Mail: amuc@fmph.uniba.sk   Internet: www.iam.fmph.uniba.sk/amuc

© Copyright 2001, ACTA MATHEMATICA UNIVERSITATIS COMENIANAE