On some properties of antipodal partial cubes. (English) Zbl 1439.05072
Summary: 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(\operatorname{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.
References:
| [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. · Zbl 0722.05042 |
| [2] | B. Brešar and S. Klavžar, On partial cubes and graphs with convex intervals, Comment. Math. Univ. Carolin. 43 (2002) 537-545. · Zbl 1090.05023 |
| [3] | V. Chepoi, Isometric subgraphs of Hamming graphs and d-convexity, Cybernetics 24 (1988) 6-11. doi:10.1007/BF01069520 · Zbl 0739.05035 |
| [4] | V. Chepoi, K. Knauer and T. Marc, Partial cubes without Q_3^- minors, CoRR abs/1606.02154 (2016) (submitted). · Zbl 1433.05228 |
| [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 · Zbl 0245.05113 |
| [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 · Zbl 0782.05069 |
| [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 · Zbl 0202.55701 |
| [10] | F. Göbel and H.J. Veldman, Even graphs, J. Graph Theory 10 (1986) 225-239. doi:10.1002/jgt.3190100212 · Zbl 0593.05055 |
| [11] | R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs, Second Edition (CRC Press, 2011). · Zbl 1283.05001 |
| [12] | S. Klavžar and M. Kovše, On even and harmonic-even partial cubes, Ars Combin. 93 (2009) 77-86. · Zbl 1224.05146 |
| [13] | K. Knauer and T. Marc, On tope graphs of complexes of oriented matroids, arXiv preprint, (2017). arXiv:1701.05525 · Zbl 1431.05034 |
| [14] | A. Kotzig, Centrally symmetric graphs, Czechoslovak Math. J. 18 (1968) 606-615. · Zbl 0165.57304 |
| [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 · Zbl 1333.05205 |
| [17] | H.M. Mulder, The structure of median graphs, Discrete Math. 24 (1978) 197-204. doi:10.1016/0012-365X(78)90199-1 · Zbl 0394.05038 |
| [18] | S. Ovchinnikov, Partial cubes: structures, characterizations, and constructions, Discrete Math. 308 (2008) 5597-5621. doi:10.1016/j.disc.2007.10.025 · Zbl 1186.05102 |
| [19] | N. Polat, Netlike partial cubes I. General properties, Discrete Math. 307 (2007) 2704-2722. doi:10.1016/j.disc.2007.01.018 · Zbl 1127.05087 |
| [20] | N. Polat, On some characterizations of antipodal partial cubes, Discuss. Math. Graph Theory, to appear. doi:10.7151/dmgt.2083 · Zbl 1404.05043 |
| [21] | G. Sabidussi, Graphs without dead ends, European J. Combin. 17 (1996) 69-87. doi:10.1006/eujc.1996.0006 · Zbl 0842.05028 |
| [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 · Zbl 0529.05055 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
