# Inherent Symmetries of graphs, paths, and Traveling Salesperson Problems

Donald G. Saari

###### Abstract.

Without imposing restrictions on a weighted graph’s arc lengths, symmetry
structures cannot be expected. But, they exist. To find them, the graphs are
decomposed into a component that dictates all closed path properties (e.g.,
shortest and longest paths), and a superfluous component that can be removed.
The simpler remaining graph exposes inherent symmetry structures that form the
basis for all closed path properties. For certain asymmetric problems, the
symmetry is that of three-cycles; for the general undirected setting it is a
type of four-cycles; for general directed problems with asymmetric costs, it
is a product of three and four cycles. Everything extends immediately to
incomplete graphs.

My thanks to George Hazelrigg for our several discussions. This work is part
of a National Science Foundation project under NSF Award Number CMMI-1923164.

##  1\. Introduction

With applications ranging from the design of microchips to the positioning of
telescopes [2], understanding properties of a weighted graph’s paths and
closed paths has attained importance beyond mathematics. What complicates this
analysis is that transmission costs between nodes typically include factors
that differ from what is needed to determine path properties; e.g., they may
reflect the problem’s topography or congestions of various types. These
portions of a graph’s entries add nothing to the analysis, but they contribute
to the complexity of these concerns.

The mathematical structure of graphs developed here separates a complete
weighted graph into two unique components. The first, with best possible
reduced degrees of freedom, has all of the information needed to develop the
particulars of paths and closed paths. The remaining component is dismissed
because it adds no value; it just complicates both the analysis of paths and
the behavior of algorithms. This approach resembles (and is motivated by) a
game theory decomposition [3] where one game component has only (and all)
information needed to find all pure and mixed Nash strategic properties;
another component captures coordination, cooperation, etc.

Three classes of graphs are examined. The first is a directed, asymmetric
setting measuring differences from the average cost between vertices. The
second and third are, respectively, the standard undirected symmetric cost and
directed asymmetric cost settings. Symmetry structures for these classes
differ; e.g., the symmetry structures for the excess cost graphs (Sect. 2) are
three-cycles. Symmetries for the standard symmetric case (Sect. 3) are a form
of four-cycles. Symmetries for the general asymmetric costs (Sect. 4) are a
product of three and four cycles.

To describe the basic theme in terms of the first class, it turns out that
these graphs can be embedded in the space of asymmetric paired comparisons. A
“decision theory” decomposition divides this space into a linear subspace
characterized by a strong form of transitivity and its normal bundle
consisting of cycles [4]. Voting methods seek linear orders, so the cyclic
components create complexities and paradoxical outcomes (e.g., Arrow’s
Impossibility Theorem [1]). Projecting the data to the transitive subspace
eliminates these difficulties and simplifies the analysis [4]. But cycles, not
linear orders, are central for closed paths, so in this setting the transitive
components are what obscure the analysis. Projecting the data to the cyclic
subspace lowers the degrees of freedom, removes trouble-causing components,
and uncovers the system’s inherent three-cycle symmetry. Here, a $A,B,C$
cycle’s costs of going from $A$ to $B$, $B$ to $C$, and $C$ to $A$ are
identical.

In general, each class of graphs is decomposed into a component characterized
by a behavior that masks the closed path structures and a component that has
only (and all) of the relevant closed path information. Everything extends to
incomplete graphs. Most proofs are in Sect. 6.

##  2\. Asymmetric excess costs

Reimbursing a salesperson for the average cost of traveling between cities
creates an incentive to find routes with below average costs. For notation, it
takes 40 minutes to walk from home, H, to campus, C; returning uphill requires
50 minutes, so the average is 45. The “excess cost function” registers
differences from the average where $C\stackrel{{\scriptstyle
5}}{{\longrightarrow}}H\textrm{ represents both }C\stackrel{{\scriptstyle
5}}{{\longrightarrow}}H\textrm{ and
}H\stackrel{{\scriptstyle-5}}{{\longrightarrow}}C.$

Graphs in the space of asymmetric weighted, n-vertex graphs (with no loops)
considered here, $\mathbb{G}^{n}_{A}$, are complete (i.e., each pair of
vertices is connected with paths) and

(1) $V_{j}\stackrel{{\scriptstyle x}}{{\longrightarrow}}V_{k}\textrm{
represents both }V_{j}\stackrel{{\scriptstyle
x}}{{\longrightarrow}}V_{k}\textrm{ and
}V_{k}\stackrel{{\scriptstyle-x}}{{\longrightarrow}}V_{j}.$

To simplify the graphs, only an arc’s positive cost direction need be
represented; this is because moving counter to an arrow represents a “below
average” cost (Eq. 1). With this choice, $V_{2}$ in Fig. 1a is a “source” as
all positive value directions point away; it is a “sink” with the negative
value directions. Conversely, $V_{4}$ is a sink with positive value directions
and a source for negative value directions. Subscripts $A$ and $S$ indicate,
respectively, the asymmetric and symmetric cases.

$V_{1}$$V_{2}$$V_{3}$$V_{4}$$V_{5}$$1$$3$$8$$6$$3$414971a. Graph
$\mathcal{G}^{5}_{A}$Figure 1.
Decomposition=+$V_{1}$$V_{2}$$V_{3}$$V_{4}$$V_{5}$$1$$4$$8$$6$$3$5117103b.
Closed path independent;
$\mathcal{G}^{5}_{A,cpi}$$V_{1}$$V_{2}$$V_{3}$$V_{4}$$V_{5}$$2$$1$$0$$0$$0$13232c.
Cyclic component; $\mathcal{G}^{5}_{A,cyclic}$

Figure 1 depicts the general approach whereby graph $\mathcal{G}^{5}_{A}$ is
uniquely decomposed into a “closed path independent” component
$\mathcal{G}^{5}_{A,cpi}$ (defined in Def. 1) and a cyclic component
$\mathcal{G}^{5}_{A,cyclic}$ to have
$\mathcal{G}^{5}_{A}=\mathcal{G}^{5}_{A,cpi}+\mathcal{G}^{5}_{A,cyclic}.$ The
goal is to achieve this decomposition for any
$\mathcal{G}^{n}_{A}\in\mathbb{G}^{n}_{A}$ to obtain

(2) $\mathcal{G}^{n}_{A}=\mathcal{G}^{n}_{A,cpi}+\mathcal{G}^{n}_{A,cyclic}.$

######  Definition 1.

Graph $\mathcal{G}^{n}_{A,cpi}\in\mathbb{G}^{n}_{A}$ is “closed path
independent” (cpi) iff all closed paths have length zero. A graph is strongly
transitive iff path lengths of a triplet $\\{V_{i},V_{j},V_{k}\\}$ satisfy

(3) $V_{i}\stackrel{{\scriptstyle
x}}{{\longrightarrow}}V_{j}\stackrel{{\scriptstyle
y}}{{\longrightarrow}}V_{k}=V_{i}\stackrel{{\scriptstyle
z=x+y}}{{\longrightarrow}}V_{k}.$

Both Eq. 3 paths start at $V_{i}$ and end at $V_{k}$, so equality designates
equal path lengths. This equation modifies the concept of “strong
transitivity” developed for decision theory [4].

######  Theorem 1.

A graph is strongly transitive iff it is cpi. Strongly transitive graphs
(equivalently, cpi graphs) with $n$ vertices define a $(n-1)$-dimensional
linear subspace $\mathbb{ST}_{A}^{n}\subset\mathbb{G}^{n}_{A}$.

The Fig. 1b graph is strongly transitive and cpi. To check for strong
transitivity, select any triplet, say $\\{V_{1},V_{3},V_{5}\\},$ and determine
whether this triangle’s leg lengths, $V_{1}\stackrel{{\scriptstyle
5}}{{\longrightarrow}}V_{3},V_{3}\stackrel{{\scriptstyle
3}}{{\longrightarrow}}V_{5},$ and $V_{1}\stackrel{{\scriptstyle
8}}{{\longrightarrow}}V_{5}$, satisfy the triangle equality Eq. 3, which they
do. To equate strong transitivity with cpi, reversing
$V_{1}\stackrel{{\scriptstyle 8}}{{\longrightarrow}}V_{5}$ defines the closed
path $V_{1}\stackrel{{\scriptstyle
5}}{{\longrightarrow}}V_{3}\stackrel{{\scriptstyle
3}}{{\longrightarrow}}V_{5}\stackrel{{\scriptstyle-8}}{{\longrightarrow}}V_{1}$
with zero length.

While the proof of Thm. 1 is in Sect. 6, proving that $\mathbb{ST}_{A}^{n}$ is
a linear subspace is a common exercise. For the dimensionality assertion,
strong transitivity ensures that the $V_{i}\to V_{j}$ arc length equals the
$V_{i}\stackrel{{\scriptstyle
x}}{{\longrightarrow}}V_{1}\stackrel{{\scriptstyle
y}}{{\longrightarrow}}V_{j}$ length, where the $V_{i}\to V_{j}$ path is
diverted to pass through $V_{1}$. As all arc lengths for
$\mathcal{G}^{n}_{A,cpi}\in\mathbb{ST}^{n}_{A}$ are determined by the
$\\{V_{1}\to V_{k}\\}_{k=2}^{n}$ arc lengths, $\mathbb{ST}_{A}^{n}$ has
dimension $(n-1)$.

A standard induction argument applied to Eq. 3 proves the following result.

######  Corollary 1.

For $\mathcal{G}^{n}_{A,cpi}\in\mathbb{ST}_{A}^{n}$, any path starting at
$V_{i}$ and ending at $V_{j}$ has length equal to the $V_{i}\to V_{j}$ arc
that connects the endpoints.

A Fig. 1b example of Cor. 1 is where the $4$ length of
$V_{2}\stackrel{{\scriptstyle
7}}{{\longrightarrow}}V_{5}\stackrel{{\scriptstyle
3}}{{\longrightarrow}}V_{4}\stackrel{{\scriptstyle-10}}{{\longrightarrow}}V_{2}\stackrel{{\scriptstyle
10}}{{\longrightarrow}}V_{6}\stackrel{{\scriptstyle-6}}{{\longrightarrow}}V_{3}$,
where vertices can be revisited, equals the arc length connecting the
endpoints $V_{2}\stackrel{{\scriptstyle 4}}{{\longrightarrow}}V_{3}$.

###  2.1. Cyclic Normal Bundle.

As Thm. 3 will assert, the $\mathcal{G}^{n}_{A,cpi}\in\mathbb{ST}_{A}^{n}$
component of $\mathcal{G}^{n}_{A}$ (see Eq. 2) blurs the closed path
properties of $\mathcal{G}^{n}_{A}$. Thus, path properties must be based on
the structure of $\mathbb{ST}_{A}^{n}$’s normal bundle. The
$\mathbb{G}^{n}_{A}$ and $\mathbb{ST}^{n}_{A}$ dimensions are $n\choose 2$ and
$(n-1)$, so $\mathbb{ST}^{n}_{A}$’s normal subspace, $\mathbb{C}^{n}_{A}$, has
dimension ${{n-1}\choose 2}$. As described next, $\mathbb{C}^{n}_{A}$ consists
of cyclic actions.

######  Theorem 2.

[4] For $n\geq 3$, the linear subspace orthogonal to $\mathbb{ST}_{A}^{n}$,
$\mathbb{C}_{A}^{n}$, has dimension ${{n-1}\choose 2}$. A basis for
$\mathbb{C}^{n}_{A}$, which consists of three-cycles with equal costs between
successive vertices, is

(4) $\\{V_{1}\stackrel{{\scriptstyle
1}}{{\longrightarrow}}V_{j}\stackrel{{\scriptstyle
1}}{{\longrightarrow}}V_{k}\stackrel{{\scriptstyle
1}}{{\longrightarrow}}V_{1}\\}_{1<j<k\leq n}.$

The Eq. 4 cycles are anchored at one vertex, so the following offers a more
general choice.

######  Corollary 2.

If $\mathcal{CB}^{n}_{A}$ has ${n-1}\choose 2$ three-cycles where each arc in
a three-cycle has length 1 and each three-cycle has one arc that is not in any
other $\mathcal{CB}^{n}_{A}$ three-cycle, then $\mathcal{CB}^{n}_{A}$ is a
$\mathbb{C}^{n}_{A}$ basis.

According to Thm. 2, the $\mathcal{G}^{n}_{A,cyclic}\in\mathbb{C}^{n}_{A}$
structure is governed by three-cycles. To motivate their Eq. 4 form, strong
transitivity requires $V_{1}\stackrel{{\scriptstyle
x}}{{\longrightarrow}}V_{j}\stackrel{{\scriptstyle
y}}{{\longrightarrow}}V_{k}=V_{1}\stackrel{{\scriptstyle
z}}{{\longrightarrow}}V_{k}$, which defines the equation $x+y-z=0$. This
equation has the normal vector $(1,1,-1)$, which, when expressed in a path
form, is $V_{1}\stackrel{{\scriptstyle
1}}{{\longrightarrow}}V_{j}\stackrel{{\scriptstyle
1}}{{\longrightarrow}}V_{k}\stackrel{{\scriptstyle
1}}{{\longrightarrow}}V_{1}$, or an Eq. 4 three-cycle. It follows that the
multiple of a three-cycle measures how this triplet’s $\mathcal{G}^{n}_{A}$
data portion deviates from the triplet’s cpi “sameness.”

This discussion leads to the following central result where Eq. 5 asserts that
the Eq. 2 goal has been realized. The theorem’s concluding statement is
crucial for what follows in this section.

######  Theorem 3.

Space $\mathbb{G}^{n}_{A}$ is divided into a linear subspace
$\mathbb{ST}^{n}_{A}$ and its orthogonal complement $\mathbb{C}^{n}_{A}$. For
$\mathcal{G}_{A}^{n}\in\mathbb{G}^{n}_{A}$, there are unique
$\mathcal{G}^{n}_{A,cpi}\in\mathbb{ST}^{n}_{A}$ and
$\mathcal{G}^{n}_{A,cyclic}\in\mathbb{C}^{n}_{A}$ so that

(5) $\mathcal{G}_{A}^{n}=\mathcal{G}^{n}_{A,cpi}+\mathcal{G}^{n}_{A,cyclic};$

$\mathcal{G}^{n}_{A,cpi}$ and $\mathcal{G}^{n}_{A,cyclic}$ are, respectively,
the orthogonal projections of $\mathcal{G}^{n}_{A}$ to $\mathbb{ST}_{A}^{n}$
and to $\mathbb{C}^{n}_{A}$. The length of a closed path in
$\mathcal{G}_{A}^{n}$ equals its $\mathcal{G}^{n}_{A,cyclic}$ length.

The critical last statement is a consequence of the linear form of Eq. 5,
which requires the length of a path in $\mathcal{G}_{A}^{n}$ to equal the sum
of its lengths in $\mathcal{G}^{n}_{A,cpi}$ and in
$\mathcal{G}^{n}_{A,cyclic}.$ By design, the length of a closed path in
$\mathcal{G}^{n}_{A,cpi}$ is zero. Namely, $\mathcal{G}^{n}_{A,cpi}$ extracts
those portions of $\mathcal{G}^{n}_{A}$ entries that have nothing substantive
to contribute to closed path lengths. It now follows that the path’s lengths
in $\mathcal{G}_{A}^{n}$ and in $\mathcal{G}^{n}_{A,cyclic}$ must agree. In
turn, this means that all relevant closed path information for
$\mathcal{G}^{n}_{A}$ is encoded in the three-cycles of
$\mathcal{G}^{n}_{A,cyclic}$. Stated differently,
$\mathcal{G}^{n}_{A}\in\mathbb{G}^{n}_{A}$ has an inherent three-cycle
symmetry structure displayed by $\mathcal{G}^{n}_{A,cyclic}$ but camouflaged
by $\mathcal{G}^{n}_{A,cpi}$.

$V_{1}$$V_{2}$$V_{3}$81210a. $\mathcal{G}^{3}_{A}$=$V_{1}$$V_{2}$$V_{3}$6148b.
$\mathcal{G}^{3}_{A,cpi}$+$V_{1}$$V_{2}$$V_{3}$222c.
$\mathcal{G}^{3}_{A,cyclic}$Figure 2. Interpreting
$\mathcal{G}^{n}_{A,cyclic}$

To expand on the comment that the $\mathcal{G}^{n}_{A,cpi}$ entries contribute
nothing substantive about closed path lengths, notice that computing the
$V_{1}\stackrel{{\scriptstyle
8}}{{\longrightarrow}}V_{2}\stackrel{{\scriptstyle
10}}{{\longrightarrow}}V_{3}\stackrel{{\scriptstyle-12}}{{\longrightarrow}}V_{1}$
length of 6 in Fig. 2a involves a subtraction cancelation. To appreciate this
structure, let the optimal (but unknown) cancelled values be $u$, $v$, and $w$
from, respectively, arcs $\widehat{V_{1}V_{2}}$, $\widehat{V_{2}V_{3}}$, and
$\widehat{V_{3}V_{1}}$. That is, $(8-u)+(10-v)+(-12-w)=6$ where the cancelled
values define the equation $u+v+w=0$, which corresponds to a zero-length
closed path. For $n>3$, this cancellation applies to all triplets, so these
extracted values define a $\mathbb{ST}_{A}^{n}$ graph. The optimal choice of
removed terms comes from the $\mathbb{ST}_{A}^{n}$ graph that most closely
resembles $\mathcal{G}^{n}_{A}$, which is its orthogonal projection
$\mathcal{G}^{n}_{A,cpi}$ (Thm. 3). Indeed, with Fig. 2, the
$\mathcal{G}^{3}_{A,cpi}$ component extracts $u+v+w=6+8-14=0$. What remains
are portions of arc entries that, without further need of modification, are
relevant for computing path lengths. These terms define the
$\mathcal{G}^{3}_{A,cyclic}$ graph with its $V_{1}\stackrel{{\scriptstyle
2}}{{\longrightarrow}}V_{2}\stackrel{{\scriptstyle
2}}{{\longrightarrow}}V_{3}\stackrel{{\scriptstyle
2}}{{\longrightarrow}}V_{1}$ closed cycle that directly provides the path
length of 6. Not only do the superfluous $\mathcal{G}^{n}_{A,cpi}$ terms
complicate computations, but, as discussed below, they can sidetrack
optimization approaches such as the greedy algorithm.

The same behavior holds in general; e.g., the zero length of each triplet in
Fig. 1b identifies the optimal subtraction cancelations for computing
$\mathcal{G}^{5}_{A}$ path lengths. As the cyclic $\mathcal{G}^{n}_{A,cyclic}$
captures the germane portions for path-length considerations, when searching
for the longest or shortest $\mathcal{G}^{n}_{A}$ paths, ignore
$\mathcal{G}^{n}_{A}$ and analyze only the simpler
$\mathcal{G}^{n}_{A,cyclic}$. (Some $\mathcal{G}^{n}_{A,cyclic}$ arcs belong
to several cycles; e.g., the $V_{2}\stackrel{{\scriptstyle
2}}{{\longrightarrow}}V_{1}$ leg in Fig. 1c is the sum of this arc’s length in
two cycles.)

A slight modification of Thm. 3 describes the length of any connected path.

######  Corollary 3.

The length of a path in $\mathcal{G}^{n}_{A}$ that connects $V_{j}$ with
$V_{k}$ is the length of this path in $\mathcal{G}^{n}_{A,cyclic}$ plus the
length of the $V_{j}\to V_{k}$ arc in $\mathcal{G}^{n}_{A,cpi}$.

To illustrate, the length of 12 for path $V_{1}\stackrel{{\scriptstyle
14}}{{\longrightarrow}}V_{4}\stackrel{{\scriptstyle-6}}{{\longrightarrow}}V_{3}\stackrel{{\scriptstyle
1}}{{\longrightarrow}}V_{5}\stackrel{{\scriptstyle
3}}{{\longrightarrow}}V_{4}$ in $\mathcal{G}^{5}_{A}$ (Fig. 1a), which can
meet vertices multiple times, equals the easier computed length of 1 for
$V_{1}\stackrel{{\scriptstyle
3}}{{\longrightarrow}}V_{4}\stackrel{{\scriptstyle
0}}{{\longrightarrow}}V_{3}\stackrel{{\scriptstyle-2}}{{\longrightarrow}}V_{5}\stackrel{{\scriptstyle
0}}{{\longrightarrow}}V_{4}$ in $\mathcal{G}^{5}_{A,cyclic}$ plus 11 from the
$V_{1}\stackrel{{\scriptstyle 11}}{{\longrightarrow}}V_{4}$ arc length in
$\mathcal{G}^{5}_{A,cpi}$. The $3-2$ subtraction manifests the algebraic
arrangement of the triplets.

Proof: The length of a path in $\mathcal{G}^{n}_{A}$ equals the sum of its
lengths in $\mathcal{G}^{n}_{A,cpi}$ and $\mathcal{G}^{n}_{A,cyclic}$.
According to Cor. 1, the length of a connected path in
$\mathcal{G}^{n}_{A,cpi}$ starting at $V_{j}$ and ending at $V_{k}$ equals the
length of the arc $V_{j}\to V_{k}$ connecting the endpoints. This completes
the proof. $\square$

In general, it is easier to extract $\mathcal{G}^{n}_{A}$ path properties from
$\mathcal{G}^{n}_{A,cyclic}$ than from $\mathcal{G}^{n}_{A}$; e.g., even the
flawed greedy algorithm (GA) shows that $V_{1}\stackrel{{\scriptstyle
3}}{{\longrightarrow}}V_{4}\stackrel{{\scriptstyle
3}}{{\longrightarrow}}V_{2}\stackrel{{\scriptstyle
2}}{{\longrightarrow}}V_{5}\stackrel{{\scriptstyle
2}}{{\longrightarrow}}V_{3}\stackrel{{\scriptstyle
1}}{{\longrightarrow}}V_{1}$ of length 11 is the longest
$\mathcal{G}^{5}_{A,cyclic}$ (Fig. 1c) Hamiltonian path. According to Eq. 1,
its reversal (length -11) is the shortest. This solves the
$\mathcal{G}^{5}_{A}$ TSP problem because, as Thm. 3 asserts, these two
$\mathcal{G}^{5}_{A,cyclic}$ paths identify, respectively, the longest and
shortest $\mathcal{G}^{5}_{A}$ Hamiltonian paths and their lengths. But
GA111Because its limitations and failings are well known, the greedy algorithm
(GA) is used to illustrate advantages of the decomposition. Other GA
difficulties, caused by the algebra of cycles, are indicated with Fig. 12.
fails with $\mathcal{G}^{5}_{A}$ primarily because the
$\mathcal{G}^{5}_{A,cpi}$ values, which cancel when calculating lengths,
divert the algorithm. To see this, using the GA to search for the longest
Hamiltonian path of $\mathcal{G}^{5}_{A}$ yields the incorrect
$V_{1}\stackrel{{\scriptstyle
14}}{{\longrightarrow}}V_{4}\stackrel{{\scriptstyle-3}}{{\longrightarrow}}V_{5}\stackrel{{\scriptstyle-1}}{{\longrightarrow}}V_{3}\stackrel{{\scriptstyle-3}}{{\longrightarrow}}V_{2}\stackrel{{\scriptstyle
1}}{{\longrightarrow}}V_{1}$. Applying GA to $\mathcal{G}^{5}_{A,cpi}$
generates the same path, which underscores the fact that
$\mathcal{G}^{5}_{A,cpi}$ is the source of this problem.

For $\mathbb{G}^{n}_{A}$, the tasks of finding the longest and shortest
$\mathcal{G}^{n}_{A,cyclic}$ Hamiltonian paths coincide. This is because the
reversal of one is the other.

######  Corollary 4.

If the length of a path in $\mathcal{G}^{n}_{A,cyclic}$ is $x$, then the
length of its reversal is $-x$.

###  2.2. Decomposition

To compute $\mathcal{G}^{n}_{A,cpi}$ and $\mathcal{G}^{n}_{A,cyclic}$, recall
that $\mathcal{G}^{n}_{A,cpi}\in\mathbb{ST}^{n}_{A}$ is the orthogonal
projection of $\mathcal{G}^{n}_{A}$. Terms from this projection are described
next; for added details see [4].

The projection is a linear algebra exercise. To connect graphs with vectors,
let $\mathbf{d}_{A}^{n}\in\mathbb{R}_{A}^{n\choose 2}$ be

(6)
$\mathbf{d}_{A}^{n}=(d_{1,2},d_{1,3},\dots,d_{1,n};d_{2,3},\dots,d_{2,n};d_{3,4},\dots;d_{n-1,n}),\textrm{
where }d_{i,j}=-d_{j,i};$

the semicolons designate where the first subscript changes. To identify
$\mathbb{G}^{n}_{A}$ with $\mathbb{R}_{A}^{n\choose 2}$, let $d_{i,j}$ be the
arc length $V_{i}\stackrel{{\scriptstyle d_{i,j}}}{{\longrightarrow}}V_{j}.$
As $V_{i}\stackrel{{\scriptstyle d_{i,j}}}{{\longrightarrow}}V_{j}$ equals
$V_{j}\stackrel{{\scriptstyle-d_{i,j}}}{{\longrightarrow}}V_{i}$, it follows
that $d_{j,i}=-d_{i,j}$. Let $\mathbb{ST}_{A}^{n}\subset\mathbb{G}^{n}_{A}$
also denote the $(n-1)$-dimensional (strongly transitive) subspace of
$\mathbb{R}_{A}^{n\choose 2}$ where each triplet $\\{i,j,k\\}$ satisfies
$d_{i,j}+d_{j,k}=d_{i,k}$. With these identifications, structures of
$\mathbb{R}^{n\choose 2}_{A}$ and $\mathbb{G}^{n}_{A}$ can be described
interchangeably.

######  Definition 2.

For vertex $V_{j}$ of $\mathcal{G}_{A}^{n}\in\mathbb{G}^{n}_{A}$, let
$\mathcal{S}_{A}(V_{j})$ be $\frac{1}{n}$ times the sum of the arc lengths
leaving vertex $V_{j}$, $j=1,\dots,n.$

######  Theorem 4.

[4] For $\mathcal{G}_{A}^{n}\in\mathbb{G}^{n}_{A}$, the
$\mathcal{G}^{n}_{A,cpi}$ path length from $V_{i}$ to $V_{j}$ is
$d_{i,j}=\mathcal{S}_{A}(V_{i})-\mathcal{S}_{A}(V_{j})$,
$i,j\in\\{1,\dots,n\\}$. Each of $\mathcal{G}_{A}^{n}$ and
$\mathcal{G}_{A,cpi}^{n}$ satisfy $\sum_{j=1}^{n}\mathcal{S}_{A}(V_{j})=0$.
Graph $\mathcal{G}^{n}_{A,cyclic}$ is given by
$\mathcal{G}^{n}_{A,cyclic}=\mathcal{G}^{n}_{A}-\mathcal{G}^{n}_{A,cpi}$. All
vertices of $\mathcal{G}^{n}_{A,cyclic}$ satisfy the stronger
$\mathcal{S}_{A}(V_{j})=0.$ Conversely, if all vertices of
$\mathcal{G}^{n}_{A}\in\mathbb{G}^{n}_{A}$ satisfy $\mathcal{S}_{A}(V_{j})=0,$
then $\mathcal{G}^{n}_{A}\in\mathbb{C}^{n}_{A}$

The concluding statement follows from Thm. 4’s first sentence. This is because
$\mathcal{S}_{A}(V_{j})=0$ for all vertices requires all $d_{i,j}$ legs of
$\mathcal{G}^{n}_{A,cpi}$ to equal zero. As $\mathcal{G}^{n}_{A,cpi}=0$,
$\mathcal{G}^{n}_{A}$ equals its $\mathcal{G}^{n}_{A,cyclic}$ component.

With $\mathcal{G}^{6}_{A}$ (Fig. 3a), the $S_{A}(V_{j})$ values (called ‘Borda
Values’ in [4]) are
$\mathcal{S}_{A}(V_{1})=\frac{1}{6}(-1-5-3+4-1)=-1,\mathcal{S}_{A}(V_{2})=0,\mathcal{S}_{A}(V_{3})=2,\mathcal{S}_{A}(V_{4})=-2,\mathcal{S}_{A}(V_{5})=-3,\mathcal{S}_{A}(V_{6})=4.$
Thus (Thm. 4), the Fig. 3b values for $\mathcal{G}^{6}_{A,cpi}$ are
$d_{1,2}=\mathcal{S}_{A}(V_{1})-\mathcal{S}_{A}(V_{2})=-1,d_{1,3}=3,d_{1,4}=1,d_{1,5}=2,d_{1,6}=-5,d_{2,3}=-2,d_{2,4}=2,d_{2,5}=3,d_{2,6}=-4,d_{3,4}=4,d_{3,5}=5,d_{3,6}=-2,d_{4,5}=1,d_{4,6}=-6,d_{5,6}=-7.$
Graph $\mathcal{G}^{6}_{A,cyclic}$ follows from the equality
$\mathcal{G}^{6}_{A,cyclic}=\mathcal{G}^{6}_{A}-\mathcal{G}^{6}_{A,cpi}$; this
defines Fig. 3c.

$V_{1}$1534$V_{6}$17$V_{2}$7342$V_{3}$351$V_{4}$7$V_{5}$7a.
$\mathcal{G}_{A}^{6}$$V_{1}$1312$V_{6}$52$V_{2}$2344$V_{3}$521$V_{4}$6$V_{5}$7=b.
$\mathcal{G}_{A,cpi}^{6}$$V_{1}$0242$V_{6}$45$V_{2}$5002$V_{3}$230$V_{4}$1$V_{5}$0+c.
$\mathcal{G}_{A,cyclic}^{6}$Figure 3. Decomposition of a $\mathcal{G}_{A}^{6}$

