Distance Polynomials of Extended Double Covers and Their Iterates, with Corrections to Two Formulas for the Eccentric Distance Sum

Abstract

Correction and extension of two formulas of H. Hua, S. Zhang and K. Xu, "Further results on the eccentric distance sum", Discrete Appl. Math. 160 (2012) 170–180 (doi:10.1016/j.dam.2011.10.002). Theorem 7 of that paper states ξd(G*) = 6ξd(G) + 12W(G) + 2(n−1)ζ(G) + 2n(n−1) for the extended double cover G* (Alon 1986) of a connected graph G of order n. The formula is incorrect for every connected graph with n ≥ 3 and holds only for K2: the correct identity is ξd(G*) = 4ξd(G) + 8W(G) + 2nζ(G) + 2n2, and the published expression exceeds the true value by exactly 2∑v(ε(v)+1)(D(v)−1). The smallest counterexample is G = K3, where G* = K3,3 and ξd = 84 against the printed 96. The source of the error is a distance miscount in the published proof: the transmission of a clone xi in G* is 2D(vi) + n, not 3D(vi) + (n−1). Both worked examples of the 2012 paper are also incorrect, including the example illustrating the correct companion theorem on double graphs; corrected polynomials are supplied. From a parity lemma describing all distances in G*, the manuscript further derives transformation rules for the Hosoya polynomial and for an eccentricity–distance polynomial under the extended double cover, closed formulas for the Hosoya polynomial, the Wiener index, the total eccentricity and the eccentric distance sum of every iterate G⋆k, and the analogous formulas for the extended m-cover of Hou and Xu with m ≥ 3. Contents: the manuscript (paper.pdf), a self-contained verification script (verify_eds_double_cover.py; Python/NetworkX, exact integer arithmetic, no floating point) whose 31 checks cover all 995 connected graphs with 2 ≤ n ≤ 7, iterates up to k = 3 for base graphs of order at most five, extended m-covers with m = 3, 4, 5 for base graphs of order at most six, and paths up to n = 60, its full output (verification_output.txt, all checks pass), and a README.