Partial cube

<h2 id="history">History</h2>
Firsov (1965) was the first to study isometric embeddings of graphs into hypercubes. The graphs that admit such embeddings were characterized by Djoković (1973) and Winkler (1984), and were later named partial cubes. A separate line of research on the same structures, in the terminology of <a href="/facts/Family_of_sets/WbYof7lP">families of sets</a> rather than of hypercube labelings of graphs, was followed by Kuzmin & Ovchinnikov (1975) and Falmagne & Doignon (1997), among others.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a>

<h2 id="examples">Examples</h2>

Every <a href="/facts/Tree_(graph_theory)/TCWk4Joy">tree</a> is a partial cube. For, suppose that a tree T has m edges, and number these edges (arbitrarily) from 0 to m – 1. Choose a root vertex r for the tree, arbitrarily, and label each vertex v with a string of m bits that has a 1 in position i whenever edge i lies on the path from r to v in T. For instance, r itself will have a label that is all zero bits, its neighbors will have labels with a single 1-bit, etc. Then the <a href="/facts/Hamming_distance/MgdtbYPo">Hamming distance</a> between any two labels is the <a href="/facts/Distance_(graph_theory)/EmQFKvqa">distance</a> between the two vertices in the tree, so this labeling shows that T is a partial cube.
Every <a href="/facts/Hypercube_graph/pwfGEl9J">hypercube graph</a> is itself a partial cube, which can be labeled with all the different bitstrings of length equal to the dimension of the hypercube.
More complex examples include the following:

<ul><li>Consider the graph whose vertex labels consist of all possible (2n + 1)-digit bitstrings that have either n or n + 1 nonzero bits, where two vertices are adjacent whenever their labels differ by a single bit. This labeling defines an embedding of these graphs into a hypercube (the graph of all bitstrings of a given length, with the same adjacency-condition) that turns out to be distance-preserving. The resulting graph is a <a href="/facts/Kneser_graph/Iu0TVMKT">bipartite Kneser graph</a>; the graph formed in this way with n = 2 has 20 vertices and 30 edges, and is called the <a href="/facts/Desargues_graph/M6sXWfFK">Desargues graph</a>.</li>
<li>All <a href="/facts/Median_graph/xl4m0C9I">median graphs</a> are partial cubes.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> The trees and hypercube graphs are examples of median graphs. Since the median graphs include the <a href="/facts/Squaregraph/IAJaxdIp">squaregraphs</a>, <a href="/facts/Simplex_graph/79wHGpT2">simplex graphs</a>, and <a href="/facts/Fibonacci_cube/2dgHmmlm">Fibonacci cubes</a>, as well as the covering graphs of finite <a href="/facts/Distributive_lattice/97DFz1cu">distributive lattices</a>, these are all partial cubes.</li>
<li>The <a href="/facts/Planar_dual/1t14hhEF">planar dual</a> graph of an <a href="/facts/Arrangement_of_lines/15uaSKRu">arrangement of lines</a> in the <a href="/facts/Euclidean_plane/tAUtRFcn">Euclidean plane</a> is a partial cube. More generally, for any <a href="/facts/Hyperplane_arrangement/78c23rYy">hyperplane arrangement</a> in <a href="/facts/Euclidean_space/R2UbzmzM">Euclidean space</a> of any number of dimensions, the graph that has a vertex for each cell of the arrangement and an edge for each two adjacent cells is a partial cube.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a></li>
<li>A partial cube in which every vertex has exactly three neighbors is known as a <a href="/facts/Cubic_graph/6M32WUIJ">cubic</a> partial cube. Although several infinite families of cubic partial cubes are known, together with many other sporadic examples, the only known cubic partial cube that is not a <a href="/facts/Planar_graph/plREagr9">planar graph</a> is the Desargues graph.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a></li>
<li>The underlying graph of any <a href="/facts/Antimatroid/hYBJb89z">antimatroid</a>, having a vertex for each set in the antimatroid and an edge for every two sets that differ by a single element, is always a partial cube.</li>
<li>The <a href="/facts/Cartesian_product_of_graphs/wC4JJdyU">Cartesian product</a> of any finite set of partial cubes is another partial cube.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a></li>
<li>A <a href="/facts/Homeomorphism_(graph_theory)/WbFo1mNW">subdivision</a> of a <a href="/facts/Complete_graph/AYD6hUqI">complete graph</a> is a partial cube if and only if either every complete graph edge is subdivided into a two-edge path, or there is one complete graph vertex whose incident edges are all unsubdivided and all non-incident edges have been subdivided into even-length paths.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a></li></ul>
<h2 id="the-djokoviwinkler-relation">The Djoković–Winkler relation</h2>
Many of the theorems about partial cubes are based directly or indirectly upon a certain <a href="/facts/Binary_relation/r9BwGgaK">binary relation</a> defined on the edges of the graph. This relation, first described by Djoković (1973) and given an equivalent definition in terms of distances by Winkler (1984), is denoted by 
 
 
 
 Θ
 
 
 {\displaystyle \Theta }
 
