Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
hypercube; $(0,2)$-graph; rectagraph; 4-cycle; characterization
hypercube; $(0,2)$-graph; rectagraph; 4-cycle; characterization
Summary:
A $(0,2)$-graph is a connected graph, where each pair of vertices has either 0 or 2 common neighbours. These graphs constitute a subclass of $(0,\lambda )$-graphs introduced by Mulder in 1979. A rectagraph, well known in diagram geometry, is a triangle-free $(0,2)$-graph. $(0,2)$-graphs include hypercubes, folded cube graphs and some particular graphs such as icosahedral graph, Shrikhande graph, Klein graph, Gewirtz graph, etc. In this paper, we give some local properties of 4-cycles in $(0,\lambda )$-graphs and more specifically in $(0,2)$-graphs, leading to new characterizations of rectagraphs and hypercubes.
References:
[1] Berrachedi, A., Mollard, M.: Median graphs and hypercubes, some new characterizations. Discrete Math. 208-209 (1999), 71-75. DOI 10.1016/S0012-365X(99)00063-1 | MR 1725521 | Zbl 0933.05133
[2] Brouwer, A. E.: Classification of small $(0,2)$-graphs. J. Comb. Theory Ser. A 113 (2006), 1636-1645. DOI 10.1016/j.jcta.2006.03.023 | MR 2269544 | Zbl 1105.05009
[3] Brouwer, A. E., Östergård, P. R. J.: Classification of the {$(0,2)$}-graphs of valency 8. Discrete Math. 309 (2009), 532-547. DOI 10.1016/j.disc.2008.07.037 | MR 2499006 | Zbl 1194.05129
[4] Burosch, G., Havel, I., Laborde, J.-M.: Distance monotone graphs and a new characterization of hypercubes. Discrete Math. 110 (1992), 9-16. DOI 10.1016/0012-365X(92)90696-D | MR 1197441 | Zbl 0768.05033
[5] Laborde, J.-M., Hebbare, S. P. Rao: Another characterization of hypercubes. Discrete Math. 39 (1982), 161-166. DOI 10.1016/0012-365X(82)90139-X | MR 0675861 | Zbl 0482.05033
[6] Mulder, H. M.: $(0,\lambda )$-graphs and $n$-cubes. Discrete Math. 28 (1979), 179-188. DOI 10.1016/0012-365X(79)90095-5 | MR 0546651 | Zbl 0418.05034
[7] Mulder, H. M.: The Interval Function of a Graph. Mathematical Centre Tracts 132, Mathematisch Centrum, Amsterdam (1980). MR 0605838 | Zbl 0446.05039
[8] Mulder, H. M.: Interval-regular graphs. Discrete Math. 41 (1982), 253-269. DOI 10.1016/0012-365X(82)90021-8 | MR 0676887 | Zbl 0542.05051
[9] Neumaier, A.: Rectagraphs, diagrams, and Suzuki's sporadic simple group. Ann. Discrete Math. 15 (1982), 305-318. DOI 10.1016/S0304-0208(08)73275-4 | MR 0772605 | Zbl 0491.05033
[10] Nieminen, J., Peltola, M., Ruotsalainen, P.: Two characterizations of hypercubes. Electron. J. Comb. (electronic only) 18 (2011), Research Paper 97 10 pages. MR 2795778 | Zbl 1217.05195
[11] Sabidussi, G.: Graph multiplication. Math. Z. 72 (1960), 446-457. DOI 10.1007/BF01162967 | MR 0209177 | Zbl 0093.37603
Search
Partner of
