A theorem on Wiener-type invariants for isometric subgraphs of hypercubes (Q2371123)

The number of pairs of vertices which are at distance \(k\) in a graph \(G\) endowed with the usual graph distance is denoted by \(d(G,k)\), the numbers \(d(G,0)\) and \(d(G,1)\) represent the number of vertices and edges, respectively. Let \(\lambda\) be a real (or complex) number, and \(W_\lambda=\sum_{k\geq 1}d(G,k)k^\lambda\). A graph is called a partial cube, if it is an isometric subgraph of a hypercube. The edge set of a partial cube can be partitioned into equivalence classes of the so-called Djoković-Winkler relation \(\Theta\): edges \(e=xy\) and \(f=uv\) of a graph \(G\) are in relation \(\Theta\) if and only if \(d_G(x,u)+d_G(y,v)\neq d_G(x,v)+d_G(y,u)\). The main result of the paper reads: Let \({\mathcal F}=\{F_1,\dots,F_r\}\) be the partition of the edge set of a partial cube \(G\) induced by the relation \(\Theta\). Then for any real (or complex) number \(\lambda\), \[ W_{\lambda+1}(G)=| {\mathcal F}| W_\lambda(G)-\sum_{F\in{\mathcal F}}W_\lambda(G\backslash F). \] This result is used to find relations between some other parameters of similar nature.