. Two edges 
 
 
 
 e
 =
 {
 x
 ,
 y
 }
 
 
 {\displaystyle e=\{x,y\}}
 
 and 
 
 
 
 f
 =
 {
 u
 ,
 v
 }
 
 
 {\displaystyle f=\{u,v\}}
 
 are defined to be in the relation 
 
 
 
 Θ
 
 
 {\displaystyle \Theta }
 
, written 
 
 
 
 e
 
 
 Θ
 
 
 f
 
 
 {\displaystyle e{\mathrel {\Theta }}f}
 
, if

d
 (
 x
 ,
 u
 )
 +
 d
 (
 y
 ,
 v
 )
 ≠
 d
 (
 x
 ,
 v
 )
 +
 d
 (
 y
 ,
 u
 )
 
 
 {\displaystyle d(x,u)+d(y,v)\not =d(x,v)+d(y,u)}
 
. This relation is <a href="/facts/Reflexive_relation/NzTytEg9">reflexive</a> and <a href="/facts/Symmetric_relation/ekCWDIAH">symmetric</a>, but in general it is not <a href="/facts/Transitive_relation/9r90y50r">transitive</a>.
Winkler showed that a <a href="/facts/Connectivity_(graph_theory)/FSNjsYhz">connected</a> graph is a partial cube if and only if it is <a href="/facts/Bipartite_graph/xWcXV9MB">bipartite</a> and the relation 
 
 
 
 Θ
 
 
 {\displaystyle \Theta }
 
 is transitive.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a> In this case, it forms an <a href="/facts/Equivalence_relation/1MQ5rtkW">equivalence relation</a> and each equivalence class separates two connected subgraphs of the graph from each other. A Hamming labeling may be obtained by assigning one bit of each label to each of the equivalence classes of the Djoković–Winkler relation; in one of the two connected subgraphs separated by an equivalence class of edges, all of the vertices have a 0 in that position of their labels, and in the other connected subgraph all of the vertices have a 1 in the same position.

<h2 id="recognition">Recognition</h2>
Partial cubes can be recognized, and a Hamming labeling constructed, in 
 
 
 
 O
 (
 
 n
 
 2
 
 
 )
 
 
 {\displaystyle O(n^{2})}
 
 time, where 
 
 
 
 n
 
 
 {\displaystyle n}
 
 is the number of vertices in the graph.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a> Given a partial cube, it is straightforward to construct the equivalence classes of the Djoković–Winkler relation by doing a <a href="/facts/Breadth_first_search/2kulDXCx">breadth first search</a> from each vertex, in total time 
 
 
 
 O
 (
 n
 m
 )
 
 
 {\displaystyle O(nm)}
 
; the 
 
 
 
 O
 (
 
 n
 
 2
 
 
 )
 
 
 {\displaystyle O(n^{2})}
 
-time recognition algorithm speeds this up by using <a href="/facts/Bit-level_parallelism/HgFdRBM3">bit-level parallelism</a> to perform multiple breadth first searches in a single pass through the graph, and then applies a separate algorithm to verify that the result of this computation is a valid partial cube labeling.

<h2 id="dimension">Dimension</h2>
The isometric dimension of a partial cube is the minimum dimension of a hypercube onto which it may be isometrically embedded, and is equal to the number of equivalence classes of the Djoković–Winkler relation. For instance, the isometric dimension of an 
 
 
 
 n
 
 
 {\displaystyle n}
 
-vertex tree is its number of edges, 
 
 
 
 n
 −
 1
 
 
 {\displaystyle n-1}
 
