Geodesic
On Some Characterizations of Antipodal Partial Cubes
Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 2, pp. 439-453

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

We prove that any harmonic partial cube is antipodal, which was conjectured by Fukuda and K. Handa, Antipodal graphs and oriented matroids, Discrete Math. 111 (1993) 245–256. Then we prove that a partial cube G is antipodal if and only if the subgraphs induced by Wab and Wba are isomorphic for every edge ab of G. This gives a positive answer to a question of Klavžar and Kovše, On even and harmonic-even partial cubes, Ars Combin. 93 (2009) 77–86. Finally we prove that the distance-balanced partial cube that are antipodal are those whose pre-hull number is at most 1.
Keywords: diametrical graph, harmonic graph, antipodal graph, distance-balanced graph, partial cube, pre-hull number 
Polat, Norbert. On Some Characterizations of Antipodal Partial Cubes. Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 2, pp. 439-453. http://geodesic.mathdoc.fr/item/DMGT_2019_39_2_a9/
@article{DMGT_2019_39_2_a9,
     author = {Polat, Norbert},
     title = {On {Some} {Characterizations} of {Antipodal} {Partial} {Cubes}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {439--453},
     year = {2019},
     volume = {39},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2019_39_2_a9/}
}
TY  - JOUR
AU  - Polat, Norbert
TI  - On Some Characterizations of Antipodal Partial Cubes
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2019
SP  - 439
EP  - 453
VL  - 39
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_2019_39_2_a9/
LA  - en
ID  - DMGT_2019_39_2_a9
ER  - 
%0 Journal Article
%A Polat, Norbert
%T On Some Characterizations of Antipodal Partial Cubes
%J Discussiones Mathematicae. Graph Theory
%D 2019
%P 439-453
%V 39
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_2019_39_2_a9/
%G en
%F DMGT_2019_39_2_a9

[1] H.-J. Bandelt and A.W.M. Dress, A canonical decomposition theory for metrics on a finite set, Adv. Math. 92 (1992) 47–105. doi:10.1016/0001-8708(92)90061-O

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

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

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

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

[6] D. Eppstein, The lattice dimension of a graph, European J. Combin. 26 (2005) 585–592. doi:10.1016/j.ejc.2004.05.001

[7] M. Faghani, E. Pourhadi and H. Kharazi, On the new extension of distance-balanced graphs, Trans. Comb. 5 (2016) 23–34.

[8] V.V. Firsov, Isometric embedding of a graph into a Boolean cube, Cybernetics 1 (1965) 112–113. doi:10.1007/BF01074705

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

[10] 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

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

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

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

[14] A. Ilíc, S. Klavžar and M. Milanovíc, On distance-balanced graphs, European J. Combin. 31 (2010) 732–737. doi:10.1016/j.ejc.2009.10.006

[15] J. Jerebic, S. Klavžar and D.F. Rall, Distance-balanced graphs, Ann. Comb. 12 (2008) 71–79. doi:10.1007/s00026-008-0337-2

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

[17] S. Klavžar and H.M. Mulder, Partial cubes and crossing graphs, SIAM J. Discrete Math. 15 (2002)) 235–251. doi:10.1137/S0895480101383202

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

[19] A. Kotzig and P. Laufer, Generalized S -Graphs, preprint CRM-779, Centre de recherches mathématiques (Université de Montréal, 1978).

[20] 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

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

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

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

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

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

[26] N. Polat and G. Sabidussi, On the geodesic pre-hull number of a graph, European J. Combin. 30 (2009) 1205–1220. doi:10.1016/j.ejc.2008.09.022

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

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