×

Graphs which are edge-locally \(C_n\). (English) Zbl 0958.05037

The neighbourhood of an edge \(e\) of a graph \(G\) is the set of vertices which are adjacent to the end vertices of \(e\) and are distinct from them. If this set induces a subgraph isomorphic to a circuit \(C_n\) of length \(n\), the graph \(G\) is called edge-locally \(C_n\). Analogously a vertex-locally \(C_n\) graph is defined. The edge-locally \(C_n\) graphs containing circuits are characterized, using the property of being vertex-locally \(C_n\). The main result states that an edge-locally \(C_n\) graph exists if and only if \(n = 3\) or \(n\) is even, \(n > 4\), and that for each \(n \geq 8\) there are infinitely many connected edge-locally \(C_n\) graphs. A construction of such graphs is described. Interconnections with group theory are mentioned.

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C75 Structural characterization of families of graphs
PDFBibTeX XMLCite
Full Text: EuDML

References:

[1] BLASS A.-HARARY F.-MILLER Z.: Which trees are link graphs?. J. Combin. Theory Ser. B 29 (1980), 277-292. · Zbl 0448.05028 · doi:10.1016/0095-8956(80)90085-4
[2] BROWN M.-CONNELLY R.: On graphs with a constant link. New Directions in The Theory of Graphs (F. Harary, Academic Press, New York, 1973, pp. 19-51. · Zbl 0258.05104
[3] BULITKO V. K.: O grafach s zadanymi okruzeniami veršin. Trudy Mat. Inst. Steklov. 133 (1973), 78-94.
[4] BUSSET D.: Graphs which are locally a cube. Discrete Math. 46 (1983), 221-229.
[5] CHILTON B. L.-GOULD R.-POLIMENI A. D.: A note on graphs whose neighbourhoods are n-cycles. Geom. Dedicata 3 (1974), 289-294. · Zbl 0325.05116 · doi:10.1007/BF00181321
[6] COXETER H. S. M.-MOSER W. O.: Generators and Relations for Discrete Groups. (3rd.. Ergeb. Math. Grenzgeb. 14, Springer, Berlin, 1972. · Zbl 0239.20040
[7] FRONČEK D.: Graphs with a given edge neighbourhood. Czechoslovak Math. J. 39(114) (1989), 627-630. · Zbl 0724.05063
[8] GROSS J. L.-TUCKER T. W.: Topological Graph Theory. Wiley-Interscience, New York, 1987. · Zbl 0621.05013
[9] HALL J. I.: A local characterization of the Johnson Scheme. Combinatorica 7 (1987), 77-85. · Zbl 0653.05019 · doi:10.1007/BF02579203
[10] HALL J. I.: Locally Petersen graphs. J. Graph Theory 4 (1980), 173-187. · Zbl 0407.05041 · doi:10.1002/jgt.3190040206
[11] HARARY F.: Graph Theory. Addison-Wesley, Reading, 1969. · Zbl 0196.27202
[12] HELL P.: Graphs with given neighbourhoods I. Problémes combinatoires et theorie des graphes, Proc. Coll. Int. C. N. R. S., Orsay, 1976.
[13] JENDROL’ S.-NEDELA R.-ŠKOVIERA M.: Generating maps from their planar quotients. Math. Slovaca 47 (1997), 155-170.
[14] JONES G. A.-SINGERMAN D.: Theory of maps on orientable surfaces. Proc. London Math. Soc. (3) 37 (1978), 273-307. · Zbl 0391.05024 · doi:10.1112/plms/s3-37.2.273
[15] NEDELA R.-ŠKOVIERA M.: Exponents of orientable maps. Proc. London Math. Soc. 75 (1997), 1-31. · Zbl 0877.05012 · doi:10.1112/S0024611597000245
[16] PARSONS T. D.-PISANSKI T.: Graphs which are locally paths. Combinatorics and Graph Theory (Z. Skupien, M. Borowiecky, Banach Center Publications Vol. 25, PWN - Pol. Sci. Publ., Warszawa, 1989, pp. 163-175. · Zbl 0757.05071
[17] RONAN M. A.: On the second homotopy group of certain simplicial complexes and some combinatorial applications. Quart. J. Math. Oxford Ser. (2) 32 (1981), 225-233. · Zbl 0466.57004 · doi:10.1093/qmath/32.2.225
[18] VINCE A.: Locally homogeneous graphs from groups. J. Graph Theory 5 (1981), 417-422. · Zbl 0472.05055 · doi:10.1002/jgt.3190050411
[19] VOGLER W.: Representing groups by graphs with constant link and hypergraphs. J. Graph Theory 10 (1986), 461-475. · Zbl 0632.05034 · doi:10.1002/jgt.3190100406
[20] WHITE A. T.: Graphs, Groups and Surfaces. North-Holland, Amsterdam, 1984. · Zbl 0551.05037
[21] ZELINKA B.: Edge neighbourhood graphs. Czechoslovak Math. J. 36(111) (1986), 44-47. · Zbl 0599.05054
[22] ZYKOV A. A.: Problem 30. Theory of Graphs and Its Applications. Proc. Symp. Smolenice 1963, Praha, 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.