pith. sign in

arxiv: 1906.08765 · v1 · pith:FZBFSY6Wnew · submitted 2019-06-20 · 🧮 math.CO · cs.DM

Extra-factorial sum: a graph-theoretic parameter in Hamiltonian cycles of complete weighted graphs

V. Papadinas , W. Xiong , N. A. Valous This is my paper

Pith reviewed 2026-05-25 19:16 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords extra-factorial sumHamiltonian cyclescomplete weighted graphsarithmetic meangraph-theoretic parameterfactorial term countcycle length average
0
0 comments X

The pith

In complete weighted graphs, the extra-factorial sum for an edge equals (n-2) times the arithmetic mean of the total lengths of all Hamiltonian cycles through that edge.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces the extra-factorial sum as a graph-theoretic parameter computed separately for each edge in a complete weighted graph on n vertices. It proves that this sum contains exactly (n-2)! terms, each corresponding to a distinct ordering of the remaining vertices, and that scaling the sum by 1/(n-2) produces the average length sum over all Hamiltonian cycles using the chosen edge. The same construction extends to the average of squared cycle lengths taken over the full set of (n-1)!/2 cycles. A reader would care because the parameter supplies a direct computational route to these averages without listing every cycle.

Core claim

The extra-factorial sum is obtained for each edge of WH_n. If this sum is multiplied by 1/(n-2) then it gives directly the arithmetic mean of the sum of lengths l_i of all Hamiltonian cycles that traverse a selected edge e_q. The number of terms in this sum is a factorial proven to be (n-2)!. Using the extra-factorial sum, the arithmetic mean of the sum of the squared lengths of (n-1)!/2 Hamiltonian cycles of WH_n can be obtained as well.

What carries the argument

The extra-factorial sum, a sum with (n-2)! terms formed by fixing one edge and summing contributions from all permutations of the remaining vertices.

If this is right

  • The average total length of Hamiltonian cycles through any chosen edge is obtained by dividing the extra-factorial sum by (n-2).
  • The average of squared cycle lengths across all (n-1)!/2 cycles follows from the same sum construction.
  • The number of terms in the sum for each edge is exactly (n-2)!, confirming dependence on n.
  • The parameter is defined and computable separately for every edge of the complete weighted graph.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The construction may reduce the cost of evaluating edge-specific averages in large instances where full enumeration is infeasible.
  • The same summation pattern could be examined for other cycle statistics such as variance or higher moments.
  • Because the term count is proven to be (n-2)!, the expression supplies an explicit combinatorial identity linking permutations to cycle lengths.

Load-bearing premise

The graph must be complete so that every ordering of the remaining n-2 vertices produces a valid Hamiltonian cycle through the fixed edge.

What would settle it

For the complete graph on four vertices with unit weights, compute the extra-factorial sum on one edge and check whether dividing by two recovers the exact average length sum of the two cycles that use that edge.

Figures

Figures reproduced from arXiv: 1906.08765 by N. A. Valous, V. Papadinas, W. Xiong.

