Geodesic
On Some Properties of Antipodal Partial Cubes
Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 3, pp. 755-770

Voir la notice de l'article provenant de la source Library of Science

We prove that an antipodal bipartite graph is a partial cube if and only it is interval monotone. Several characterizations of the principal cycles of an antipodal partial cube are given. We also prove that an antipodal partial cube G is a prism over an even cycle if and only if its order is equal to 4(diam(G) − 1), and that the girth of an antipodal partial cube is less than its diameter whenever it is not a cycle and its diameter is at least equal to 6.
Keywords: antipodal graph, partial cube, interval monotony, girth, diameter 
Polat, Norbert. On Some Properties of Antipodal Partial Cubes. Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 3, pp. 755-770. http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a3/
@article{DMGT_2020_40_3_a3,
     author = {Polat, Norbert},
     title = {On {Some} {Properties} of {Antipodal} {Partial} {Cubes}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {755--770},
     year = {2020},
     volume = {40},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a3/}
}
TY  - JOUR
AU  - Polat, Norbert
TI  - On Some Properties of Antipodal Partial Cubes
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2020
SP  - 755
EP  - 770
VL  - 40
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a3/
LA  - en
ID  - DMGT_2020_40_3_a3
ER  - 
%0 Journal Article
%A Polat, Norbert
%T On Some Properties of Antipodal Partial Cubes
%J Discussiones Mathematicae. Graph Theory
%D 2020
%P 755-770
%V 40
%N 3
%U http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a3/
%G en
%F DMGT_2020_40_3_a3

[1] A. Berman, A. Kotzig and G. Sabidussi, Antipodal graphs of diameter 4 and extremal girth, in: Contemporary Methods in Graph Theory, R. Bodendiek (Ed(s)), (B.I. Wissenschaftsverlag, Mannheim, 1990) 137–150.

[2] B. Brešar and S. Klavžar, On partial cubes and graphs with convex intervals, Comment. Math. Univ. Carolin. 43 (2002) 537–545.

[3] V. Chepoi, Isometric subgraphs of Hamming graphs and d-convexity, Cybernetics 24 (1988) 6–11. doi:10.1007/BF01069520

[4] V. Chepoi, K. Knauer and T. Marc, Partial cubes without Q3- minors, CoRR abs/1606.02154 (2016) (submitted).

[5] J. Desharnais, Maille et plongements de graphes antipodaux, Mémoire de maitrise (Université de Montréal, 1993).

[6] D. Djoković, Distance-preserving subgraphs of hypercubes, J. Combin. Theory Ser. B 14 (1973) 263–267. doi:10.1016/0095-8956(73)90010-5

[7] V.V. Firsov, Isometric embedding of a graph in a Boolean cube, Cybernet. Systems Anal. 1 (1965) 112–113. doi:10.1007/BF01074705

[8] K. Fukuda and K. Handa, Antipodal graphs and oriented matroids, Discrete Math. 111 (1993) 245–256. doi:10.1016/0012-365X(93)90159-Q

[9] F. Glivjak, A. Kotzig and J. Plesník, Remarks on the graphs with a central symmetry, Monatsh.Math. 74 (1970) 302–307. doi:10.1007/BF01302697

[10] F. Göbel and H.J. Veldman, Even graphs, J. Graph Theory 10 (1986) 225–239. doi:10.1002/jgt.3190100212

[11] R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs, Second Edition (CRC Press, 2011).

[12] S. Klavžar and M. Kovše, On even and harmonic-even partial cubes, Ars Combin. 93 (2009) 77–86.

[13] K. Knauer and T. Marc, On tope graphs of complexes of oriented matroids, arXiv preprint, (2017). arXiv:1701.05525

[14] A. Kotzig, Centrally symmetric graphs, Czechoslovak Math. J. 18 (1968) 606–615.

[15] A. Kotzig and P. Laufer, Generalized S -graphs, Research Report CRM-779 (Centre de recherches mathématiques, Université de Montréal, 1978).

[16] T. Marc, There are no finite partial cubes of girth more than 6 and minimum degree at least 3, European J. Combin. 55 (2016) 62–72. doi:10.1016/j.ejc.2016.01.005

[17] H.M. Mulder, The structure of median graphs, Discrete Math. 24 (1978) 197–204. doi:10.1016/0012-365X(78)90199-1

[18] S. Ovchinnikov, Partial cubes: structures, characterizations, and constructions, Discrete Math. 308 (2008) 5597–5621. doi:10.1016/j.disc.2007.10.025

[19] N. Polat, Netlike partial cubes I. General properties, Discrete Math. 307 (2007) 2704–2722. doi:10.1016/j.disc.2007.01.018

[20] N. Polat, On some characterizations of antipodal partial cubes, Discuss. Math. Graph Theory, to appear. doi:10.7151/dmgt.2083

[21] G. Sabidussi, Graphs without dead ends, European J. Combin. 17 (1996) 69–87. doi:10.1006/eujc.1996.0006

[22] C. Tardif, Planar antipodal bipartite graphs, manuscript (1991).

[23] P. Winkler, Isometric embedding in products of complete graphs, Discrete Appl. Math. 7 (1984) 221–225. doi:10.1016/0166-218X(84)90069-6