Czechoslovak Mathematical Journal, Vol. 67, No. 1, pp. 29-36, 2017


4-cycle properties for characterizing rectagraphs and hypercubes

Khadra Bouanane, Abdelhafid Berrachedi

Received May 1, 2015.  First published February 24, 2017.

Abstract:  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.
Keywords:  hypercube; $(0,2)$-graph; rectagraph; 4-cycle; characterization
Classification MSC:  05C75


References:
[1] A. Berrachedi, M. Mollard: 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] A. E. Brouwer: 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] A. E. Brouwer, P. R. J. Östergård: 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] G. Burosch, I. Havel, J.-M. Laborde: 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] J.-M. Laborde, S. P. Rao Hebbare: Another characterization of hypercubes. Discrete Math. 39 (1982), 161-166. DOI 10.1016/0012-365X(82)90139-X | MR 0675861 | Zbl 0482.05033
[6] H. M. Mulder: $(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] H. M. Mulder: The Interval Function of a Graph. Mathematical Centre Tracts 132, Mathematisch Centrum, Amsterdam (1980). MR 0605838 | Zbl 0446.05039
[8] H. M. Mulder: Interval-regular graphs. Discrete Math. 41 (1982), 253-269. DOI 10.1016/0012-365X(82)90021-8 | MR 0676887 | Zbl 0542.05051
[9] A. Neumaier: 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] J. Nieminen, M. Peltola, P. Ruotsalainen: Two characterizations of hypercubes. Electron. J. Comb. (electronic only) 18 (2011), Research Paper 97 10 pages. MR 2795778 | Zbl 1217.05195
[11] G. Sabidussi: Graph multiplication. Math. Z. 72 (1960), 446-457. DOI 10.1007/BF01162967 | MR 0209177 | Zbl 0093.37603

Affiliations:   Khadra Bouanane, Department of Mathematics, Kasdi Merbah University, Ave 1er Novembre 1954, 30000 Ouargla, Algeria, and Faculty of Mathematics, University of Science and Technology Houari Boumediene, BP 32 El Alia, 16111 Bab Ezzouar, Algiers, Algeria, e-mail: bouanane.khadra@univ-ouargla.dz; Abdelhafid Berrachedi, Faculty of Mathematics, University of Science and Technology Houari Boumediene, BP 32 El Alia, 16111 Bab Ezzouar, Algiers, Algeria, e-mail: berrachedi.abdelhafid@usthb.dz


 
PDF available at: