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

arXiv1906.08765MaRDI QIDQ6320801FDOQ6320801

Authors: Vassilis Papadinas, N. A. Valous 

Publication date: 20 June 2019

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 $W{H}_n$ with $n$ vertices and is obtained for each edge of $W{H}_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 $W{H}_n$ can be obtained as well.

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph theory (05Cxx)

This page was built for publication: Extra-factorial sum: a graph-theoretic parameter in Hamiltonian cycles of complete weighted graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6320801)