. An embedding of a partial cube onto a hypercube of this dimension is unique, up to symmetries of the hypercube.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a>
Every hypercube and therefore every partial cube can be embedded isometrically into an <a href="/facts/Integer_lattice/h4FP4pjm">integer lattice</a>. The lattice dimension of a graph is the minimum dimension of an integer lattice into which the graph can be isometrically embedded. The lattice dimension may be significantly smaller than the isometric dimension; for instance, for a tree it is half the number of leaves in the tree (rounded up to the nearest integer). The lattice dimension of any graph, and a lattice embedding of minimum dimension, may be found in <a href="/facts/Polynomial_time/77T62gmf">polynomial time</a> by an algorithm based on <a href="/facts/Maximum_matching/oKaChmBt">maximum matching</a> in an auxiliary graph.<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a>
Other types of dimension of partial cubes have also been defined, based on embeddings into more specialized structures.<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a>

<h2 id="application-to-chemical-graph-theory">Application to chemical graph theory</h2>
Isometric embeddings of graphs into hypercubes have an important application in <a href="/facts/Chemical_graph_theory/bst0G88w">chemical graph theory</a>. A benzenoid graph is a graph consisting of all vertices and edges lying on and in the interior of a cycle in a <a href="/facts/Hexagonal_lattice/p6Qtm7FB">hexagonal lattice</a>. Such graphs are the <a href="/facts/Molecular_graph/RqdFhT5h">molecular graphs</a> of the <a href="/facts/Benzenoid_hydrocarbon/K52xSfNC">benzenoid hydrocarbons</a>, a large class of organic molecules. Every such graph is a partial cube. A Hamming labeling of such a graph can be used to compute the <a href="/facts/Wiener_index/ablp743I">Wiener index</a> of the corresponding molecule, which can then be used to predict certain of its chemical properties.<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a>
A different molecular structure formed from carbon, the <a href="/facts/Diamond_cubic/6dK7DpGB">diamond cubic</a>, also forms partial cube graphs.<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a>

<h2 id="notes">Notes</h2>

