ACTA MATHEMATICA UNIVERSITATIS COMENIANAE

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