Geodesic
4-cycle properties for characterizing rectagraphs and hypercubes
Czechoslovak Mathematical Journal, Tome 67 (2017) no. 1, pp. 29-36
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.21136/CMJ.2017.0227-15
Classification : 05C75
Keywords: hypercube; $(0, 2)$-graph; rectagraph; 4-cycle; characterization 
@article{10_21136_CMJ_2017_0227_15,
     author = {Bouanane, Khadra and Berrachedi, Abdelhafid},
     title = {4-cycle properties for characterizing rectagraphs and hypercubes},
     journal = {Czechoslovak Mathematical Journal},
     pages = {29--36},
     year = {2017},
     volume = {67},
     number = {1},
     doi = {10.21136/CMJ.2017.0227-15},
     mrnumber = {3632996},
     zbl = {06738502},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2017.0227-15/}
}
TY  - JOUR
AU  - Bouanane, Khadra
AU  - Berrachedi, Abdelhafid
TI  - 4-cycle properties for characterizing rectagraphs and hypercubes
JO  - Czechoslovak Mathematical Journal
PY  - 2017
SP  - 29
EP  - 36
VL  - 67
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2017.0227-15/
DO  - 10.21136/CMJ.2017.0227-15
LA  - en
ID  - 10_21136_CMJ_2017_0227_15
ER  - 
%0 Journal Article
%A Bouanane, Khadra
%A Berrachedi, Abdelhafid
%T 4-cycle properties for characterizing rectagraphs and hypercubes
%J Czechoslovak Mathematical Journal
%D 2017
%P 29-36
%V 67
%N 1
%U http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2017.0227-15/
%R 10.21136/CMJ.2017.0227-15
%G en
%F 10_21136_CMJ_2017_0227_15
Bouanane, Khadra; Berrachedi, Abdelhafid. 4-cycle properties for characterizing rectagraphs and hypercubes. Czechoslovak Mathematical Journal, Tome 67 (2017) no. 1, pp. 29-36. doi: 10.21136/CMJ.2017.0227-15

[1] Berrachedi, A., Mollard, M.: Median graphs and hypercubes, some new characterizations. Discrete Math. 208-209 (1999), 71-75. | DOI | MR | JFM

[2] Brouwer, A. E.: Classification of small $(0,2)$-graphs. J. Comb. Theory Ser. A 113 (2006), 1636-1645. | DOI | MR | JFM

[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 | MR | JFM

[4] Burosch, G., Havel, I., Laborde, J.-M.: Distance monotone graphs and a new characterization of hypercubes. Discrete Math. 110 (1992), 9-16. | DOI | MR | JFM

[5] Laborde, J.-M., Hebbare, S. P. Rao: Another characterization of hypercubes. Discrete Math. 39 (1982), 161-166. | DOI | MR | JFM

[6] Mulder, H. M.: $(0,\lambda )$-graphs and $n$-cubes. Discrete Math. 28 (1979), 179-188. | DOI | MR | JFM

[7] Mulder, H. M.: The Interval Function of a Graph. Mathematical Centre Tracts 132, Mathematisch Centrum, Amsterdam (1980). | MR | JFM

[8] Mulder, H. M.: Interval-regular graphs. Discrete Math. 41 (1982), 253-269. | DOI | MR | JFM

[9] Neumaier, A.: Rectagraphs, diagrams, and Suzuki's sporadic simple group. Ann. Discrete Math. 15 (1982), 305-318. | DOI | MR | JFM

[10] Nieminen, J., Peltola, M., Ruotsalainen, P.: Two characterizations of hypercubes. Electron. J. Comb. (electronic only) 18 (2011), Research Paper 97 10 pages. | MR | JFM

[11] Sabidussi, G.: Graph multiplication. Math. Z. 72 (1960), 446-457. | DOI | MR | JFM

Cité par Sources :