<ul><li>Beaudou, Laurent; Gravier, Sylvain; Meslem, Kahina (2008), <a href="https://hal.archives-ouvertes.fr/hal-00187039/file/clique_partial_cubes.pdf">"Isometric embeddings of subdivided complete graphs in the hypercube"</a> (PDF), SIAM Journal on Discrete Mathematics, 22 (3): 1226–1238, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1137%2F070681909">10.1137/070681909</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=2424849">2424849</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:6332951">6332951</a></li>
<li>Cabello, S.; <a href="/facts/David_Eppstein/hIjTU6nC">Eppstein, D.</a>; Klavžar, S. (2011), "The Fibonacci dimension of a graph", Electronic Journal of Combinatorics, 18 (1), P55, <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/0903.2507">0903.2507</a>, <a href="/facts/Bibcode_(identifier)/9HtdQSGB">Bibcode</a>:<a href="https://ui.adsabs.harvard.edu/abs/2009arXiv0903.2507C">2009arXiv0903.2507C</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.37236%2F542">10.37236/542</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:9363180">9363180</a>.</li>
<li>Djoković, Dragomir Ž. (1973), "Distance-preserving subgraphs of hypercubes", <a href="/facts/Journal_of_Combinatorial_Theory/oYS6G76K">Journal of Combinatorial Theory</a>, Series B, 14 (3): 263–267, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0095-8956%2873%2990010-5">10.1016/0095-8956(73)90010-5</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0314669">0314669</a>.</li>
<li><a href="/facts/David_Eppstein/hIjTU6nC">Eppstein, David</a> (2005), "The lattice dimension of a graph", European Journal of Combinatorics, 26 (6): 585–592, <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/cs.DS/0402028">cs.DS/0402028</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2Fj.ejc.2004.05.001">10.1016/j.ejc.2004.05.001</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:7482443">7482443</a>.</li>
<li><a href="/facts/David_Eppstein/hIjTU6nC">Eppstein, David</a> (2006), <a href="http://www.combinatorics.org/Volume_13/Abstracts/v13i1r79.html">"Cubic partial cubes from simplicial arrangements"</a>, Electronic Journal of Combinatorics, 13 (1), R79, <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/math.CO/0510263">math.CO/0510263</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.37236%2F1105">10.37236/1105</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:8608953">8608953</a>.</li>
<li><a href="/facts/David_Eppstein/hIjTU6nC">Eppstein, David</a> (2008), "Recognizing partial cubes in quadratic time", Proc. 19th ACM-SIAM Symposium on Discrete Algorithms, pp. 1258–1266, <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/0705.1025">0705.1025</a>, <a href="/facts/Bibcode_(identifier)/9HtdQSGB">Bibcode</a>:<a href="https://ui.adsabs.harvard.edu/abs/2007arXiv0705.1025E">2007arXiv0705.1025E</a>.</li>
<li><a href="/facts/David_Eppstein/hIjTU6nC">Eppstein, David</a> (2009), "Isometric diamond subgraphs", <a href="/facts/International_Symposium_on_Graph_Drawing/KNNSXw64">Proc. 16th International Symposium on Graph Drawing, Heraklion, Crete, 2008</a>, Lecture Notes in Computer Science, vol. 5417, Springer-Verlag, pp. 384–389, <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/0807.2218">0807.2218</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F978-3-642-00219-9_37">10.1007/978-3-642-00219-9_37</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-642-00218-2, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:14066610">14066610</a>.</li>
<li><a href="/facts/Jean-Claude_Falmagne/uMyr6gLA">Falmagne, J.-C.</a>; Doignon, J.-P. (1997), <a href="https://dipot.ulb.ac.be/dspace/bitstream/2013/303273/3/1997s_Falmagne_Doignon.pdf">"Stochastic evolution of rationality"</a> (PDF), Theory and Decision, 43 (2): 107–138, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1023%2FA%3A1004981430688">10.1023/A:1004981430688</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:117983644">117983644</a>.</li>
<li>Firsov, V.V. (1965), "On isometric embedding of a graph into a Boolean cube", Cybernetics, 1: 112–113, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2Fbf01074705">10.1007/bf01074705</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:121572742">121572742</a>. As cited by Ovchinnikov (2011).</li>
<li>Hadlock, F.; Hoffman, F. (1978), "Manhattan trees", Utilitas Mathematica, 13: 55–67. As cited by Ovchinnikov (2011).</li>
<li>Imrich, Wilfried; Klavžar, Sandi (2000), Product Graphs: Structure and Recognition, Wiley-Interscience Series in Discrete Mathematics and Optimization, New York: John Wiley & Sons, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-471-37039-0, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1788124">1788124</a>.</li>
<li>Klavžar, Sandi; Gutman, Ivan; <a href="/facts/Bojan_Mohar/5Djly8Ax">Mohar, Bojan</a> (1995), <a href="http://www.fmf.uni-lj.si/~klavzar/preprints/labeling-benzi.pdf">"Labeling of benzenoid systems which reflects the vertex-distance relations"</a> (PDF), Journal of Chemical Information and Computer Sciences, 35 (3): 590–593, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1021%2Fci00025a030">10.1021/ci00025a030</a>.</li>
<li>Kuzmin, V.; Ovchinnikov, S. (1975), "Geometry of preferences spaces I", Automation and Remote Control, 36: 2059–2063. As cited by Ovchinnikov (2011).</li>
<li>Ovchinnikov, Sergei (2011), Graphs and Cubes, Universitext, Springer. See especially Chapter 5, "Partial Cubes", pp. 127–181.</li>
<li><a href="/facts/Peter_Winkler/tpvKJwrA">Winkler, Peter M.</a> (1984), "Isometric embedding in products of complete graphs", Discrete Applied Mathematics, 7 (2): 221–225, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0166-218X%2884%2990069-6">10.1016/0166-218X(84)90069-6</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0727925">0727925</a>.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Ovchinnikov (2011), Definition 5.1, p. 127. - Ovchinnikov, Sergei (2011), Graphs and Cubes, Universitext, Springer <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Ovchinnikov (2011), p. 174. - Ovchinnikov, Sergei (2011), Graphs and Cubes, Universitext, Springer <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Ovchinnikov (2011), Section 5.11, "Median Graphs", pp. 163–165. - Ovchinnikov, Sergei (2011), Graphs and Cubes, Universitext, Springer <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Ovchinnikov (2011), Chapter 7, "Hyperplane Arrangements", pp. 207–235. - Ovchinnikov, Sergei (2011), Graphs and Cubes, Universitext, Springer <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Eppstein (2006). - Eppstein, David (2006), "Cubic partial cubes from simplicial arrangements", Electronic Journal of Combinatorics, 13 (1), R79, arXiv:math.CO/0510263, doi:10.37236/1105, S2CID 8608953 <a href="http://www.combinatorics.org/Volume_13/Abstracts/v13i1r79.html" target="_blank">http://www.combinatorics.org/Volume_13/Abstracts/v13i1r79.html</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Ovchinnikov (2011), Section 5.7, "Cartesian Products of Partial Cubes", pp. 144–145. - Ovchinnikov, Sergei (2011), Graphs and Cubes, Universitext, Springer <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Beaudou, Gravier & Meslem (2008). - Beaudou, Laurent; Gravier, Sylvain; Meslem, Kahina (2008), "Isometric embeddings of subdivided complete graphs in the hypercube" (PDF), SIAM Journal on Discrete Mathematics, 22 (3): 1226–1238, doi:10.1137/070681909, MR 2424849, S2CID 6332951 <a href="https://hal.archives-ouvertes.fr/hal-00187039/file/clique_partial_cubes.pdf" target="_blank">https://hal.archives-ouvertes.fr/hal-00187039/file/clique_partial_cubes.pdf</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Winkler (1984), Theorem 4. See also Ovchinnikov (2011), Definition 2.13, p.29, and Theorem 5.19, p. 136. - Winkler, Peter M. (1984), "Isometric embedding in products of complete graphs", Discrete Applied Mathematics, 7 (2): 221–225, doi:10.1016/0166-218X(84)90069-6, MR 0727925 <a href="https://doi.org/10.1016%2F0166-218X%2884%2990069-6" target="_blank">https://doi.org/10.1016%2F0166-218X%2884%2990069-6</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Eppstein (2008). - Eppstein, David (2008), "Recognizing partial cubes in quadratic time", Proc. 19th ACM-SIAM Symposium on Discrete Algorithms, pp. 1258–1266, arXiv:0705.1025, Bibcode:2007arXiv0705.1025E <a href="https://arxiv.org/abs/0705.1025" target="_blank">https://arxiv.org/abs/0705.1025</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Ovchinnikov (2011), Section 5.6, "Isometric Dimension", pp. 142–144, and Section 5.10, "Uniqueness of Isometric Embeddings", pp. 157–162. - Ovchinnikov, Sergei (2011), Graphs and Cubes, Universitext, Springer <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Hadlock & Hoffman (1978); Eppstein (2005); Ovchinnikov (2011), Chapter 6, "Lattice Embeddings", pp. 183–205. - Hadlock, F.; Hoffman, F. (1978), "Manhattan trees", Utilitas Mathematica, 13: 55–67 <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Eppstein (2009); Cabello, Eppstein & Klavžar (2011). - Eppstein, David (2009), "Isometric diamond subgraphs", Proc. 16th International Symposium on Graph Drawing, Heraklion, Crete, 2008, Lecture Notes in Computer Science, vol. 5417, Springer-Verlag, pp. 384–389, arXiv:0807.2218, doi:10.1007/978-3-642-00219-9_37, ISBN 978-3-642-00218-2, S2CID 14066610 <a href="https://arxiv.org/abs/0807.2218" target="_blank">https://arxiv.org/abs/0807.2218</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Klavžar, Gutman & Mohar (1995), Propositions 2.1 and 3.1; Imrich & Klavžar (2000), p. 60; Ovchinnikov (2011), Section 5.12, "Average Length and the Wiener Index", pp. 165–168. - Klavžar, Sandi; Gutman, Ivan; Mohar, Bojan (1995), "Labeling of benzenoid systems which reflects the vertex-distance relations" (PDF), Journal of Chemical Information and Computer Sciences, 35 (3): 590–593, doi:10.1021/ci00025a030 <a href="http://www.fmf.uni-lj.si/~klavzar/preprints/labeling-benzi.pdf" target="_blank">http://www.fmf.uni-lj.si/~klavzar/preprints/labeling-benzi.pdf</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Eppstein (2009). - Eppstein, David (2009), "Isometric diamond subgraphs", Proc. 16th International Symposium on Graph Drawing, Heraklion, Crete, 2008, Lecture Notes in Computer Science, vol. 5417, Springer-Verlag, pp. 384–389, arXiv:0807.2218, doi:10.1007/978-3-642-00219-9_37, ISBN 978-3-642-00218-2, S2CID 14066610 <a href="https://arxiv.org/abs/0807.2218" target="_blank">https://arxiv.org/abs/0807.2218</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
</ol>

Partial cube open-in-new

Partial cube