ACTA MATHEMATICA UNIVERSITATIS COMENIANAE
Vol. 69,   1   (2000)
NOTE ON SEED GRAPHS WITH COMPONENTS OF GIVEN ORDER
A closed neighbourhood $N_G[x]$ of a vertex $x$ in a graph $G$ is the subgraph of $G$ induced by $x$ and all neighbours of $x$. A seed of a vertex $x\in G$ is the subgraph of $G$ induced by all vertices of $G\setminus N_G[x]$ and we denote it by $S_G(x)$. A graph $F$ is a seed graph if there exists a graph $G$ such that $S_G(x)\cong F$ for each $x\in G$. In this paper seed graphs with more than two components are studied. It is shown that if all components are of equal order, then they are all isomorphic to a complete graph. In the general case it is shown how the structure of any component $F_i$ of a seed graph $F$ depends on the structure of all components of smaller order.
AMS subject classification.
Seed graphs, isomorphic survivor graphs, local properties of graphs
Download:     Adobe PDF     Compressed Postscript
Acta Mathematica Universitatis Comenianae
Institute of Applied
Faculty of Mathematics,
Physics and Informatics
842 48 Bratislava, Slovak Republic
Telephone: + 421-2-60295111 Fax: + 421-2-65425882
© Copyright 2001, ACTA MATHEMATICA