Notice how the redundant $\mathcal{G}^{6}_{A,cpi}$ (Fig. 3b) dominates the
$\mathcal{G}_{A}^{6}$ structure even though the simpler
$\mathcal{G}^{6}_{A,cyclic}$ (Fig. 3c) is what determines all of
$\mathcal{G}_{A}^{6}$’s closed path properties. This must be expected because,
according to the orthogonal projection construction, $\mathcal{G}^{n}_{A,cpi}$
is the $\mathbb{ST}_{A}^{n}$ graph that most closely resembles
$\mathcal{G}^{n}_{A}$. As true with Fig. 2, a feature of this
$\mathcal{G}^{6}_{A,cpi}$ and $\mathcal{G}^{6}_{A}$ similarity is that
$\mathcal{G}^{6}_{A,cpi}$ collects terms involved in subtraction/cancellations
when computing $\mathcal{G}^{6}_{A}$ path lengths; the remaining
$\mathcal{G}^{6}_{A,cyclic}$ entries are the relevant portions for determining
path properties.

$V_{1}$341521$V_{6}$273$V_{2}$10172513$V_{3}$16245$V_{4}$13$V_{5}$9a.
$\mathcal{G}_{A}^{6}$$V_{1}$341520$V_{6}$281$V_{2}$12172511$V_{3}$16245$V_{4}$13$V_{5}$8b.
$\mathcal{G}_{A,cpi}^{6}$$V_{1}$0001$V_{6}$12$V_{2}$2002$V_{3}$000$V_{4}$0$V_{5}$1$=$$+$c.
$\mathcal{G}_{A,cyclic}^{6}$Figure 4. Advantages of
$\mathcal{G}_{A,cyclic}^{n}$

Figure 4 illustrates how seriously the $\mathcal{G}^{n}_{A,cpi}$ terms can
cloud a path analysis. While path properties are determined by the extremely
simple $\mathcal{G}^{6}_{A,cyclic}$ (Fig. 4c), this clarity is not obvious
from $\mathcal{G}^{6}_{A}$ (Fig. 4a). The reason is that $\mathcal{G}^{6}_{A}$
more closely resembles the associated $\mathcal{G}^{6}_{A,cpi}$. As developed
next, this is a general phenomenon.

######  Definition 3.

Two graphs $\mathcal{G}^{n}_{A,1},\mathcal{G}^{n}_{A,2}\in\mathbb{G}^{n}_{A}$
are “closed path equivalent” iff
$\mathcal{G}^{n}_{A,1,cpi}=\mathcal{G}^{n}_{A,2,cpi}$.

######  Corollary 5.

The “closed path equivalent” relationship is an equivalence relation. Two
graphs are equivalent iff their difference is a graph in
$\mathbb{ST}_{A}^{n}$. Thus, an equivalence class of this relationship is the
sum of a $\mathcal{G}^{n}_{A,cyclic}$ and the $(n-1)$-dimensional linear
subspace $\mathbb{ST}_{A}^{n}$.

According to Cor. 5, multiple (actually, most) choices of a
$\mathcal{G}^{n}_{A,cpi}$ from the vast offerings of the $(n-1)$-dimensional
$\mathbb{ST}_{A}^{n}$ dictate the form of $\mathcal{G}^{n}_{A}$ and obscure
the relevant $\mathcal{G}^{n}_{A,cyclic}$.

###  2.3. Structure of triplets

Analyzing closed path properties of a $\mathcal{G}^{n}_{A}$ involves the
algebraic structure of the $\mathcal{G}^{n}_{A,cyclic}$ three-cycles. The
following shows how to identify $\mathcal{G}^{n}_{A,cyclic}$’s three-cycles.

######  Theorem 5.

For $\mathcal{G}^{n}_{A,cyclic}$, only one three-cycle of a Cor. 2 basis has a
$\widehat{V_{j}V_{k}}$ arc. The cycle’s multiple is the
$V_{j}\stackrel{{\scriptstyle d_{j,k}}}{{\longrightarrow}}V_{k}$ weight in
$\mathcal{G}^{n}_{A,cyclic}$.

Proof: Arc $V_{j}\stackrel{{\scriptstyle d_{j,k}}}{{\longrightarrow}}V_{k}$ in
$\mathcal{G}^{n}_{A,cyclic}$ appears only in $V_{s}\stackrel{{\scriptstyle
x}}{{\longrightarrow}}V_{j}\stackrel{{\scriptstyle
x}}{{\longrightarrow}}V_{k}\stackrel{{\scriptstyle
x}}{{\longrightarrow}}V_{s}$ of the $\mathcal{CB}^{n}_{A}$ basis. As all
weights in a three-cycle agree, this is the cycle’s multiple. $\square$

To illustrate, Fig. 1c has the three three-cycles
$V_{1}\stackrel{{\scriptstyle
3}}{{\longrightarrow}}V_{4}\stackrel{{\scriptstyle
3}}{{\longrightarrow}}V_{2}\stackrel{{\scriptstyle
3}}{{\longrightarrow}}V_{1},\,V_{1}\stackrel{{\scriptstyle
1}}{{\longrightarrow}}V_{2}\stackrel{{\scriptstyle
1}}{{\longrightarrow}}V_{3}\stackrel{{\scriptstyle
1}}{{\longrightarrow}}V_{1}$ and $V_{2}\stackrel{{\scriptstyle
2}}{{\longrightarrow}}V_{5}\stackrel{{\scriptstyle
2}}{{\longrightarrow}}V_{3}\stackrel{{\scriptstyle
2}}{{\longrightarrow}}V_{2}$. Figure 3c has the four three-cycles
$V_{2}\stackrel{{\scriptstyle
5}}{{\longrightarrow}}V_{4}\stackrel{{\scriptstyle
5}}{{\longrightarrow}}V_{3}\stackrel{{\scriptstyle
5}}{{\longrightarrow}}V_{2},V_{1}\stackrel{{\scriptstyle
4}}{{\longrightarrow}}V_{6}\stackrel{{\scriptstyle
4}}{{\longrightarrow}}V_{4}\stackrel{{\scriptstyle
4}}{{\longrightarrow}}V_{1},V_{3}\stackrel{{\scriptstyle
3}}{{\longrightarrow}}V_{4}\stackrel{{\scriptstyle
3}}{{\longrightarrow}}V_{6}\stackrel{{\scriptstyle
3}}{{\longrightarrow}}V_{3},$ and $V_{1}\stackrel{{\scriptstyle
2}}{{\longrightarrow}}V_{5}\stackrel{{\scriptstyle
2}}{{\longrightarrow}}V_{3}\stackrel{{\scriptstyle
2}}{{\longrightarrow}}V_{1}.$ When finding Hamiltonian paths, to avoid
prematurely returning to a vertex, at most two arcs of a three-cycle can be
used. With this caveat, the GA can succeed with $\mathcal{G}^{n}_{A,cyclic}$
settings where it would fail for $\mathcal{G}^{n}_{A}$. For instance, the GA
delivers the longest Fig. 3c Hamiltonian path $V_{3}\stackrel{{\scriptstyle
5}}{{\longrightarrow}}V_{2}\stackrel{{\scriptstyle
5}}{{\longrightarrow}}V_{4}\stackrel{{\scriptstyle
4}}{{\longrightarrow}}V_{1}\stackrel{{\scriptstyle
4}}{{\longrightarrow}}V_{6}\stackrel{{\scriptstyle
0}}{{\longrightarrow}}V_{5}\stackrel{{\scriptstyle
2}}{{\longrightarrow}}V_{3}$ with length $20,$ which is its
$\mathcal{G}^{6}_{A}$ (Fig. 3a) path length (Thm. 3). For
$\mathcal{G}^{n}_{A}\in\mathbb{G}^{n}_{A}$, its shortest Hamiltonian route
reverses the longest.

A vertex that is a source or sink imposes an obstacle in finding optimal
paths. For instance, if $V_{j}$ is a sink for negative cost directions, as is
$V_{6}$ in Fig. 3a, all ways to leave this vertex require using a positive
cost direction. Fortunately, general properties of
$\mathcal{G}^{n}_{A,cyclic}\in\mathbb{C}^{n}_{A}$ can be obtained via the
$\mathbb{C}^{n}_{A}$ basis (Thm. 2, Cor. 2); sample conclusions are in Thm. 6.
The first assertion identifies two well behaved settings. The second comment
asserts that although sources and sinks are not unusual in
$\mathcal{G}^{n}_{A}$, which cause subtraction cancellations, they never arise
in $\mathcal{G}^{n}_{A,cyclic}$. According to the theorem’s last comment,
sources and sinks appear in $\mathcal{G}^{n}_{A}$ only because
$\mathcal{G}^{n}_{A,cpi}$ almost always has them. Thus if
$\mathcal{G}^{n}_{A}$ has a source and/or sink, expect that its structure is
dominated by $\mathcal{G}^{n}_{A,cpi}$.

######  Theorem 6.

For $\mathcal{G}^{n}_{A,cyclic}\in\mathbb{C}^{n}_{A}$, $n=4,5$, its longest
and shortest Hamiltonian paths have, respectively, all non-negative arc costs
and non-positive arc costs. For $n\geq 4,$ while $\mathcal{G}^{n}_{A}$ can
have sinks and/or sources, this is impossible for a
$\mathcal{G}^{n}_{A,cyclic}$. In contrast, if all positive cost directions of
$\mathcal{G}^{n}_{A,cpi}$ are non-zero, then both the positive and negative
cost directions have a sink and a source.

$V_{1}$551611$V_{6}$5$V_{2}$1715$V_{3}$5$V_{4}$8$V_{5}$12a.
$\mathcal{G}_{A}^{6}$$V_{1}$67139$V_{6}$21$V_{2}$7346$V_{3}$254$V_{4}$11$V_{5}$7=b.
$\tilde{\mathcal{G}}_{A,cpi}^{6}$$V_{1}$1232$V_{6}$26$V_{2}$10416$V_{3}$754$V_{4}$3$V_{5}$5+c.
$\tilde{\mathcal{G}}_{A,cyclic}^{6}$Figure 5. An incomplete
$\mathcal{G}_{A}^{6}$

###  2.4. Incomplete graphs

Incomplete graphs are similarly reduced. The approach is illustrated with
$\mathcal{G}_{A}^{6}$ (Fig. 5a) where arcs $\widehat{V_{1}V_{6}}$,
$\widehat{V_{3}V_{4}}$, $\widehat{V_{3}V_{6}}$, and $\widehat{V_{4}V_{5}}$ are
excluded. To complete $\mathcal{G}^{6}_{A}$, add in the missing arcs with
arbitrarily selected lengths. (For Fig. 5a, arcs of zero length were added.)
Denote the completed graph by $\tilde{\mathcal{G}}_{A}^{6}$, and compute
$\tilde{\mathcal{G}}^{6}_{A,cpi}$ (Fig. 5b) and
$\tilde{\mathcal{G}}^{6}_{A,cyclic}$ (Fig. 5c). Closed path lengths in
$\mathcal{G}^{6}_{A}$ agree with their lengths in
$\tilde{\mathcal{G}}^{6}_{A,cyclic}$. (The four dashed arrows in Fig. 5c
denote the forbidden arcs.) As the path $V_{2}\stackrel{{\scriptstyle
10}}{{\longrightarrow}}V_{4}\stackrel{{\scriptstyle
3}}{{\longrightarrow}}V_{6}.\stackrel{{\scriptstyle
5}}{{\longrightarrow}}V_{5}\stackrel{{\scriptstyle
7}}{{\longrightarrow}}V_{3}\stackrel{{\scriptstyle
2}}{{\longrightarrow}}V_{1}\stackrel{{\scriptstyle-1}}{{\longrightarrow}}V_{2}$
uses most of the largest allowed $\tilde{\mathcal{G}}^{6}_{A,cyclic}$ leg
lengths, it is easy to show that its length of 26 is the longest
$\tilde{\mathcal{G}}^{6}_{A,cyclic}$ Hamiltonian path. Thus, this is the
longest $\mathcal{G}^{6}_{A}$ Hamiltonian path with the same length.

######  Theorem 7.

For an incomplete $\mathcal{G}_{A}^{n}$, replace all non-admissible arcs with
arcs of arbitrary lengths to define $\tilde{\mathcal{G}}_{A}^{n}$; compute
$\tilde{\mathcal{G}}_{A,cyclic}^{n}$. The length of a closed path in
$\mathcal{G}_{A}^{n}$ equals its length in
$\tilde{\mathcal{G}}_{A,cyclic}^{n}$.

The length of an admissible path starting at $V_{j}$ and ending at $V_{k}$ in
the incomplete $\mathcal{G}^{n}_{A}$ is its length in
$\tilde{\mathcal{G}}^{n}_{A,cyclic}$ plus the length of the $V_{j}\to V_{k}$
arc in $\tilde{\mathcal{G}}^{n}_{A,cpi}$.

The concluding Thm. 7 assertion allows the $V_{j}\to V_{k}$ arc in
$\tilde{\mathcal{G}}^{n}_{A,cpi}$ to be a forbidden $\mathcal{G}^{n}_{A}$
choice. As a Fig. 5 example, the $\mathcal{G}^{6}_{A}$ path
$V_{6}\stackrel{{\scriptstyle
12}}{{\longrightarrow}}V_{5}\stackrel{{\scriptstyle
5}}{{\longrightarrow}}V_{3}$ has length 17. In
$\tilde{\mathcal{G}}^{6}_{A,cyclic}$ this path $V_{6}\stackrel{{\scriptstyle
5}}{{\longrightarrow}}V_{5}\stackrel{{\scriptstyle
7}}{{\longrightarrow}}V_{3}$ has length 12, which is added to the 5 length of
the banned $V_{6}\stackrel{{\scriptstyle 5}}{{\longrightarrow}}V_{3}$ arc in
$\tilde{\mathcal{G}}^{6}_{A,cpi}$.

Proof: A closed path’s length in $\mathcal{G}_{A}^{n}$ is the same in
$\tilde{\mathcal{G}}_{A}^{n}$ and (by Thm. 3) in
$\tilde{\mathcal{G}}_{A,cyclic}^{n}$.

A connected path’s length in $\mathcal{G}^{n}_{A}$ is the same in
$\tilde{\mathcal{G}}^{n}_{A}$, which equals the sum of its lengths in
$\tilde{\mathcal{G}}^{n}_{A,cpi}$ and $\mathcal{G}^{n}_{A,cyclic}$. Its
$\tilde{\mathcal{G}}^{n}_{A,cpi}$ length is that of its $V_{j}\to V_{k}$ arc,
which completes the proof. $\square$

###  2.5. Lower degrees of freedom

The $\mathbb{C}^{n}_{A}$ graphs have all (and only) path information, which
simplifies deriving closed path properties, computing lengths, and designing
algorithms by using the (somewhat predictive) algebra of three-cycles. General
path properties follow from the $\mathbb{C}^{n}_{A}$ basis, which
characterizes all $\mathcal{G}^{n}_{A,cyclic}$ choices. By seeking general
closed path properties, rather than just Hamiltonian circuits,
$\mathbb{C}^{n}_{A}$ is a best possible component. This is because the
simplest closed path is a triplet, so that three-cycle must be in
$\mathbb{C}^{n}_{A}$.

##  3\. Symmetric cost settings

Deriving the structure of $\mathbb{G}^{n}_{S}$—the space of n-vertex complete
symmetric weighted (no loops) graphs—mimics what was done for
$\mathbb{G}^{n}_{A}$. As with Eq. 2, the goal is to decompose a
$\mathcal{G}^{n}_{S}\in\mathbb{G}^{n}_{S}$ as

(7) $\mathcal{G}^{n}_{S}=\mathcal{G}^{n}_{S,cpi}+\mathcal{G}^{n}_{S,cyclic},$

where the definition of $\mathcal{G}^{n}_{S,cpi}$ will captures terms that, at
least initially, can be ignored when computing lengths of
$\mathcal{G}^{n}_{S}$ closed paths. Thus, all central $\mathcal{G}^{n}_{S}$
path properties are based on the $\mathcal{G}^{n}_{S,cyclic}$ structure. The
approach is to find the manifold of $\mathbb{G}^{n}_{S}$ graphs where closed
paths have a fixed length; this manifold defines the $\mathcal{G}^{n}_{S,cpi}$
components. The normal bundle of this manifold measures deviations from
“sameness” to capture what is needed to find closed path properties of a
$\mathcal{G}_{S}^{n}\in\mathbb{G}^{n}_{S}$.

$y_{1}$$x_{2}$$y_{2}$$x_{1}$$z_{2}$$z_{1}$$V_{1}$$V_{2}$$V_{4}$$V_{3}$a.
${\mathcal{G}}_{S}^{4}$$V_{1}\stackrel{{\scriptstyle
y_{1}}}{{\longrightarrow}}V_{2}\stackrel{{\scriptstyle
x_{2}}}{{\longrightarrow}}V_{3}\stackrel{{\scriptstyle
y_{2}}}{{\longrightarrow}}V_{4}\stackrel{{\scriptstyle
x_{1}}}{{\longrightarrow}}V_{1}$$V_{1}\stackrel{{\scriptstyle
z_{1}}}{{\longrightarrow}}V_{3}\stackrel{{\scriptstyle
y_{2}}}{{\longrightarrow}}V_{4}\stackrel{{\scriptstyle
z_{2}}}{{\longrightarrow}}V_{2}\stackrel{{\scriptstyle
y_{1}}}{{\longrightarrow}}V_{1}$$V_{1}\stackrel{{\scriptstyle
x_{1}}}{{\longrightarrow}}V_{4}\stackrel{{\scriptstyle
z_{1}}}{{\longrightarrow}}V_{2}\stackrel{{\scriptstyle
x_{2}}}{{\longrightarrow}}V_{3}\stackrel{{\scriptstyle
z_{2}}}{{\longrightarrow}}V_{1}$b. Equal path
lengths$\scriptstyle{\omega_{1}+\omega_{2}}$$\scriptstyle{\omega_{2}+\omega_{3}}$$\scriptstyle{\omega_{3}+\omega_{4}}$$\scriptstyle{\omega_{1}+\omega_{4}}$$\scriptstyle{\omega_{2}+\omega_{4}}$$\scriptstyle\scriptstyle{\omega_{1}+\omega_{3}}$$\omega_{1}$$\omega_{2}$$\omega_{4}$$\omega_{3}$c.
$\mathcal{G}^{4}_{S,cpi}$ representationFigure 6. Closed path independence for
$\mathbb{G}^{4}_{S}$

The $\mathbb{G}^{n}_{S}$ cpi definition and structure differs from that of
$\mathbb{G}^{n}_{A}$; e.g., rectangles replace triangles. For instance,
$\mathcal{G}_{S}^{4}\in\mathbb{G}^{4}_{S}$ (Fig. 6a) is cpi iff the three Fig.
6b routes have equal length. With cancelations, this requires the three sums
of the vertical, the horizontal, and the diagonal lengths to agree, or

(8) $x_{1}+x_{2}=y_{1}+y_{2}=z_{1}+z_{2}.$

Hamiltonian paths for $\mathcal{G}_{S}^{4}\in\mathbb{G}^{4}_{S}$ combine two
of the pairs of diagonals, vertical edges, or horizontal edges, so the two
smallest Eq. 8 sums define the shortest path with length equal to this
sum.222Should the vertices define a triangle with one in the interior, the
three pairs are defined by the triangle’s three vertices. A pair is the arc
from a vertex to the interior point and the triangle’s leg that is opposite
the vertex. For instance, if $x_{1}+x_{2}=10,\,y_{1}+y_{2}=20,$ and
$z_{1}+z_{2}=30$, then the shortest Hamiltonian circuit traverses the
perimeter and it has length 30..

All cpi graphs in $\mathbb{G}^{4}_{S}$ satisfy two independent equations (Eq.
8) in six variables. One solution has zero leg lengths, so all solutions
(i.e., all cpi graphs $\mathcal{G}^{4}_{S,cpi}$) are characterized by Eq. 8’s
four-dimensional kernel. One choice uses weights $\\{\omega_{j}\\}_{j=1}^{4}$
where $\omega_{j}$ is assigned to vertex $V_{j}$, $j=1,\dots,4$, to define the
$\widehat{V_{j}V_{k}}$ length of ${\omega_{j}+\omega_{k}}$ (Fig. 6c). It
follows from Fig. 6c that this choice satisfies Eq. 8. For
$\mathbb{G}^{4}_{S}$, these are the ‘closed path independent’ graphs. The
common path length depends on how often each vertex is visited; e.g., a
$\mathcal{G}^{4}_{S,cpi}$ closed path that visits each of the three vertices
$\\{V_{i}\\}_{i=1}^{3}$ twice has length $4\sum_{j=1}^{3}\omega_{j}$;
Hamiltonian paths in $\mathcal{G}^{4}_{S,cpi}$ have length
$T(\mathcal{G}_{S,cpi}^{4})=2\sum_{j=1}^{4}\omega_{j}$.

The above discussion centered on Fig. 6 extends to $n\geq 4.$

######  Definition 4.

A graph $\mathcal{G}^{n}_{S}\in\mathbb{G}^{n}_{S}$ is ‘closed path
independent’ iff for any set of vertices, all closed paths that pass through
each of these vertices once have the same length.

######  Theorem 8.

For $n\geq 4$, a cpi graph $\mathcal{G}^{n}_{S,cpi}\in\mathbb{G}^{n}_{S}$
assigns weight $\omega_{j}$ to vertex $V_{j}$, $j=1,\dots,n;$ the
$\widehat{V_{j}V_{k}}$ length is ${\omega_{j}+\omega_{k}}$, $j\neq k$. A
closed path passing once through the vertices $\\{V_{j}\\}_{j\in\mathcal{D}}$
has length $2\sum_{j\in\mathcal{D}}\omega_{j}$. A Hamiltonian path length in
$\mathcal{G}^{n}_{S,cpi}$ is $2\sum_{j=1}^{n}\omega_{j}$.

Determining the structure of $\mathcal{G}^{n}_{S,cpi}$ requires identifying
$\mathbb{G}^{n}_{S}$ with $\mathbb{R}^{n\choose 2}_{S}$. Here,
$\mathbb{R}^{n\choose 2}_{S}$ differs from $\mathbb{R}^{n\choose 2}_{A}$ (Eq.
6) because in $\mathbb{G}^{n}_{A}$ (Sect. 2.2), $d_{i,j}=-d_{j,i}$, but in
$\mathbb{G}^{n}_{S}$, $d_{i,j}=d_{j,i}$. Thus,

(9)
$\mathbf{d}_{S}^{n}=(d_{1,2},d_{1,3},\dots,d_{1,n};d_{2,3},\dots,d_{2,n};d_{3,4},\dots;d_{n-1,n})\in\mathbb{R}^{n\choose
2}_{S},\textrm{ where }d_{i,j}=d_{j,i};$

######  Theorem 9.

The space of $\mathcal{G}^{n}_{S,cpi}$ graphs, denoted by
$\mathbb{CPI}_{S}^{n}$, is a $n$-dimensional linear subspace of
$\mathbb{G}^{n}_{S}$, or, equivalently, of $\mathbb{R}^{n\choose 2}_{S}.$ Let
$\mathbf{B}^{n}_{j}\in\mathbb{R}_{S}^{n\choose 2}$ be where $d_{j,k}=1$ for
all $k\neq j,k=1,\dots,n$; all other $d_{u,v}=0$. A basis for
$\mathbb{CPI}_{S}^{n}$ is $\\{\mathbf{B}^{n}_{j}\\}_{j=1}^{n}$.

As $\mathcal{G}^{n}_{S,cpi}$ will identify components of $\mathcal{G}_{S}^{n}$
entries that cloud analyzing closed paths, the emphasis shifts to
$\mathcal{G}^{n}_{S,cyclic}=\mathcal{G}_{S}^{n}-\mathcal{G}^{n}_{S,cpi}$. The
dimensions of $\mathbb{G}_{S}^{n}$ and $\mathbb{CPI}_{S}^{n}$ are $n\choose 2$
and $n$, so $\mathbb{CPI}_{S}^{n}$’s normal subspace, $\mathbb{C}^{n}_{S}$,
has dimension $\frac{n(n-3)}{2}$. (The dimension of $\mathbb{C}^{n}_{A}$ is
${{n-1}\choose 2}=\frac{n(n-3)}{2}+1$.) Its four-cycle structure (Thm 10)
identifies $\mathcal{G}^{n}_{S}$’s inherent symmetry.

######  Theorem 10.

Let vector $\mathbf{b}^{n}_{i,j,k,s}$ be where
$d_{i,j}=1,d_{j,k}=-1,d_{k,s}=1,d_{s,i}=-1$; all other $d_{u,v}=0$. The space
$\mathbb{C}^{n}_{S}$ spanned by all $\\{\mathbf{b}^{n}_{i,j,k,s}\\}$, with
dimension $\frac{n(n-3)}{2}$, is orthogonal to $\mathbb{CPI}_{S}^{n}$. With

(10) $\mathcal{A}^{n}_{1,2}=\\{\mathbf{b}^{n}_{1,2,j,k}\\}_{2<j<k\leq
n},\,\mathcal{B}^{n}_{1,2}=\\{\mathbf{b}^{n}_{1,2,j,3}\\}_{j=4}^{n},\textrm{ a
basis is }\mathcal{A}^{n}_{1,2}\cup\mathcal{B}^{n}_{1,2}.$

To explain these $\mathbf{b}^{n}_{i,j,k,s}$ vectors, if the arc lengths of the
route around the perimeter of Fig. 6a satisfy the Eq. 8 cpi requirement, then
$x_{1}-y_{1}+x_{2}-y_{2}=0$. This equation has the normal vector
$(1,-1,1,-1)$, which in path form, is $\mathbf{b}^{4}_{4,1,2,3}$. In general
the $\mathbf{b}^{n}_{i,j,k,s}$ path is the four-cycle
$V_{i}\stackrel{{\scriptstyle
1}}{{\longrightarrow}}V_{j}\stackrel{{\scriptstyle-1}}{{\longrightarrow}}V_{k}\stackrel{{\scriptstyle
1}}{{\longrightarrow}}V_{s}\stackrel{{\scriptstyle-1}}{{\longrightarrow}}V_{i}$;
each vertex has one leg of length $1$ and one of length $-1$. With Fig. 6a,
the $\mathbf{b}^{4}_{1,2,3,4}$ and $\mathbf{b}^{4}_{1,4,2,3}$ multiples are,
respectively, $\frac{1}{4}\\{(y_{1}+y_{2})-(x_{1}+x_{2})\\}$ and
$\frac{1}{4}\\{(x_{1}+x_{2})-(z_{1}+z_{2})\\}$. Namely,
$\mathbf{b}^{n}_{i,j,k,s}$ measures how the $\mathcal{G}^{n}_{S}$ data
deviates from cpi sameness while identifying which data edges of a four-tuple
are ridges or valleys.

Proof. That $\mathbf{b}^{n}_{i,j,k,s}$ is orthogonal to each
$\mathbf{B}^{n}_{t}$ is immediate. If $t\neq i,j,k,s$, the scalar product is
zero. If $t$ is one of these indices, say $t=j$, then one component of
$\mathbf{b}^{n}_{i,j,k,s}$ with vertex $V_{j}$ is positive and the other is
negative, so the scalar product with $\mathbf{B}^{n}_{t}$ is zero.

Establishing the linear independence of Eq. 10 follows a switching pattern.
Iteratively, it will be shown that all coefficients of $\sum_{2<j<k\leq
n}\alpha_{j,k}\mathbf{b}^{n}_{1,2,j,k}=\mathbf{0}$ must equal zero. For each
of the ${n-3}\choose 2$ top vectors in $\mathcal{A}^{n}_{1,2}$ (i.e., $j,k\geq
4$), only vector $\mathbf{b}^{n}_{1,2,j,k}$ has a non-zero $d_{j,k}$, so
$\alpha_{j,k}=0.$ For all remaining vectors, either $j$ or $k$ equals 3. Of
these, only the top $\mathcal{B}^{n}_{1,2}$ vector of
$\mathbf{b}^{n}_{1,2,n,3}$ has a non-zero $d_{2,n}$, so $\alpha_{n,3}=0$. The
top remaining $\mathcal{A}^{n}_{1,2}$ vector is $\mathbf{b}^{n}_{1,2,3,n}$,
where, with the removal of $\mathbf{b}^{n}_{1,2,n,3}$, only
$\mathbf{b}^{n}_{1,2,3,n}$ has non-zero $d_{3,n}$, so $\alpha_{3,n}=0$. The
obvious induction argument of switching between remaining
$\mathcal{A}^{n}_{1,2}$ and $\mathcal{B}^{n}_{1,2}$ vectors continues. That
is, if $s$ is the upper bound of the remaining $j,k$ values, then only
$\mathbf{b}^{n}_{1,2,s,3}\in\mathcal{B}^{n}_{1,2}$ has a non-zero $d_{2,s}$
term, so $\alpha_{s,3}=0$. The top remaining $\mathcal{A}^{n}_{1,2}$ vector is
$\mathbf{b}^{n}_{1,2,3,s}$; as $\mathbf{b}^{n}_{1,2,s,3}$ was removed, only
$\mathbf{b}^{n}_{1,2,3,s}$ of the remaining vectors has a non-zero $d_{3,s}$
term, so $\alpha_{3,s}=0$ and $s-1$ is the largest remaining $j,k$ value. This
completes the proof. $\square$

