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.
05C75 Structural characterization of families of graphs
Full Text: EuDML
[1] BEINEKE L. W.: Characterizations of derived graphs. J. Combin. Theory 9 (1970), 129-135. · Zbl 0202.55702
[2] BIELAK H.: On j-neighbourhoods in simple graphs. Graphs and Other Combinatorial Topics, vol. 59, Teubner-Texte zur Mathematik, 1983, pp. 7-11. · Zbl 0536.05058
[3] BIELAK H.: On graphs with non-isomorphic 2-neighbourhoods. Časopis Pěst. Mat. 108 (1983), 294-298. · Zbl 0526.05056
[4] BLASS A., HARARY F., MILLER Z.: Which trees are link graphs. J. Combin. Theory B 29 (1980), 277-292. · Zbl 0448.05028
[5] BLOKHUIS A., BROUWER A. E., BUSET D., COHEN A. M.: The locally icosahedral graphs. Lecture Notes in Pure and Appl. Math., vol. 103, 1985, pp. 19-22. · Zbl 0587.05059
[6] BOESCH F., TINDELL R.: Circulants and their connectivities. J. Graph Theory 8 (1984), 487-499. · Zbl 0549.05048
[7] BROWN M., CONNELLY R.: On graphs with a constant link. I. New Directions in the Theory of Graphs, Academic Press, 1973, pp. 19-51..
[8] BROWN M., CONNELLY R.: On graphs with a constant link. II. Discrete Math. 11 (1975), 199-232. · Zbl 0304.05102
[9] BULITKO V. K.: On graphs with given vertex-neighbourhoods. Trudy Mat. Inst. Steklov. 133 (1973), 78-94.
[10] BURNS D., KAPOOR S. F., OSTRAND P. A.: On line-symmetric graphs. Fund. Math. 122 (1984), 1-21. · Zbl 0547.05053
[11] BUSET D.: Graphs which are locally a cube. Discrete Math. 46 (1983), 221-226. · Zbl 0532.05050
[12] CHILTON B. L., GOULD R., POLIMENI A. D.: A note on graphs whose neighborhoods are n-cycles. Geom. Dedicata 3 (1974), 289-294. · Zbl 0325.05116
[13] CRUYCE, VANDENP.: A fìnite graph which is locally a dodecahedron. Discrete Math. 54 (1985), 343-346. · Zbl 0571.05047
[14] DOYEN J., HUBAUT X., REYNART M.: Finite graphs with isomorphic neighbourhoods. Problèmes Combinaíoires et Théorie des Graphes (Colloq. Orsay 1976), CNRS, Paris, 1978, p. 111.
[15] GODSIL C. D.: Neighbourhoods of transitive graphs and GRR’s. J. Combin. Theory B 29 (1980), 116-140. · Zbl 0443.05047
[16] GODSIL C. D., MCKAY B. D.: Graphs with regular neighbourhoods. Lecture Notes in Math. 829, 1980, pp. 127-140.. · Zbl 0453.05052
[17] HALL J. I.: Locally Petersen graphs. J. Graph Theory 4 (1980), 173-187. · Zbl 0407.05041
[18] HALL J. I.: Graphs with constant link and small degree or order. J. Graph Theory 8 (1985), 419-444. · Zbl 0582.05049
[19] HARARY F.: Graph Theory. Addison-Wesley, Reading, Mass., 1969. · Zbl 0196.27202
[20] HARARY F. PALMER E.: A note on similar points and similar lines of a graph. Rev. Roumaine Math. Pures Appl. 10 (1965), 1489-1492. · Zbl 0141.21403
[21] HELL P.: Graphs with given neighbourhoods I. Problèmes Combinatoires et Théorie des Graphes (Colloq. Orsay 1976), ONRS, Paris, 1978, pp. 219-223.
[22] HELL P., LEVINSON H. WATKINS M.: Some remarks on transitive realizations of graphs. Proc. 2nd Carrib. Conf. on Combinatorics and Computing, Barbados, 1977, pp. 1-8.
[23] MOKAY B. D.: Transitive graphs with fewer than twenty vertices. Math. Comp. 33 (1977), 1101-1121. · Zbl 0411.05046
[24] RYJÀČEK Z.: On graphs with isomorphic, nonisomorphic and connected N2 -neighbourhoods. Časopis Pěst. Mat. 112 (1987), 66-79. · Zbl 0619.05041
[25] RYJÁČEK Z.: Graphs with nonisomorphic vertex neighbourhoods of the first and second types. Časopis P\?st. Mat. 112 (1987), 390-394. · Zbl 0638.05048
[26] SEDLÁČEK J.: On local properties of finite graphs. Časopis Pěst. Mat. 106 (1981), 290-298.
[27] SEDLÁČEK J.: On local properties of finite graphs. Lecture Notes in Math. 1018, 1983, pp. 242-247. · Zbl 0531.05056
[28] SEDLÁČEK J.: Finite graphs with distinct neighbourhoods. Teubner-Texte Math. 73 (1985), 152-156.
[29] TURNER J.: Point-symmetric graphs with a prime number of points. J. Combin. Theory 3 (1967), 136-145. · Zbl 0161.20803
[30] VOGLER W.: Graphs with given group and given constant link. J. Graph Theory 8 (1984), 111-115. · Zbl 0534.05035
[31] VOGLER W.: Representing groups by graphs with constant link and hypergraphs. J. Graph Theory 10 (1986), 461-475. · Zbl 0632.05034
[32] WINKLER P. M.: Existence of graphs wirth a given set of r-neighbourhoods. J. Combin. Theory Ser. B 34 (1983), 165-176. · Zbl 0517.05056
[33] YAP H. P.: Some Topics in Graph Theory. London Mathematical Society, Lecture Note Series 108, Cambridge University Press, Cambridge, 1986. · Zbl 0588.05002
[34] ZELINKA B.: Graphs with prescribed neighbourhood graphs. Math. Slovaca 35 (1985), 195-197. · Zbl 0579.05045
[35] ZELINKA B.: Edge neighbourhood graphs. Czech. Math. J. 36 (111) (1986), 44-47. · Zbl 0599.05054
[36] ZELINKA B.: Disconnected neighbourhood graphs. Math. Slovaca 36 (1986), 109-110. · Zbl 0603.05039
[37] ZYKOV A. A.: Problem 30. Theory of Graphs and its Applications, Academia, Prague, 1964, pp. 164-165.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.