{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:44:49Z","timestamp":1787323489178,"version":"build-2736575974"},"reference-count":17,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2008,1]]},"abstract":"<jats:p>Isometric subgraphs of hypercubes are known as partial cubes. These graphs have first been investigated by Graham and Pollak [Bell System Tech. J., 50 (1971), pp. 2495\u20132519] and Djokovi\u0107 [J. Combinatorial Theory Ser. B, 14 (1973), pp. 263\u2013267]. Several papers followed with various characterizations of partial cubes. In this paper, it is proven that a subdivision of a complete graph of order n ($n \\geq 4$) is a partial cube if and only if it is isomorphic to $S(K_n)$ or there exist $n-1$ nonsubdivided edges of $K_n$ adjacent to a common vertex in the subdivision and the other edges of $K_n$ are subdivided an odd number of times. As a corollary, we build partial cubes with arbitrary graph as a minor.<\/jats:p>","DOI":"10.1137\/070681909","type":"journal-article","created":{"date-parts":[[2008,7,17]],"date-time":"2008-07-17T16:01:32Z","timestamp":1216310492000},"page":"1226-1238","source":"Crossref","is-referenced-by-count":5,"title":["Isometric Embeddings of Subdivided Complete Graphs in the Hypercube"],"prefix":"10.1137","volume":"22","author":[{"given":"Laurent","family":"Beaudou","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sylvain","family":"Gravier","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kahina","family":"Meslem","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2008,7,16]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"M. A\u00efder, S. Gravier, and K. Meslem,\n                      Isometric embeddings of subdivided connected graphs in the hypercube\n                      , in Proceedings of the 5th Cracow Conference on Graph Theory (USTRON '06), Electron. Notes Discrete Math. 24, Elsevier, Amsterdam, 2006, pp. 145\u2013151.","DOI":"10.1016\/j.endm.2006.06.045"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(02)00416-X"},{"key":"R3","first-page":"537","volume":"43","author":"Bre\u0161ar B.","year":"2002","journal-title":"Comment. Math. Univ. Carolin."},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1007\/BF01069520"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(97)00066-8"},{"key":"R6","unstructured":"V. Chepoi and C. Tardif,\n                      personal communication\n                      , 1994."},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(73)90010-5"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"D. Eppstein,\n                      Recognizing partial cubes in quadratic time\n                      , in Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2008), SIAM, Philadelphia, PA, 2008, pp. 1258\u20131266.","DOI":"10.1137\/1.9780898716474"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2004.05.001"},{"key":"R10","doi-asserted-by":"crossref","first-page":"articl","DOI":"10.37236\/1105","volume":"13","author":"Eppstein D.","year":"2006","journal-title":"Electron. J. Combin.","ISSN":"https:\/\/id.crossref.org\/issn\/1077-8926","issn-type":"print"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1971.tb02618.x"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(03)00057-8"},{"key":"R13","unstructured":"W. Imrich and S. Klav\u017ear,\n                      Product Graphs: Structure and Recognition\n                      , Wiley, New York, 2000."},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(02)00575-7"},{"key":"R15","first-page":"139","volume":"70","author":"Klav\u017ear S.","year":"2004","journal-title":"Ars Combin.","ISSN":"https:\/\/id.crossref.org\/issn\/0381-7032","issn-type":"print"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1006\/eujc.1993.1016"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(84)90069-6"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/070681909","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:05:20Z","timestamp":1787321120000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/070681909"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1]]},"references-count":17,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2008,1]]}},"alternative-id":["10.1137\/070681909"],"URL":"https:\/\/doi.org\/10.1137\/070681909","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,1]]}}}