###  3.1. Decomposing $\mathbb{G}^{n}_{S}$

Theorem 11 summarizes the above; it is the $\mathbb{G}^{n}_{S}$ version of
Thm. 2. As with Sect. 2, the decomposition involves $O(n^{2})$ computations.

######  Theorem 11.

For $n\geq 4$, $\mathbb{G}^{n}_{S}$ has an $n$-dimensional linear subspace
$\mathbb{CPI}_{S}^{n}$ and an orthogonal $\frac{n(n-3)}{2}$ dimensional linear
subspace $\mathbb{C}^{n}_{S}$. A $\mathcal{G}_{S}^{n}\in\mathbb{G}^{n}_{S}$
has a unique decomposition
$\mathcal{G}_{S}^{n}=\mathcal{G}^{n}_{S,cpi}+\mathcal{G}^{n}_{S,cyclic}$ where
$\mathcal{G}^{n}_{S,cpi}\in\mathbb{CPI}^{n}_{S}$ and
$\mathcal{G}^{n}_{S,cyclic}\in\mathbb{C}^{n}_{S}$ are, respectively, the
orthogonal projection of $\mathcal{G}^{n}_{S}$ to $\mathbb{CPI}^{n}_{S}$ and
to $\mathbb{C}^{n}_{S}$.

$V_{1}$$V_{2}$$V_{3}$$V_{4}$17131717$14$$12$a.
$\mathcal{G}^{4}_{S}$=$V_{1}$$V_{2}$$V_{3}$$V_{4}$15131715$16$$14$b.
$\mathcal{G}^{4}_{S,cpi}$+2$V_{1}$$V_{2}$$V_{3}$$V_{4}$002$-2$$-2$c.
$\mathcal{G}^{4}_{S,cyclic};2\mathbf{b}_{1,2,4,3}$+Figure 7. Interpreting
$\mathcal{G}^{n}_{S,cyclic}$

Before computing $\mathcal{G}^{n}_{S,cpi}$ and $\mathcal{G}^{n}_{S,cyclic}$,
Fig. 7 is used to explain their roles and to relate $\mathcal{G}^{n}_{S,cpi}$
with $\mathcal{G}^{n}_{A,cpi}.$ According to Thm. 11,
$\mathcal{G}^{n}_{S,cpi}$ is the $\mathbb{CPI}_{S}^{n}$ graph that most
closely resembles $\mathcal{G}^{n}_{S}$; this similarity is apparent when
comparing Figs. 7a, b. A defining feature of
$\mathcal{G}^{n}_{A,cpi}\in\mathbb{ST}_{A}^{n}$ is that for any set of
vertices, the length of all closed paths meeting each vertex once is zero.
Similarly, according to Def. 4, for
$\mathcal{G}^{n}_{S,cpi}\in\mathbb{CPI}_{S}^{n}$ and for any selected set of
vertices, the length of all closed paths that meet each vertex once is the
same, but not necessarily zero. The role of the decomposition in
$\mathbb{G}^{n}_{A}$ and in $\mathbb{G}^{n}_{S}$ is to remove these common
path length values. Thus the $\mathcal{G}^{n}_{A,cyclic}$ and
$\mathcal{G}^{n}_{S,cyclic}$ graphs characterize how the data from the
original graph ($\mathcal{G}^{n}_{A}$ or $\mathcal{G}^{n}_{S}$) differs from
the cpi sameness to provide valued path length information.

In Fig. 7b, the sums of its vertical edges, horizontal edges, and diagonals
all equal 30. Thus, all Fig. 7b Hamiltonian paths have the length 60. Three of
the six Fig. 7a Hamiltonian circuits are $V_{1}\stackrel{{\scriptstyle
17}}{{\longrightarrow}}V_{2}\stackrel{{\scriptstyle
17}}{{\longrightarrow}}V_{3}\stackrel{{\scriptstyle
17}}{{\longrightarrow}}V_{4}\stackrel{{\scriptstyle
13}}{{\longrightarrow}}V_{1}$ with length 64, $V_{1}\stackrel{{\scriptstyle
17}}{{\longrightarrow}}V_{2}\stackrel{{\scriptstyle
12}}{{\longrightarrow}}V_{4}\stackrel{{\scriptstyle
17}}{{\longrightarrow}}V_{3}\stackrel{{\scriptstyle
14}}{{\longrightarrow}}V_{1}$ with length 60, and
$V_{1}\stackrel{{\scriptstyle
14}}{{\longrightarrow}}V_{3}\stackrel{{\scriptstyle
17}}{{\longrightarrow}}V_{2}\stackrel{{\scriptstyle
12}}{{\longrightarrow}}V_{4}\stackrel{{\scriptstyle
13}}{{\longrightarrow}}V_{1}$ with length 56; the other three are reversals.
The average length of these paths is 60, which agrees with its Fig. 7b value.
This comparison accurately suggests that for any set of vertices used to
define closed paths, what happens in $\mathcal{G}^{n}_{S,cpi}$ is the average
of what happens in $\mathcal{G}^{n}_{S}.$ For instance, the length of a
Hamiltonian path for Fig. 7a is the sum of its lengths in Fig.7b and Fig. 7c.
A “subtraction” argument, similar to that used with Fig. 2, is that the
portion of a path entry contributing to the Fig. 7b average Hamiltonian length
is subtracted from the actual leg value. What remains determines how the path
length differs from the average, so it is used in the computation; the average
length of a Hamiltonian path is replaced at the end. Thus, as developed below,
path lengths in $\mathcal{G}^{n}_{S,cyclic}$ (e.g., Fig. 7c) measure
differences from the average. As
$V_{1}\stackrel{{\scriptstyle-2}}{{\longrightarrow}}V_{3}\stackrel{{\scriptstyle
0}}{{\longrightarrow}}V_{2}\stackrel{{\scriptstyle-2}}{{\longrightarrow}}V_{4}\stackrel{{\scriptstyle
0}}{{\longrightarrow}}V_{1}$ in Fig. 7c has the shortest length of $-4$, this
defines the shortest Fig. 7a path that has length $-4$ from the average of 60,
or 56.

###  3.2. Computing $\mathcal{G}^{n}_{S,cpi}$ and $\mathcal{G}^{n}_{S,cyclic}$

Computing the $\mathcal{G}^{n}_{S,cpi}$ and $\mathcal{G}^{n}_{S,cyclic}$ for a
$\mathcal{G}^{n}_{S}$ follows the lead of Sect. 2.2. This is because
$\mathcal{G}^{n}_{S,cpi}$ is the orthogonal projection of
$\mathcal{G}^{n}_{S}$ to $\mathbb{CPI}^{n}_{S}$, and a basis for
$\mathbb{CPI}^{n}_{S}$ is known (Thm. 9). Entries for
$\mathcal{G}^{n}_{S,cpi}$ and $\mathcal{G}^{n}_{S,cyclic}$ are based on the
following.

######  Definition 5.

For $V_{j}$ of $\mathcal{G}_{S}^{n}\in\mathbb{G}^{n}_{S}$, let
$\mathcal{S}_{S}(V_{j})$ be the sum of the arc lengths attached to vertex
$V_{j}$, $j=1,\dots,n.$ Let
$T(\mathcal{G}_{S}^{n})=\frac{1}{n-1}\sum_{j=1}^{n}\mathcal{S}_{S}(V_{j})$.

Because $\frac{1}{n-1}S(V_{j})$ is the average length of an arc with $V_{j}$
as a vertex, it follows that $T(\mathcal{G}_{S}^{n})$ is the average
$\mathcal{G}^{n}_{S}$ Hamiltonian path length. As $\mathcal{G}^{n}_{S,cyclic}$
consists of $\mathbf{b}^{n}_{i,j,k,s}$ cycles, each $\mathbf{b}^{n}_{i,j,k,s}$
arc entering a vertex has a leaving arc with the same weight but opposite
sign, so $S_{S}(V_{j})=0$. This equation requires the $S_{S}(V_{j})$ values
for $\mathcal{G}^{n}_{S}$ and $\mathcal{G}^{n}_{S,cpi}$ to agree. Because
$T(\mathcal{G}^{n}_{S})$ sums these values, the average Hamiltonian path
lengths in $\mathcal{G}^{n}_{S}$ and in $\mathcal{G}^{n}_{S,cpi}$ agree (as
suggested with Fig. 7), or

(11)
$T(\mathcal{G}^{n}_{S})=T(\mathcal{G}^{n}_{S,cpi})=2\sum_{j=1}^{n}\omega_{j}.$

Agreement between $S_{S}(V_{j})$ values in $\mathcal{G}_{S}$ and
$\mathcal{G}^{n}_{S,cpi}$ provides equations for the unknowns
$\\{\omega_{j}\\}_{j=1}^{n}$. Illustrating with Fig. 8a, as $S_{S}(V_{1})=81$
for $\mathcal{G}^{5}_{S}$, the same value holds for $\mathcal{G}^{5}_{S,cpi}$,
which means that $\sum_{j=2}^{5}(\omega_{1}+\omega_{j})=81$. In general, the
unknown $\\{\omega_{j}\\}_{j=1}^{n}$ satisfy

(12) $S_{S}(V_{j})=\sum_{k\neq
j}(\omega_{j}+\omega_{k})=(n-1)\omega_{j}+\sum_{k\neq
j}\omega_{k}=(n-2)\omega_{j}+\sum_{k=1}^{n}\omega_{k}=(n-2)\omega_{j}+\frac{1}{2}T(\mathcal{G}^{n}_{S,cpi}),.$

Using $T(\mathcal{G}^{n}_{S})=\mathcal{T}(\mathcal{G}^{n}_{S,cpi})$ (Eq. 11),
the values of the $\mathcal{G}^{n}_{S,cpi}$ weights are

(13)
$\omega_{j}=\frac{1}{n-2}[S_{S}(V_{j})-\frac{1}{2}T(\mathcal{G}_{S}^{n})],\,j=1,2,\dots,n.$

These $\omega_{j}$ weights, which define $\mathcal{G}^{n}_{S,cpi}$ and
$\mathcal{G}^{n}_{S,cyclic}$, lead to a result concerning path lengths.

######  Theorem 12.

For $\mathcal{G}^{n}_{S}\in\mathbb{G}^{n}_{S}$, Eq. 13 defines the weights of
its $\mathcal{G}^{n}_{S,cpi}$ component. Let
$\mathcal{G}^{n}_{S,cyclic}=\mathcal{G}^{n}_{S}-\mathcal{G}^{n}_{S,cpi}.$ The
$\mathcal{G}_{S}^{n}$ length of a Hamiltonian circuit equals
$T(\mathcal{G}_{S}^{n})$ plus its $\mathcal{G}^{n}_{S,cyclic}$ path length.

Proof: A $\mathcal{G}^{n}_{S}$ path length is the sum of its
$\mathcal{G}^{n}_{S,cpi}$ and $\mathcal{G}^{n}_{S,cpi}$ lengths. All
$\mathcal{G}^{n}_{S,cpi}$ Hamiltonian paths have length
$T(\mathcal{G}^{n}_{S,cpi})=T(\mathcal{G}_{S}^{n})$, so Thm. 12 follows.
$\square$

According to Thm. 12, all essential closed path properties of
$\mathcal{G}^{n}_{S}$ are based on the structure of
$\mathcal{G}^{n}_{S,cyclic}$ and its four-cycle symmetries. Thus, general
properties characterizing $\mathcal{G}^{n}_{S,cyclic}$ are useful.

######  Corollary 6.

If $\mathcal{G}^{n}_{S}$ has the property that $S_{S}(V_{j})=0$,
$j=1,\dots,n$, then $\mathcal{G}^{n}_{S}\in\mathbb{C}^{n}_{S}$.

Proof: This condition requires $T(\mathcal{G}^{n}_{S})=0$ (Def. 5) and
$\omega_{j}=0$, $j=1,\dots,n$ (Eq. 13). As $\mathcal{G}^{n}_{S,cpi}=0$, it
follows that $\mathcal{G}^{n}_{S}=\mathcal{G}^{n}_{S,cyclic}$. $\square$

$V_{1}$$V_{2}$$V_{3}$$V_{4}$$V_{5}$$3$$9$$24$$18$$9$124227213a. Original;
$\mathcal{G}_{S}^{5}$Figure 8. Decomposition of a
$\mathcal{G}_{S}^{5}\in\mathbb{G}^{5}_{S}$=+$V_{1}$$V_{2}$$V_{3}$$V_{4}$$V_{5}$$19$$6$$20$$16$$23$$13$$29$$13$$22$$7$b.
$\mathcal{G}^{5}_{S,cpi}$$V_{1}$$V_{2}$$V_{3}$$V_{4}$$V_{5}$$-{16}$$3$$4$$2$-14-11314-1-4c.
$\mathcal{G}^{5}_{S,cyclic}$

To illustrate Thm. 12, the Fig. 8a computations from $\mathcal{G}_{S}^{5}$ are
$S_{S}(V_{1})=81,S_{S}(V_{2})=60,S_{S}(V_{3})=42,S_{S}(V_{4})=90,S_{S}(V_{5})=63$,
so $T(\mathcal{G}_{S}^{5})=84.$ This means that (Eq. 13)
$\omega_{1}=\frac{1}{3}[81-42]=13,\,\omega_{2}=6,\,\omega_{3}=0,\,\omega_{4}=16,\,\omega_{5}=7,$
from which $\mathcal{G}^{5}_{S,cpi}$ and $\mathcal{G}^{5}_{S,cyclic}$ of Figs.
8b, c follow.

$V_{1}$14111517$V_{6}$129$V_{2}$9151013$V_{3}$191326$V_{4}$18$V_{5}$14a.
$\mathcal{G}_{S}^{6}$$V_{1}$9111520$V_{6}$148$V_{2}$121711
14$V_{3}$191323$V_{4}$17$V_{5}$22=b.
${\mathcal{G}_{S,cpi}^{6}}$$V_{1}$500-3$V_{6}$-21$V_{2}$-3-2-1-1$V_{3}$003$V_{4}$1$V_{5}$2+c.
${\mathcal{G}_{S,cyclic}^{6}}$Figure 9. A $\mathcal{G}_{S}^{6}$

The Fig. 9 six-alternative example is similarly obtained. The
$\mathcal{G}^{6}_{S,cpi}$ weights are
$\omega_{1}=6,\omega_{2}=3,\omega_{3}=5,\omega_{4}=9,\omega_{5}=14,\omega_{6}=8.$
As required by Def. 4, for any rectangle in $\mathcal{G}^{6}_{S,cpi}$ (Fig.
9b), the sums of its horizontal edges, its vertical edges, and its diagonals
are the same. For any five vertices, the lengths of any
$\mathcal{G}^{6}_{S,cpi}$ closed curves meeting all five vertices once are the
same. All $\mathcal{G}^{6}_{S,cpi}$ Hamiltonian paths have the same length.
Similar to Cor. 5, $\mathcal{G}^{n}_{S,cpi}$ can dominate the
$\mathcal{G}^{n}_{S}$ format.

