**
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

**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