ACTA MATHEMATICA UNIVERSITATIS COMENIANAE

Vol. 69,   1   (2000)
pp.   77-83

NOTE ON SEED GRAPHS WITH COMPONENTS OF GIVEN ORDER
D. FRONCEK

Abstract.  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.  05C99
Keywords.  Seed graphs, isomorphic survivor graphs, local properties of graphs