Turning to $\mathcal{G}^{n}_{S,cyclic}$, negative arc values normally are
avoided with symmetric costs because cycling can generate an arbitrarily small
path length. This problem is sidestepped here because such cycling increases
the value that replaces $T(\mathcal{G}^{n}_{S,cpi})$ in Thm. 12; e.g., if each
vertex is met twice, then the value is
$2T(\mathcal{G}^{n}_{S,cpi})=2(2\sum_{j=1}^{n}\omega_{j})$. As
$\mathcal{G}^{n}_{S,cyclic}$ entries indicate “differences from average,”
following arcs with negative lengths is following “below average cost” arcs; a
concept that does not exist for $\mathcal{G}^{n}_{S}$.

An importance of the reduction is that the $\mathcal{G}^{n}_{S,cyclic}$ arc
lengths have a distinct meaning for path lengths, so even the GA can be
successful where it would fail with $\mathcal{G}^{n}_{S}$. With Fig. 8c, the
GA identifies shortest $\mathcal{G}^{n}_{S,cyclic}$ Hamiltonian circuit of
$V_{1}\stackrel{{\scriptstyle-16}}{{\longrightarrow}}V_{2}\stackrel{{\scriptstyle-1}}{{\longrightarrow}}V_{4}\stackrel{{\scriptstyle-14}}{{\longrightarrow}}V_{5}\stackrel{{\scriptstyle-4}}{{\longrightarrow}}V_{3}\stackrel{{\scriptstyle-1}}{{\longrightarrow}}V_{1}$,
which uses all five negative cost arcs, has length $-36$. Its
$\mathcal{G}_{S}^{5}$ length (Thm. 12) is
$T(\mathcal{G}_{S}^{5})-36=84-36=48.$ But GA is thrown off the track with
$\mathcal{G}^{5}_{S}$ (Fig. 8a) because of the $\mathcal{G}^{5}_{S,cpi}$
terms.

Similarly, the GA identifies the shortest Fig. 9c Hamiltonian path
$V_{1}\stackrel{{\scriptstyle-3}}{{\longrightarrow}}V_{5}\stackrel{{\scriptstyle-2}}{{\longrightarrow}}V_{2}\stackrel{{\scriptstyle-3}}{{\longrightarrow}}V_{4}\stackrel{{\scriptstyle-1}}{{\longrightarrow}}V_{3}\stackrel{{\scriptstyle
0}}{{\longrightarrow}}V_{6}\stackrel{{\scriptstyle-2}}{{\longrightarrow}}V_{1}$
of $-11$. Using the $\omega_{j}$ values for Fig. 9b,
$T(\mathcal{G}^{6}_{S,cpi})=90,$ so the shortest Hamiltonian path in Fig. 9a
is $11$ below this average, or $90-11=79.$ Again, the GA fails for
$\mathcal{G}^{6}_{S}$ because the $\mathcal{G}^{6}_{S,cpi}$ entries divert it.

The construction leads to an easily computed lower bound for Hamiltonian path
lengths.

######  Corollary 7.

For $\mathcal{G}^{n}_{S}$, let the adjustment
$\mathcal{A}(\mathcal{G}^{n}_{S,cyclic})$ be the sum of the $n$ smallest arc
lengths in $\mathcal{G}^{n}_{S,cyclic}$. All $\mathcal{G}^{n}_{S}$ Hamiltonian
path lengths are bounded below by
$T(\mathcal{G}^{n}_{S})+\mathcal{A}(\mathcal{G}^{n}_{S,cyclic})$. The shortest
Hamiltonian graph is bounded above by $T(\mathcal{G}^{n}_{S})$,

The last statement follows because $T(\mathcal{G}^{n}_{S})$ is the average
length of a Hamiltonian path. Thus some Hamiltonian path length is smaller
than $T(\mathcal{G}^{n}_{S})$ and $\mathcal{A}(\mathcal{G}^{n}_{S,cyclic})<0$
iff $\mathcal{G}^{n}_{S,cyclic}\neq 0$. For Fig. 8,
$\mathcal{A}(\mathcal{G}^{5}_{S,cyclic})=-36$, so the lower bound is
$84-36=48$, which equals the length of the shortest Hamiltonian path. With
Fig. 9, $\mathcal{A}(\mathcal{G}^{5}_{S,cyclic})=-12$ for the lower bound of
$90-12=78$, but the shortest Hamiltonian path has the larger length of $79.$
The reason is that the $-1$ length of $\widehat{V_{2}V_{6}}$ can not be used.
By using the four-cycle geometry, sharper estimates can be derived.

Closely related to Cor. 7 is an approach to find the shortest Hamiltonian tour
by ranking $\mathcal{G}^{n}_{S,cyclic}$ arcs according to their lengths where
“smaller is better.” If marking first $n$ shortest arcs does not define a
Hamiltonian tour, iteratively add arcs from this list until the marked legs do
define such a closed path. (All of the shortest Hamiltonian circuits in this
section were verified in this simple manner. This approach can be improved by
using properties of the four-cycles.)

Figure 10. Finding
paths$V_{1}$$V_{2}$$V_{3}$$V_{4}$$V_{5}$$-{16}$$3$$4$$2$-14-11314-1-4a. From
Fig. 8c$V_{1}$500-3$V_{6}$-21$V_{2}$-3-2-1-1$V_{3}$003$V_{4}$1$V_{5}$2b. From
Fig. 9c.

To illustrate with Fig. 10a (from Fig.8c), just marking the five legs with
negative costs already defines the shortest Hamiltonian graph. In Fig. 10b,
the six legs with the smallest (all negative) values do not define a
Hamiltonian circuit, so add an additional leg with the next smallest cost
(here zero). The $V_{3}\stackrel{{\scriptstyle 0}}{{\longrightarrow}}V_{6}$
arc completes the
$V_{1}\stackrel{{\scriptstyle-3}}{{\longrightarrow}}V_{5}\stackrel{{\scriptstyle-2}}{{\longrightarrow}}V_{2}\stackrel{{\scriptstyle-3}}{{\longrightarrow}}V_{4}\stackrel{{\scriptstyle-1}}{{\longrightarrow}}V_{3}\stackrel{{\scriptstyle
0}}{{\longrightarrow}}V_{6}\stackrel{{\scriptstyle-2}}{{\longrightarrow}}V_{1}$
circuit, which, by construction, is the shortest.

This approach applies to other types of closed paths. Suppose the goal in Fig.
9 is to find find the shortest closed path that passes once through each of
the four vertices $\\{V_{1},V_{2},V_{4},V_{5}\\}$. The six
$\mathcal{G}^{6}_{S,cyclic}$ arc lengths of these vertices are
$\\{-3,-3,-2,0,3,5\\}$ where marking the first four on
$\mathcal{G}^{6}_{S,cyclic}$ already defines the minimal closed path
$V_{2}\stackrel{{\scriptstyle-3}}{{\longrightarrow}}V_{4}\stackrel{{\scriptstyle
0}}{{\longrightarrow}}V_{1}\stackrel{{\scriptstyle-3}}{{\longrightarrow}}V_{5}\stackrel{{\scriptstyle-2}}{{\longrightarrow}}V_{2}$
of length $-8$. This set’s $T$ value is
$2(\omega_{1}+\omega_{2}+\omega_{4}+\omega_{5}),$ which, in
$\mathcal{G}^{6}_{S,cpi}$, is the sum of the rectangle’s vertical and
horizontal legs or 64. So the length of this shortest $\mathcal{G}^{6}_{S}$
closed path over these vertices is $64-8=56.$

###  3.3. Four cycle structure

A complication in determining which four-cycles define a given
$\mathcal{G}^{n}_{S,cyclic}$ is that some of these four-cycles must overlap on
certain edges. To handle this complexity, the switching, iterative approach
used in the proof of Thm. 10 is used.

######  Theorem 13.

To express a $\mathcal{G}^{n}_{S,cycle}\in\mathbb{C}^{n}_{S}$ in terms of the
basis in Eq. 10, for $4\leq j<k$, the multiple of
$\mathbf{b}^{n}_{1,2,j,k}\in\mathcal{A}^{n}_{1,2}$ is $d_{j,k}$ from the
$V_{j}\stackrel{{\scriptstyle d_{j,k}}}{{\longrightarrow}}V_{k}$ arc in
$\mathcal{G}^{n}_{S,cycle}$. (If the arc is not in the graph, its value is
zero.) After determining the multiple of a basis vector, remove the associated
four-cycle from the graph. In what remains, the multiple of the top
$\mathbf{b}^{n}_{1,2,n,3}\in\mathcal{B}^{n}_{1,2}$ is the negative of the
$d_{2,n}$ value in the of $V_{2}\stackrel{{\scriptstyle
d_{2,n}}}{{\longrightarrow}}V_{n}$ arc in the reduced graph.333The associated
arc for $\mathbf{b}^{n}_{1,2,n,3}$ is $V_{1}\stackrel{{\scriptstyle
1}}{{\longrightarrow}}V_{2}\stackrel{{\scriptstyle-1}}{{\longrightarrow}}V_{n}\stackrel{{\scriptstyle
1}}{{\longrightarrow}}V_{3}\stackrel{{\scriptstyle-1}}{{\longrightarrow}}V_{1}$,
so for $V_{2}\stackrel{{\scriptstyle d_{2,n}}}{{\longrightarrow}}V_{n}$ to
hold, the coefficient for $\mathbf{b}^{n}_{1,2,n,3}$ must be the negative of
$d_{2,n}$. After removing this four-cycle, the top remaining
$\mathcal{A}^{n}_{1,2}$ vector is $\mathbf{b}^{n}_{1,2,3,n}$; its coefficient
is the length in $V_{3}\stackrel{{\scriptstyle
d_{3,n}}}{{\longrightarrow}}V_{n}$ in the reduced graph, which leaves $n-1$ as
the largest remaining index in the reduced graph. In general, if the largest
remaining index is s, the multiple of the top remaining
$\mathcal{B}^{n}_{1,2}$ vector, $\mathbf{b}^{n}_{1,2,s,3}$, is the negative of
$d_{2,s}$ from the reduced graph’s $V_{2}\stackrel{{\scriptstyle
d_{2,s}}}{{\longrightarrow}}V_{s}$ arc. The top of the remaining
$\mathcal{A}^{n}_{1,2}$ vectors is $\mathbf{b}^{n}_{1,2,3,s}$; its multiple is
the $d_{3,s}$ value of the $V_{3}\stackrel{{\scriptstyle
d_{3,s}}}{{\longrightarrow}}V_{s}$ arc in the reduced graph.

Proof, The proof is essentially that of Thm. 10; removing basis vectors in the
specified manner leaves, at each stage, a single $d_{u,v}$ value of a certain
type. Because $\mathbb{C}^{n}_{S}$ is the sum of these four-cycles, the
existence of this $d_{u,v}\neq 0$ requires the associated
$\mathbf{b}^{n}_{1,2,k,s}$ to be in the decomposition; the form of this four-
cycle requires $d_{u,v}$ to be the vector’s multiple. A difference is that if
$d_{u,v}$ identifies a vector from $\mathcal{B}^{n}_{1,2}$, the multiple is
the negative of $d_{u,v}$, as required by the form of the associated four-
cycle. If the vector is from $\mathcal{A}^{n}_{1,2}$, then $d_{u,v}$ is the
multiple. $\square$

Using this approach, the four cycles of $\mathcal{G}^{5}_{S,cyclic}$ in Fig.
8c are $-14\mathbf{b}^{5}_{1,2,{\mathbf{4},5}}$,
$-\mathbf{b}^{5}_{1,\mathbf{2,5,}3}$, $10\mathbf{b}^{5}_{1,2,\mathbf{3,5}}$,
$-13\mathbf{b}^{5}_{1,\mathbf{2,3,}4}$ and $15\mathbf{b}^{5}_{1,2,4,3}$.

###  3.4. Extensions

With minor modifications, all other results developed in Sect. 2 for the
asymmetric $\mathbb{G}^{n}_{A}$ transfer to the symmetric
$\mathbb{G}^{n}_{S}$. For instance, to analyze connected and closed path
properties that involve a subset of vertices, carry out the above with that
subset. Other samples follow.

######  Theorem 14.

Consider the class of paths starting at $V_{j}$ and ending at $V_{k}$ that
pass through vertices $\\{V_{i}\\}_{i\in\mathcal{D}}$ where, for each
$i\in\mathcal{D}$, the path passes through $V_{i}$ $\kappa_{i}$ times. The
length of such a path in $\mathcal{G}^{n}_{S}$ is its path length in
$\mathcal{G}^{n}_{S,cyclic}$ plus
$(\omega_{j}+\omega_{k})+2\sum_{i\in\mathcal{D}}\kappa_{i}\omega_{i}$.

As an example, consider all paths in Fig. 9 that start at $V_{1}$, end in
$V_{5}$ and pass through each of $V_{2},V_{3},V_{4}$ twice. According to the
weights of $\mathcal{G}^{6}_{S,cpi}$, the length of any of these paths in
$\mathcal{G}^{6}_{S}$ is its length in $\mathcal{G}^{6}_{S,cyclic}$ plus its
$\mathcal{G}^{6}_{S,cpi}$ length of $(6+4)+4(3+5+4).$

Graphs with incomplete symmetric costs are handled the same way as in Sect. 2.
That is, complete the graph by adding arcs of any desired length to obtain
$\tilde{\mathcal{G}}_{S}^{n}$. Then compute $\tilde{\mathcal{G}}^{n}_{S,cpi}$
and $\tilde{\mathcal{G}}^{n}_{S,cyclic}$ For incomplete graphs, $\infty$ often
is assigned to inadmissible arcs; do so only with
$\tilde{\mathcal{G}}^{n}_{S,cyclic}.$

######  Theorem 15.

For an incomplete symmetric graph $\mathcal{G}^{n}_{S}$, let
$\tilde{\mathcal{G}_{S}^{n}}$ include the missing $\mathcal{G}_{S}^{n}$ arcs
where each has an arbitrary selected length. Compute
$T(\tilde{\mathcal{G}_{S}^{n}})$ and $\tilde{\mathcal{G}}^{n}_{S,cyclic}.$ The
length of a $\mathcal{G}_{S}^{n}$ Hamiltonian path is
$T(\tilde{\mathcal{G}}_{S}^{n})$ plus its $\tilde{\mathcal{G}}^{n}_{S,cyclic}$
length.

Computations can be simplified by adding arcs of zero length so that the
$S_{S}(V_{j})$ values for $\mathcal{G}_{S}^{n}$ and
$\tilde{\mathcal{G}_{S}^{n}}$ agree, and
$T(\mathcal{G}_{S}^{n})=T(\tilde{\mathcal{G}_{S}^{n}}).$

