# zbMATH — the first resource for mathematics

Antineighbourhood graphs. (English) Zbl 0759.05084
All graphs considered in present paper are finite undirected simple ones. A graph $$H$$ is called a neighbourhood graph if there exists a graph $$G$$ in which the subgraph induced by the neighbours of each vertex is isomorphic to $$H$$, and a graph $$H$$ is said to be a $$j$$-antineighbourhood graph if there exists a graph $$G$$ in which, for each vertex $$v$$ of $$G$$, the subgraph induced by the vertices at distance at least $$j+1$$ from $$v$$ is isomorphic to $$H$$. The classes of neighbourhood and $$j$$- antineighbourhood graphs are denoted by $${\mathfrak N}$$ and $${\mathfrak A}_ j$$, respectively. At first the graphs of the classes $${\mathfrak A}_ 0$$ and $${\mathfrak A_ 1}$$ are characterized by their structural properties and several examples are given. From the numerous general results here only some can be mentioned:
$$H$$ belongs to $${\mathfrak A}_ 0$$ iff it is a disjoint union of $$n$$ copies of $$K_ 1$$ for some positive integer $$n$$ or the graph obtained from $$H$$ by adding a new vertex and joining it to all vertices of the minimum degree of $$H$$ in $$H$$ is a vertex-symmetric graph (Theorem 1).
$$H$$ belongs to $${\mathfrak A}_ 0$$ iff it is a vertex-deleted subgraph of a vertex-symmetric graph (Corollary 1, which follows from Theorem 1).
$$H$$ belongs to $${\mathfrak A}_ 0$$ iff its complement $$\overline H$$ belongs to $${\mathfrak A}_ 0$$ (Theorem 2).
The total graph $$T(G)$$ of a graph $$G$$ belongs to $${\mathfrak A}_ 0$$ iff $$G\cong K_ 2$$ or $$G\cong\overline K_ n$$ for some positive integer $$n$$ (Theorem 5).
$$H$$ belongs to $${\mathfrak N}$$ iff its complement $$\overline H$$ belongs to $${\mathfrak A}_ 1$$ (Theorem 6). This means that all elements of $${\mathfrak A}_ 1$$ are determined by the elements of $${\mathfrak N}$$, and vice versa. These results imply:
A cycle $$C_ n$$ belongs to $${\mathfrak A}_ 0$$ iff $$n=3$$.
A wheel $$W_ n$$ belongs to $${\mathfrak A}_ 0$$ iff $$n=3$$ or $$n=4$$.
A block graph $$H$$ belongs to $${\mathfrak A}_ 0$$ iff $$H$$ is a complete graph or a path.
A cycle $$C_ n$$ belongs to $${\mathfrak A}_ 1$$ iff $$n=3,4,5,6$$.
The complement $$\overline C_ n$$ of $$C_ n$$ belongs to $${\mathfrak A}_ 1$$ for every $$n\geq 3$$.
If graphs $$H_ 1$$ and $$H_ 2$$ belong to $${\mathfrak A}_ 1$$, then their join $$H_ 1+H_ 2$$ belongs to $${\mathfrak A}_ 1$$. Furthermore, the block graphs which belong to $${\mathfrak A_ 1}$$ are characterized by the following main theorem:
If $$G$$ is a block graph, then $$G$$ belongs to $${\mathfrak A}_ 1$$ iff $$G$$ is a path or a regular windmill graph.
The proof of this theorem is an extensive one, numerous lemmas are used and many distinctions of cases are necessary. Finally, the authors get interesting statements about the membership of $$C^ 2_ n$$ from cycles $$C_ n$$ to the classes $${\mathfrak N}$$ respectively $${\mathfrak A}_ 1$$ depending on the length $$n$$. And regarding the classes $${\mathfrak A}_ j$$, $$j\geq 2$$, they obtain the result that every graph $$H$$ belongs to such a class.
##### MSC:
 05C75 Structural characterization of families of graphs
Full Text: