Geodesic
On Antipodal and Diametrical Partial Cubes
Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 4, pp. 1127-1145.

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

We prove that any diametrical partial cube of diameter at most 6 is antipodal. Because any antipodal graph is harmonic, this gives a partial answer to a question of Fukuda and Handa [Antipodal graphs and oriented matroids, Discrete Math. 111 (1993) 245–256] whether any diametrical partial cube is harmonic, and improves a previous result of Klavžar and Kovše [On even and harmonic-even partial cubes, Ars Combin. 93 (2009) 77–86].
Keywords: diametrical graph, harmonic graph, antipodal graph, partial cube, diameter, isometric dimension 
@article{DMGT_2021_41_4_a17,
     author = {Polat, Norbert},
     title = {On {Antipodal} and {Diametrical} {Partial} {Cubes}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1127--1145},
     publisher = {mathdoc},
     volume = {41},
     number = {4},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a17/}
}
TY  - JOUR
AU  - Polat, Norbert
TI  - On Antipodal and Diametrical Partial Cubes
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2021
SP  - 1127
EP  - 1145
VL  - 41
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a17/
LA  - en
ID  - DMGT_2021_41_4_a17
ER  - 
%0 Journal Article
%A Polat, Norbert
%T On Antipodal and Diametrical Partial Cubes
%J Discussiones Mathematicae. Graph Theory
%D 2021
%P 1127-1145
%V 41
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a17/
%G en
%F DMGT_2021_41_4_a17
Polat, Norbert. On Antipodal and Diametrical Partial Cubes. Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 4, pp. 1127-1145. http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a17/

[1] K. Balakrishnan, B. Brešar, M. Changat, S. Klavžar, I. Peterin and A.R. Subhamathi, Almost self-centered median and chordal graphs, Taiwanese J. Math. 16 (2012) 1911–1922. https://doi.org/10.11650/twjm/1500406804

[2] V. Chepoi, Isometric subgraphs of Hamming graphs and d-convexity, Cybernet. Systems Anal. 24 (1988) 6–11. https://doi.org/10.1007/BF01069520

[3] J. Desharnais, Maille et Plongements de Graphes Antipodaux (Mémoire de Maitrise, Université de Montréal, 1993).

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

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

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

[7] F. Glivjak, A. Kotzig and J. Plesnik, Remarks on graphs with a central symmetry, Monatsh. Math. 74 (1970) 302–307. https://doi.org/10.1007/BF01302697

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

[9] R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs, Second Edition (CRC Press, Boca Raton, 2011). https://doi.org/10.1201/b10959

[10] K. Handa, Bipartite graphs with balanced ( a, b ) -partitions, Ars Combin. 51 (1999) 113–119.

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

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

[13] A. Kotzig, Centrally symmetric graphs, Czechoslovak Math. J. 18 (1968) 605–615, in Russian.

[14] A. Kotzig and P. Laufer, Generalized S-graphs, preprint CRM-779, Centre de Recherches Mathématiques (Université de Montréal, 1978).

[15] 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. https://doi.org/10.1016/j.ejc.2016.01.005

[16] H.M. Mulder, n-cubes and median graphs, J. Graph Theory 4 (1980) 107–110. https://doi.org/10.1002/jgt.3190040112

[17] K.R. Parthasarathy and R. Nandakumar, Unique eccentric point graphs, Discrete Math. 46 (1983) 69–74. https://doi.org/10.1016/0012-365X(83)90271-6

[18] N. Polat, On some characterizations of antipodal partial cubes, Discuss. Math. Graph Theory 39 (2019) 439–453. https://doi.org/10.7151/dmgt.2083

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

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