Proof: A Hamiltonian path length in $\mathcal{G}_{S}^{n}$ is the same in
$\tilde{\mathcal{G}_{S}^{n}}$, which equals $T(\tilde{\mathcal{G}_{S}^{n}})$
plus its length in $\tilde{\mathcal{G}^{n}}_{S,cyclic}.$ The result follows.
$\square$

As $\widehat{V_{1}V_{4}}$ and $\widehat{V_{2}V_{5}}$ are not admitted in Fig.
11, include them in Fig. 11a with zero lengths (the two dashed arcs in Fig.
11a). The $S_{S}(V_{j})$ values of $\tilde{\mathcal{G}_{S}^{n}}$ are
$S_{S}(V_{1})=27,S_{S}(V_{2})=27,S_{S}(V_{3})=39,S_{S}(V_{4})=23,S_{S}(V_{5})=23,S_{S}(V_{6})=51$.
Thus $T(\tilde{\mathcal{G}_{S}^{n}})=38,$
$\omega_{1}=\frac{1}{4}[27-19]=2,\omega_{2}=2,\omega_{3}=5,\omega_{4}=1,\omega_{5}=1,\omega_{6}=8,$
and Figs. 10b, c follow. The two inadmissible Fig. 11c arcs (both with length
of $-3$) could be dropped or, as in Fig. 11c, replaced with $\infty.$ The
shortest $\mathcal{G}^{6}_{S,cyclic}$ Hamiltonian path
$V_{1}\stackrel{{\scriptstyle-2}}{{\longrightarrow}}V_{3}\stackrel{{\scriptstyle
0}}{{\longrightarrow}}V_{2}\stackrel{{\scriptstyle-1}}{{\longrightarrow}}V_{6}\stackrel{{\scriptstyle-2}}{{\longrightarrow}}V_{4}\stackrel{{\scriptstyle
2}}{{\longrightarrow}}V_{5}\stackrel{{\scriptstyle
0}}{{\longrightarrow}}V_{1}$ of length $-3$, which includes all allowed arcs
with negative costs, can be found in the above described manner. In
$\mathcal{G}_{S}^{6}$ this path has the “below average” length of
$T(\mathcal{G}_{S}^{6})-3=35.$

$V_{1}$7503$V_{6}$127$V_{2}$4098$V_{3}$6134$V_{4}$7$V_{5}$10a. From
$\mathcal{G}_{S}^{6}$ to
$\widetilde{\mathcal{G}_{S}^{6}}$$V_{1}$4733$V_{6}$107$V_{2}$3310
6$V_{3}$6132$V_{4}$9$V_{5}$9=b.
$\widetilde{\mathcal{G}_{S,cpi}^{6}}$$V_{1}$3-2$\infty$0$V_{6}$20$V_{2}$1$\infty$-12$V_{3}$002$V_{4}$-2$V_{5}$1+c.
$\widetilde{\mathcal{G}_{S,cyclic}^{6}}$Figure 11. An incomplete
$\mathcal{G}_{S}^{6}$

While the method associated with Fig. 10 is more efficient than the GA, it is
worth using the structure of the decomposition to explain certain GA traits.
Parallel to the $\mathcal{G}^{n}_{A,cyclic}$ concern whether a vertex can be a
source, a $\mathcal{G}^{n}_{S,cyclic}$ worry is whether all of a vertex’s legs
are positive. But $S_{S}(V_{j})=0$, so this cannot happen. Thus, if all
$\mathcal{G}^{n}_{S,cyclic}$ vertices have an arc with non-zero length, then
the number of negative length arcs is bounded below by $\frac{n}{2}$ and above
by $\frac{n(n-2)}{2}$. Dropping $\mathcal{G}^{n}_{S,cpi}$ eliminates one GA
difficulty, but another is caused by the number of options. This can be seen
with Fig. 12a, which is given by
$\\{-x_{1}\mathbf{b}^{6}_{1,2,5,6}-x_{2}\mathbf{b}^{6}_{1,2,6,5}\\}$,
$\\{-y_{1}\mathbf{b}^{6}_{1,2,3,4},-y_{2}\mathbf{b}^{6}_{1,2,4,3}\\}$, and
$\\{-z_{1}\mathbf{b}^{6}_{3,4,5,6},-z_{2}\mathbf{b}^{6}_{3,4,6,5}\\},$ where
each bracket defines a rectangle. Thus $u=-(x_{1}+x_{2})-(y_{1}+y_{2})$,
$v=-(y_{1}+y_{2})-(z_{1}+z_{2})$, and $w=-(x_{1}+x_{2})-(z_{1}+z_{2})$. Should
the $x$’s, $y$’s, and $z$’s have positive values, the graph has
$\frac{n}{2}=3$ negative and $\frac{n(n-2)}{2}=12$ positive arc lengths.

$V_{1}$u$y_{2}$$y_{1}$$x_{2}$$V_{6}$$x_{1}$$y_{1}$$V_{2}$$y_{2}$$x_{1}$$x_{2}$v$V_{3}$$z_{2}$$z_{1}$$z_{1}$$V_{4}$$z_{2}$$V_{5}$wa.
A choice of
$\mathcal{G}^{6}_{S,cyclic}$$V_{1}$u$y_{2}$$y_{1}$$x_{2}$$V_{6}$$x_{1}$$y_{1}$$V_{2}$$y_{2}$$x_{1}$$x_{2}$
v$V_{3}$$z_{2}$$z_{1}$$z_{1}$$V_{4}$$z_{2}$$V_{5}$$\bullet$wb. Selecting
$z_{1}$$V_{1}$u$y_{2}$$y_{1}$$x_{2}$$V_{6}$$x_{1}$$y_{1}$$V_{2}$$y_{2}$$x_{1}$$x_{2}$v$V_{3}$$z_{2}$$z_{1}$$z_{1}$$V_{4}$$z_{2}$$V_{5}$wc.
Selecting $z_{2}$Figure 12. Potential failures of the Greedy Algorithm

It follows from the material following Cor. 7 that a shortest Hamiltonian path
must include the three arcs with negative lengths (of u, v, and w). Thus the
four-cycle symmetry requires all Hamiltonian paths of Fig. 12a with these
negative length arcs to have one of only four sizes where $u+v+w$ is
supplemented by $x_{1}+y_{1}+z_{1},x_{1}+y_{2}+z_{2},x_{2}+y_{1}+z_{1}$ or
$x_{2}+y_{2}+z_{2}$. Starting the GA at $V_{1}$ and assuming that $x_{1}$ is
smaller than $x_{2},y_{1},y_{2}$, the first three moves (Figs. 12b, c) are
$V_{1}\stackrel{{\scriptstyle
u}}{{\longrightarrow}}V_{2}\stackrel{{\scriptstyle
x_{1}}}{{\longrightarrow}}V_{5}\stackrel{{\scriptstyle
w}}{{\longrightarrow}}V_{6}$. The next move is to the $\widehat{V_{3}V_{4}}$
arc. Whichever way $\widehat{V_{3}V_{4}}$ is entered determines the last arc.

Should $z_{1}<z_{2}$, then Fig. 12b represents the fourth GA step
$V_{6}\stackrel{{\scriptstyle z_{1}}}{{\longrightarrow}}V_{3}$. But should
$y_{1}$ be much larger than $y_{2}$, the Fig. 12c route would be shorter. As
the arrangement of the $\mathcal{G}^{n}_{Scyclic}$ four-cycles can affect the
success of an algorithm, the algebra of these four-cycles needs to be better
understood.

For small values of $n$, and theoretically for all values, the basis for
$\mathbb{C}^{n}_{S}$ exhibits all possible $\mathcal{G}^{n}_{S,cyclic}$
choices. To illustrate an application, if arc costs represent Euclidean
distances in the planar problem and the triangle inequality is satisfied, then
minimal Hamiltonian paths cannot have a self intersection. It is reasonable to
wonder where else does the triangle inequality ensure this behavior. Here, the
structure of $\mathcal{G}^{n}_{S,cpi}$ plays a role.

######  Theorem 16.

For $n\geq 3$, $\mathcal{G}^{n}_{S,cpi}$ satisfies the triangle inequality iff
all weights $\omega_{j}$ are non-negative.

According to Eq. 13, $\omega_{k}<0$ represents where the associated
$S_{S}(V_{k})$ is bounded above by $\frac{1}{2}T(\mathcal{G}^{n}_{S})$. That
is, the average of arc lengths attached to $V_{k}$ is much smaller than
average over the graph.

Proof: The $\mathcal{G}^{n}_{S,cpi}$ arc length for $\widehat{V_{i}V_{j}}$ is
$\omega_{i}+\omega_{j}$. For a triplet, the length of the two arcs
$\widehat{V_{i}V_{j}}$ and $\widehat{V_{j}V_{k}}$ is
$\omega_{i}+2\omega_{j}+\omega_{k}$, which differs from the
$\widehat{V_{i}V_{k}}$ arc length by $2\omega_{j}$. Thus, the triangle
inequality is satisfied iff $\omega_{j}\geq 0$. This must hold for all legs of
all triplets, so $\omega_{j}\geq 0$ for all $j$. $\square$

Turning to $n=4$, Fig. 13a represents all possible
$\mathcal{G}^{4}_{S,cyclic}$ structures (with
$u\mathbf{b}^{4}_{1,4,2,3}+v\mathbf{b}^{4}_{1,2,3,4}$), so it characterizes
all closed path properties and their lengths for
$\mathcal{G}^{4}_{S}\in\mathbb{G}^{4}_{s}$. Assuming the rectangular Fig. 13a
faithfully represents the geometry of a considered concern (e.g., using actual
rather than Euclidean costs), the issue is to understand which $(u,v)$ values
(that is, which $\mathcal{G}^{4}_{S,cyclic}$) require a shortest Hamiltonian
path to avoid the crossing diagonals. The answer follows from Fig. 13a as it
requires the length of the two diagonals to be greater than that of the two
vertical and the two horizontal edges, or $-u>v,\,-u>u-v$; this is the open,
unbounded, shaded Fig. 13b region.

vvu-vu-v-u-u$V_{1}$$V_{4}$$V_{2}$$V_{3}$a. All
$\mathcal{G}^{4}_{S,cyclic}$$v=-u$$v=2u$b. No diagonal crossingsu axisv
axis$u=-\omega$$v=\omega$$v=u-\omega$c. Triangle inequalityu axisv
axis$V_{1}$$V_{2}$$V_{3}$$V_{4}$$V_{5}$v+y-z-v+w+zx-y+zv-w+xw-x+y-x-v-w-y-zd.
All $\mathcal{G}^{5}_{S,cyclic}$ choicesFigure 13. Finding properties of
$\mathcal{G}^{n}_{S,cyclic}$

To compare this wedge with what happens should $\mathcal{G}^{4}_{S}$ satisfy
the triangle inequality, it follows from Thm. 16 that in a
$\\{V_{i},V_{j},V_{k}\\}$ triangle, the sum of the $\widehat{V_{i}V_{k}}$ and
$\widehat{V_{k}V_{j}}$ leg lengths in $\mathcal{G}^{4}_{S,cyclic}$ plus
$2\omega_{k}$ must be an upper bound for $\widehat{V_{i}V_{j}}$’s
$\mathcal{G}^{4}_{S,cyclic}$ leg length. Applying this to the three triangles
where vertex $V_{k}$ is off the triangle’s compared edge leads to

(14) $\omega_{k}\geq-u,\quad\omega_{k}\geq v,\quad\omega_{k}\geq u-v.$

######  Theorem 17.

For $\mathcal{G}^{4}_{S}$, if any $\omega_{j}<0$, then $\mathcal{G}^{4}_{S}$
does not satisfy the triangle inequality. Let
$\omega=\min(\omega_{1},\omega_{2},\omega_{3},\omega_{4})$. The region where
$\mathcal{G}^{4}_{S}$ satisfies the triangle inequality is defined by
substituting $\omega$ for $\omega_{k}$ in Eq. 14; it is depicted by the closed
shaded triangle in Fig. 13c.

Proof: If $\omega_{k}<0$. then Eq. 14 cannot be satisfied. The remainder
follows from the above. $\square$

If $\omega=0$, the triangle inequality is satisfied only for $u=v=0$, which is
$\mathcal{G}^{4}_{S,cyclic}=0$ so
$\mathcal{G}^{4}_{S}=\mathcal{G}^{4}_{S,cpi}$. Both the triangle inequality
and the non-crossing of the diagonals in the shortest Hamiltonian path hold in
the intersection of the shaded portions of Figs. 13b, c; this is the Fig. 13b
shaded triangle limited on the left by $u\geq-\omega$. What remains are
regions (i.e., choices of $\mathcal{G}^{4}_{S,cyclic}$) where the triangle
inequality is satisfied but the shortest Hamiltonian path includes the
diagonals, and a sizable region (the shaded Fig. 13b region for $u<-\omega$)
where the diagonals are not in the shortest Hamiltonian circuit and the
triangle inequality is not satisfied.

Results for $\mathcal{G}^{5}_{S,cyclic}$ follow in a similar manner. The basis
for Fig. 13d, which captures all $\mathcal{G}^{5}_{S,cyclic}$ behaviors, is
$\\{v\mathbf{b}^{5}_{1,2,3,4}+w\mathbf{b}^{5}_{2,3,4,5}+x\mathbf{b}^{5}_{3,4,5,1}+$
$y\mathbf{b}^{5}_{4,5,1,2}+z\mathbf{b}^{5}_{5,1,2,3}\\}$.

##  4\. Graphs with general asymmetric costs

Other systems can be similarly reduced. Graphs where all closed paths have a
fixed length identify components of $\mathcal{G}^{n}$ entries that frustrate a
closed path analysis. The subspace’s normal bundle measures deviations from
neutrality, so it is critical when determining closed path properties.

None of this is necessary for the standard space of graphs with asymmetric
costs. The reason is that, for each pair, the arc lengths
$V_{j}\stackrel{{\scriptstyle x}}{{\longrightarrow}}V_{k}$ and
$V_{k}\stackrel{{\scriptstyle y}}{{\longrightarrow}}V_{j}$ can be represented
as an {average cost, excess cost} pair; e.g.,
$\\{a=\frac{x+y}{2},V_{j}\stackrel{{\scriptstyle
x-a}}{{\longrightarrow}}V_{k}\\}$. By applying the Sects. 2 and 3 approaches
to each component, the above results about incomplete graphs, path lengths,
etc., transfer.