Figure 1
Figure 1. Figure 1: FIG. 1. Complete weighted graph [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 3
Figure 3. Figure 3: FIG. 3. Creation of three new [PITH_FULL_IMAGE:figures/full_fig_p002_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: FIG. 4. Creation of twelve new [PITH_FULL_IMAGE:figures/full_fig_p002_4.png] view at source ↗
Figure 6
Figure 6. Figure 6: FIG. 6. Creation of new [PITH_FULL_IMAGE:figures/full_fig_p003_6.png] view at source ↗
Figure 5
Figure 5. Figure 5: FIG. 5. The newly created [PITH_FULL_IMAGE:figures/full_fig_p003_5.png] view at source ↗
Figure 8
Figure 8. Figure 8: FIG. 8. Creation of new [PITH_FULL_IMAGE:figures/full_fig_p004_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: FIG. 9. Creation of new [PITH_FULL_IMAGE:figures/full_fig_p004_9.png] view at source ↗
Figure 11
Figure 11. Figure 11: FIG. 11. The summational graph [PITH_FULL_IMAGE:figures/full_fig_p005_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: FIG. 12. The graph [PITH_FULL_IMAGE:figures/full_fig_p006_12.png] view at source ↗
read the original abstract

A graph-theoretic parameter, in a form of a function, called the extra-factorial sum is discussed. The main results are presented in ref. [1] (Nastou et al., Optim Lett, 10, 1203-1220, 2016) and the reader is strongly advised to study the aforementioned paper. The current work presents subject matter in a tutorial form with proofs and some newer unpublished results towards the end (lemma six extension and lemma seven). The extra-factorial sum is relevant to Hamiltonian cycles of complete weighted graphs $WH_n$ with $n$ vertices and is obtained for each edge of $WH_n$. If this sum is multiplied by $1 / (n - 2)$ then it gives directly the arithmetic mean of the sum of lengths $l_i$ of all Hamiltonian cycles that traverse a selected edge $e_q$. The number of terms in this sum is a factorial proven to be $(n - 2)!$ which signifies that its value depends on $n$. Using the extra-factorial sum, the arithmetic mean of the sum of the squared lengths of $(n - 1)! / 2$ Hamiltonian cycles of $WH_{n}$ can be obtained as well.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The manuscript defines a graph-theoretic parameter called the extra-factorial sum for each edge e_q in the complete weighted graph WH_n. It claims that this sum (containing (n-2)! terms) multiplied by 1/(n-2) equals the arithmetic mean of the lengths l_i of all Hamiltonian cycles traversing e_q, and that the same construction yields the mean of squared lengths over all (n-1)!/2 cycles of WH_n. The work presents tutorial-style proofs of these relations together with two new lemmas.

Significance. If the central relations were correct, the extra-factorial sum would supply a compact, n-dependent expression for average Hamiltonian-cycle lengths through a fixed edge, which could be useful in combinatorial optimization on weighted complete graphs. The manuscript also supplies machine-checked-style proofs and extends prior results from the cited 2016 paper.

major comments (1)
  1. Abstract (and the section stating the main claim): the assertion that the extra-factorial sum multiplied by 1/(n-2) equals the arithmetic mean of the l_i is inconsistent with the explicit statement that the sum contains (n-2)! terms. The correct scaling for an arithmetic mean is division by (n-2)!, not by (n-2). The two factors agree only for n=3; no multiplicity argument or alternative interpretation of 'mean of the sum' is supplied to reconcile the discrepancy. This scaling error is load-bearing for the central claim about the parameter's meaning and utility.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the detailed review and for identifying the inconsistency between the stated number of terms in the extra-factorial sum and the scaling factor used to obtain the arithmetic mean. We acknowledge that the manuscript contains an error on this point and will revise the abstract, introduction, and related claims to correct the scaling.

read point-by-point responses

  1. Referee: Abstract (and the section stating the main claim): the assertion that the extra-factorial sum multiplied by 1/(n-2) equals the arithmetic mean of the l_i is inconsistent with the explicit statement that the sum contains (n-2)! terms. The correct scaling for an arithmetic mean is division by (n-2)!, not by (n-2). The two factors agree only for n=3; no multiplicity argument or alternative interpretation of 'mean of the sum' is supplied to reconcile the discrepancy. This scaling error is load-bearing for the central claim about the parameter's meaning and utility.

    Authors: The referee correctly identifies an inconsistency in the manuscript. The text states that the sum contains (n-2)! terms yet claims that division by (n-2) yields the arithmetic mean of the cycle lengths. This is erroneous; the proper divisor for the arithmetic mean is (n-2)!. We will revise the abstract, the statement of the main result, and any interpretive discussion to replace the factor 1/(n-2) with 1/(n-2)! and to remove the incorrect claim that the current scaling directly supplies the mean. The underlying definition of the extra-factorial sum and the tutorial proofs of the lemmas remain unchanged, but the interpretation of the parameter as supplying a mean will be corrected. We also note that the secondary claim concerning the mean of squared lengths over all (n-1)!/2 cycles will be reviewed for consistency with the same correction. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained from graph definitions

full rationale

The extra-factorial sum is introduced as a direct aggregation over the (n-2)! Hamiltonian cycles through a fixed edge in the complete weighted graph WH_n, with the term count established by counting permutations of the remaining vertices. The subsequent claim that multiplication by 1/(n-2) yields the arithmetic mean follows from this definition and the completeness assumption without any reduction to a fitted parameter, renamed input, or load-bearing self-citation chain. Reference [1] supplies background results but the present manuscript supplies independent proofs; no step equates the output to its inputs by construction. The noted scaling discrepancy with standard averaging is a potential arithmetic inconsistency, not a circularity pattern.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Based on abstract only; the paper introduces the extra-factorial sum as a new named parameter but relies on the standard combinatorial fact that K_n has (n-2)! Hamiltonian cycles through a fixed edge.

axioms (1)
  • standard math In the complete graph K_n the number of Hamiltonian cycles through any fixed edge is exactly (n-2)!, proven in the paper.
    Stated explicitly in the abstract as the number of terms in the sum.

pith-pipeline@v0.9.0 · 5756 in / 1335 out tokens · 40136 ms · 2026-05-25T19:16:54.882845+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

  1. [1]

    SIVA starts from T 3 1 and iterates k times to introduce, in each repetition, a new vertex in everyT 3+j i with G= [(3+ j)− 3], for 1 ≤ j ≤ k. Fig. 3 shows H3 = ABC and two new vertices X and Y(k = 2); ABC is also aT 3 1 = ABCA. A B C Χ A B C Χ A B C Χ Y Y Y Y3 1T 13 1 + T 13 2 + T 13 3 + T A B C Χ FIG. 3. Creation of three newT 4 i (G= 1). Applying SIVA ...

    work page

  2. [2]

    With the addition of vertices and starting withn = 3, the new T n+k i tends exactly to: n(n+ 1)(n+ 2)(n+ 3)/uni22EF(n+ k− 1)= (n+ k− 1)! 2 (3) A X Y CB FIG

    The term (1× n) are the T 4 i (G = 1) and the term (n+ 1) are the e4 T in each T 4 i (G= 1). With the addition of vertices and starting withn = 3, the new T n+k i tends exactly to: n(n+ 1)(n+ 2)(n+ 3)/uni22EF(n+ k− 1)= (n+ k− 1)! 2 (3) A X Y CB FIG. 5. The newly createdH5 = ABCXY. This concludes the proof./uni220E Lemma 3 . The number of T n i in Hn (n ≥ ...

    work page

  3. [3]

    ABXCA”“ABCXA

    SIVA is applied to the edges (eAC q , eBC q ) of T 3 1 except eAB q ; hence a T 4 1 (G = 1) is created. For T 4 1 = ABCXA and T 4 2 = ABXCA, SIVA adds the fifth and final vertex ofH5 without breaking eAB q . In the general case ofHn, the algorithm proceeds till all remaining vertices are added. Hence, a set ofT n i is created that always traverseeAB q . The...

    work page

  4. [4]

    edgeseAY q and eY X q with commonY are selected. Ini- tially, it is observed that there are noT 5 i that traverse eAX q and no edge capable of linkingY with vertices other than A and X, therefore eAX q , eY B q , and eY C q have to be removed. ForHn (n≥ 4) and pair of adjacent edges (e.g. eAY q and eY X q ), the edge that links the vertices of the se- lec...

    work page

  5. [5]

    Therefore the sum of li of the T 4 i (W H ′

    work page

  6. [6]

    This can be written as:24(7+8+5+4)+25(7+ 4+2+12)+27(8+5+2+12) which is:(576)+(625)+(729)

    is given by: 7 (n− 2)!eAB 1 ∑ (n−2)! i=1 lAB i (n− 2)! + +(n− 2)!eAC 2 ∑ (n−2)! i=1 lAC i (n− 2)! + +(n− 2)!eAD 3 ∑ (n−2)! i=1 lAD i (n− 2)! + +(n− 2)!eBC 4 ∑ (n−2)! i=1 lBC i (n− 2)! + +(n− 2)!eBD 5 ∑ (n−2)! i=1 lBD i (n− 2)! + +(n− 2)!eCD 6 ∑ (n−2)! i=1 lCD i (n− 2)! = = eAB 1 (n−2)! /summation.disp i=1 lAB i + eAC 2 (n−2)! /summation.disp i=1 lAC i + e...

    work page

  7. [7]

    is equal to the sum of squared lengths ofT 4 i of the initialW H4. Lemma 7. The arithmetic mean ofli of theT n i (W Hn or W H ′ n) is given by: l1+ l2+ l3+/uni22EF+l(n−1)!/slash.left2 (n− 1)!/slash.left2 = = n w(e1)+ w(e2)+/uni22EF+w(en(n−1)/slash.left2) n(n− 1)/slash.left2 (16) Proof. According to Lemma 3, the following can be deduced: l1+ l2+ l3+/uni22E...

    work page

  8. [8]

    P. E. Nastou, V. Papadinas, P. M. Pardalos, Y. C. Stama- tiou (2016). On a new edge function on complete weighted graphs and its application for locating Hamiltonian cycles of small weight.Optim Lett, 10(6):1203–1220

    work page 2016

  9. [9]

    K. H. Rosen (2007).Discrete Mathematics and its Appli- cations, McGraw Hill, New York

    work page 2007

  10. [10]

    G. J. Woeginger (2003). Exact algorithms for NP-hard problems: a survey.Lect Notes Comput Sc , 2570:185–207

    work page 2003

  11. [11]

    Orogramma, Nr

    Hellenic Society for Terminology (ELETO) (2009). Orogramma, Nr. 95, March-April. Retrieved from: www.eleto.gr/download/Orogramma/Or95_V06.pdf

    work page 2009

  12. [12]

    Papadinas, Y

    V. Papadinas, Y. C. Stamatiou (2009). Geometric ap- proaches for creating low power low interference con- nectivity patterns in static structureless sensor networks, in: Proceedings of the International Symposium on Au- tonomous Decentralized Systems (ISADS) , pp. 1–5

    work page 2009

  13. [13]

    L. A. Zager, G. C. Verghese (2008). Graph similarity scor- ing and matching.Appl Math Lett , 21:86–94

    work page 2008

  14. [14]

    Sandryhaila, J

    A. Sandryhaila, J. M. F. Moura (2014). Big data analy- sis with signal processing on graphs: representation and processing of massive data sets with irregular structure. IEEE Signal Proc Mag , 31:80–90

    work page 2014

  15. [15]

    Goulon-Sigwalt-Abram, A

    A. Goulon-Sigwalt-Abram, A. F. Duprat, G. Dreyfus (2005). From Hopfield nets to recursive networks to graph machines: numerical machine learning for structured data. Theor Comput Sci , 344:298–334

    work page 2005