$V_{1}$$V_{2}$$V_{3}$$V_{4}$$V_{5}$1519192312229251921261421232463214240a. A
general $\mathcal{G}^{5}$Figure 14. Decomposing an asymmetric
$\mathcal{G}^{5}$$\to$+$V_{1}$$V_{2}$$V_{3}$$V_{4}$$V_{5}$$-3$$3$$1$$-3$$2$20-11-2b.
$\mathcal{G}^{5}_{S,cyclic}$.$V_{1}$$V_{2}$$V_{3}$$V_{4}$$V_{5}$$2$$0$$0$$1$$1$02021c.
$\mathcal{G}^{5}_{A.cyclic}$$V_{1}$$V_{2}$$V_{3}$$V_{4}$$V_{5}$-1-531-2-43122-2-13-1-3-1d.
Reduced $\mathcal{G}^{5}$=

To illustrate this program with Fig. 14, by representing the Fig. 14a costs as
{average cost, excess cost} pairs, the original graph becomes
$\mathcal{G}^{5}=\mathcal{G}^{5}_{S}+\mathcal{G}^{5}_{A}\in\mathbb{G}^{5}_{S}\times\mathbb{G}^{5}_{A}$,
where $\widehat{V_{j}V_{k}}$’s length in $\mathcal{G}^{5}_{S}$ is the average
cost of its arcs, and $\mathcal{G}^{5}_{A}$ represents how costs differ from
the average. Thus, with $V_{1}\stackrel{{\scriptstyle
26}}{{\longrightarrow}}V_{3}$ and $V_{3}\stackrel{{\scriptstyle
14}}{{\longrightarrow}}V_{1}$ from Fig. 14a, $\widehat{V_{1}V_{3}}$’s length
in $\mathcal{G}^{5}_{S}$ is $20$ and $\mathcal{G}^{5}_{A}$ has
$V_{1}\stackrel{{\scriptstyle 6}}{{\longrightarrow}}V_{3}$.

The analysis of $\mathcal{G}^{5}_{S}+\mathcal{G}^{5}_{A}$ follows as above:
find each graph’s cpi and cyclic components. Removing
$\mathcal{G}^{5}_{S,cpi}$ and $\mathcal{G}^{5}_{A,cpi}$ leaves Figs. 14b, c. A
$\mathcal{G}^{5}$ Hamiltonian path length (with $\mathcal{G}^{5}_{S,cpi}$
weights
$\omega_{1}=10,\,\omega_{2}=10,\,\omega_{3}=8,\,\omega_{4}=12,\,\omega_{5}=6$)
equals $T(\mathcal{G}^{5}_{S,cpi})=92$ plus the sum of its
$\mathcal{G}^{5}_{S,cyclic}$ and $\mathcal{G}^{5}_{A,cyclic}$ lengths.
Expressing $\mathcal{G}^{5}_{S,cyclic}+\mathcal{G}^{5}_{A,cyclic}$ in a
standard Fig. 14d form, its shortest Hamiltonian path of
$V_{1}\stackrel{{\scriptstyle-5}}{{\longrightarrow}}V_{2}\stackrel{{\scriptstyle-1}}{{\longrightarrow}}V_{4}\stackrel{{\scriptstyle-4}}{{\longrightarrow}}V_{3}\stackrel{{\scriptstyle-3}}{{\longrightarrow}}V_{5}\stackrel{{\scriptstyle
1}}{{\longrightarrow}}V_{1}$ follows. Its $\mathcal{G}^{5}$ path length is
$T(\mathcal{G}^{5}_{S,cpi})-12=80$.

##  5\. Summary

Components of a graph’s entries that hamper finding closed path properties are
identified. Eliminating them determines the graph’s essence—a reduced graph
with smaller degrees of freedom where all closed graph properties are
expressed in terms of inherent symmetry structures.

##  6\. Proofs

Results not proved above or in [4], are proved here.

Proof of Theorem 1: For a triplet $\\{V_{i},V_{j},V_{k}\\}$ in a cpi graph,
the closed path $V_{i}\stackrel{{\scriptstyle
x}}{{\longrightarrow}}V_{j}\stackrel{{\scriptstyle
y}}{{\longrightarrow}}V_{k}\stackrel{{\scriptstyle
z}}{{\longrightarrow}}V_{i}$ has path length zero, so $x+y=-z.$ Thus,
$V_{i}\stackrel{{\scriptstyle
x}}{{\longrightarrow}}V_{j}\stackrel{{\scriptstyle
y}}{{\longrightarrow}}V_{k}=V_{i}\stackrel{{\scriptstyle-z=x+y}}{{\longrightarrow}}V_{k}$
satisfies Eq. 3. As all triplets satisfy Eq. 3, a cpi graph is strongly
transitive.

A triplet $\\{V_{i},V_{j},V_{s}\\}$ in a strongly transitive graph satisfies
$V_{i}\stackrel{{\scriptstyle
x}}{{\longrightarrow}}V_{j}\stackrel{{\scriptstyle
y}}{{\longrightarrow}}V_{s}=V_{i}\stackrel{{\scriptstyle
z}}{{\longrightarrow}}V_{s}$ where $z=x+y$. Applying a fourth alternative
$V_{t}$ to this relationship yields

$(V_{i}\stackrel{{\scriptstyle
x}}{{\longrightarrow}}V_{j}\stackrel{{\scriptstyle
y}}{{\longrightarrow}}V_{s})\stackrel{{\scriptstyle
u}}{{\longrightarrow}}V_{t}=(V_{i}\stackrel{{\scriptstyle
z}}{{\longrightarrow}}V_{s})\stackrel{{\scriptstyle
u}}{{\longrightarrow}}V_{t}=V_{i}\stackrel{{\scriptstyle
w}}{{\longrightarrow}}V_{t},$

where $w=z+u=x+y+u.$ With the obvious induction argument, it follows that any
path from $V_{i}$ to $V_{k}$ has the same length as the direct path from
$V_{i}$ to $V_{k}$. (This proves Cor. 1.) A closed path has $V_{k}=V_{i}$, so
its length is that of $V_{i}$ to $V_{i}$, or zero. Hence, a strongly
transitive graph is cpi.

To prove that the set of strongly transitive graphs forms a linear subspace,
notice that a multiple $\mu$ of a strongly transitive graph in
$\mathbb{G}^{n}_{A}$ changes all path lengths by this multiple; thus the new
graph’s arcs remain strongly transitive. Therefore the multiple defines
another $\mathbb{G}^{n}_{A}$ strongly transitive graph. (If $\mu<0$, then
positive cost arcs in the original graph become negative cost arcs in the new
graph.) Similarly, for two strongly transitive $\mathbb{G}^{n}_{A}$ graphs and
any $\\{V_{i},V_{j},V_{k}\\}$ triplet, the first graph satisfies
$V_{i}\stackrel{{\scriptstyle
x}}{{\longrightarrow}}V_{j}\stackrel{{\scriptstyle
y}}{{\longrightarrow}}V_{k}=V_{i}\stackrel{{\scriptstyle
x+y}}{{\longrightarrow}}V_{k}$ while the second satisfies
$V_{i}\stackrel{{\scriptstyle\tilde{x}}}{{\longrightarrow}}V_{j}\stackrel{{\scriptstyle\tilde{y}}}{{\longrightarrow}}V_{k}=V_{i}\stackrel{{\scriptstyle\tilde{x}+\tilde{y}}}{{\longrightarrow}}V_{k}.$
Combining these graphs leads to $V_{i}\stackrel{{\scriptstyle
x+\tilde{x}}}{{\longrightarrow}}V_{j}\stackrel{{\scriptstyle
y+\tilde{y}}}{{\longrightarrow}}V_{k}=V_{i}\stackrel{{\scriptstyle(x+y)+(\tilde{x}+\tilde{y})}}{{\longrightarrow}}V_{k}$,
which satisfies Eq. 3. Thus the set of strongly transitive graphs in
$\mathbb{G}^{n}_{A}$, $\mathbb{ST}_{A}^{n}$, is a linear subspace. $\square$

Proof of Cor. 2: The Eq. 4 basis of $\\{V_{1}\stackrel{{\scriptstyle
1}}{{\longrightarrow}}V_{j}\stackrel{{\scriptstyle
1}}{{\longrightarrow}}V_{k}\stackrel{{\scriptstyle
1}}{{\longrightarrow}}V_{1}\\}_{1<j<k\leq n}$ satisfies Cor. 2 because in this
set, only the three cycle $V_{1}\stackrel{{\scriptstyle
1}}{{\longrightarrow}}V_{s}\stackrel{{\scriptstyle
1}}{{\longrightarrow}}V_{k}\stackrel{{\scriptstyle
1}}{{\longrightarrow}}V_{1}$ has a $\widehat{V_{s}V_{k}}$ arc. For the
independence of the arcs, if $\mathbf{c}_{j,k}$ represents the only
$\mathcal{CB}^{n}_{A}$ cycle with a $\widehat{V_{j}V_{k}}$ arc, it must be
shown that $\sum x_{j,k}\mathbf{c}_{j,k}=\mathbf{0}$ iff all $x_{j,k}=0.$ But
as $\mathbf{c}_{j,k}$ is the only vector with a non-zero ${j,k}$ component,
$x_{j,k}=0.$

That theses cycles are in $\mathbb{ST}_{A}^{n}$’s normal bundle is proved in
[4]. As this set consists of ${n-1}\choose 2$ linearly independent elements
that are orthogonal to $\mathbb{ST}^{n}_{A}$, it is a basis for the normal
bundle. $\square$

Proof of Thm. 3: Equation 5 is an immediate consequence of the representation
of $\mathbb{G}_{A}^{n}$ into the orthogonal subspaces $\mathbb{ST}_{A}^{n}$
and $\mathbb{C}^{n}_{A}$. The last comment is proved above.$\square$

Proof of Cor. 5: That the Def. 3 relationship is an equivalence relationship
(reflexive, symmetricaA, transitive) follows immediately from the equality of
the cyclic components. The difference between any two graphs in
$\mathbb{G}^{n}_{A}$ is the difference between their cpi and cyclic
components. As their cyclic components agree, the difference is the difference
between cpi components. Because $\mathbb{ST}_{A}^{n}$ is a linear subspace,
this difference also is in $\mathbb{ST}_{A}^{n}$. $\square$

Proof of Thm. 6: The fact that $\mathcal{G}^{n}_{A,cpi}$ normally has a sink
and source for positive and negative directions follows from the fact that all
triplets are transitive, so there is a maximum and a minimum term. That its
arc lengths are non-zero means that this top and bottom alternative are
unique. For positive directions, the top alternative is a source, the bottom
alternative is a sink.

The assertion that $\mathcal{G}^{n}_{A,cyclic}$ cannot have a source or a sink
follows from the fact that $S_{A}(V_{j})=0$ for each vertex. (This statement
follows from the fact that each three-cycle attache to a vertex has one leg
pointing in and one leg, of same magnitude, pointing out.) Thus, each
$\mathcal{G}^{n}_{A,cyclic}$ vertex with non-zero arcs has at least one
positive direction pointing in and at least one pointing out.

What remains is to show that the longest Hamiltonian path in
$\mathcal{G}^{n}_{A,cyclic}$, $n=4,5$, has all positive directions. It already
has been shown that $\mathcal{G}^{n}_{A,cyclic}$ does not have a sink or
source. The next possible problem is three-cycle with, say, positive cost
arcs, e.g., $V_{2}\to V_{3}\to V_{4}\to V_{2}$. To avoid having all positive
arcs in the longest paths, the cycle must be attracting. But for $n=4$, that
would require all positive cost directions to point away from $V_{1}$, making
$V_{1}$ a source, which it cannot be. For $n=5$, all positive cost arrows from
$V_{1}$ and $V_{5}$ point to the cycle. The positive cost arrow between
$V_{1}$ and $V_{5}$ points away from one of these vertices, making it a
source, which is a contradiction. An attracting four cycle would make the
remaining vertex a source. Everything extends in the same manner for sinks and
for negative cost directions. $\square$

Proof of Thm. 8: While the linear algebra proof used for $n=4$ extends, an
iterative argument provides insight. One set of closed paths involves the
vertices $\\{V_{1},V_{2},V_{3},V_{4}\\}$; these cpi graphs are based on
weights $\omega_{j}$ attached to $V_{j}$, $j=1,\dots,4$. Increasing the graph
size to involve vertices $\\{V_{1},V_{2},V_{3},V_{4},V_{5}\\}$ requires
analyzing all closed graphs in $\\{V_{1},V_{2},V_{3},V_{5}\\}$. Again, the
solution has weights $\omega^{\prime}_{k},\,k=1,2,3,5$ assigned to the
appropriate vertices. To be consistent with arc lengths in the first 4-tuple,
it must be that $\omega^{\prime}_{k}=\omega_{k}$ for $k=1,2,3$. Continuing in
this iterative manner extends the proof to all vertices. That the length of a
closed path passing through the vertices $\\{V_{j}\\}_{j\in\mathcal{D}}$ once
is $2\sum_{j\in{\mathcal{D}}}\omega_{j}$ is an immediate computation. As a
path enters and leaves vertex $V_{j}$, the length is increased by
$2\omega_{j}.$ $\square$

Proof of Thm. 9: Set $\\{\mathbf{B}^{n}_{j}\\}_{j=1}^{n-1}$ is independent
because only $\mathbf{B}^{n}_{j}$ has a non-zero $d_{j,n}$ coordinate. If
$\\{\mathbf{B}^{n}_{j}\\}_{j=1}^{n}$ is not independent, there is a summation
$\sum_{j=1}^{n-1}x_{j}\mathbf{B}^{n}_{j}=\mathbf{B}^{n}_{n}.$ In the sum, each
$x_{j}=1$ to capture $\mathbf{B}^{n}_{n}$’s $d_{j,n}=1$ component. But then
$d_{1,2}=2$ (from $\mathbf{B}^{n}_{1}+\mathbf{B}^{n}_{2}$), rather than the
required zero of $\mathbf{B}^{n}_{n}$, so the linear subspace spanned by
$\\{\mathbf{B}^{n}_{j}\\}_{j=1}^{n}$ is $n$-dimensional. This space captures
the structure of $\mathcal{G}^{n}_{S,cpi}$ graphs because the $d_{i,j}$
component of $\sum_{s=1}^{n}\omega_{s}\mathbf{B}^{n}_{s}$ is the required
$\omega_{i}+\omega_{j}$. $\square$

Proof of Thm. 14: A path’s length in $\mathcal{G}^{n}_{S}$ is the sum of its
lengths in $\mathcal{G}^{n}_{S,cpi}$ and in $\mathcal{G}^{n}_{S,cyclic}$.
$\square$

## References

  * [1] Arrow, K., (1963) Social choice and individual values. (New York, NY: Wiley).
  * [2] Cook, W. (2012) In Pursuit of the Traveling Salesman, (Princeton University Press, Princeton).
  * [3] Jessie, D., and D. G. Saari (2019) Coordinate Systems for Games: Simplifying the “me” and “we” interactions.” (Springer, New York).
  * [4] Saari, D. G. (2021) Seeking consistency with paired comparisons: A systems approach, Theory and Decisions, 91 (3) 377-402.