Hamiltonian Cycles in Signed and Multisigned Complete Graphs

Xiyong Yan · 2025

Read Hamiltonian Cycles in Signed and Multisigned Complete Graphs by Xiyong Yan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-10612.txt.

Introduction

Xiyong Yan settled in 2025 a clean question in graph theory: when does a complete graph with signed edges hold round trips of both signs? Each edge carries a plus or a minus, and a Hamiltonian cycle visits every vertex once. The sign of any trip is read from its edges, and triangles are the smallest trips of all.

Yan proves the big trips mirror the small ones. Both signs of Hamiltonian cycle appear exactly when both signs of triangle appear. If all triangles are negative, every big trip is negative for odd counts and positive for even; if all are positive, all trips are positive. The result extends to edges carrying many signs: varied trips exist exactly when varied triangles do. The theorem ties global structure to a three-vertex test.

Catalog record

CREATORXiyong Yan
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE9 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-10612

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Hamiltonian Cycles in Signed and Multisigned Complete Graphs Xiyong Yan Abstract . A signed complete graph on n n vertices contains both positive and negative Hamiltonian cycles if and only if it also contains both positive and negative triangles. Otherwise, all Hamiltonian cycles are negative if and only if all triangles are negative and n n is odd, while all Hamiltonian cycles are positive if and only if all triangles are negative and n n is even, or all triangles are positive. Extending these results to multisigned complete graphs, we prove that such a graph contains at least two Hamiltonian cycles with different multisigns if and only if it contains at least two triangles with different multisigns. 1. Introduction Our research question originates from the paper “Negative (and Positive) Circles in Signed Graphs: A Problem Collection” [ 2 ] . In it, the author poses the question: Assume a signed graph has a Hamiltonian cycle and is unbalanced. Is there a negative Hamiltonian cycle? A positive one? In our study, we narrow the focus to signed complete graphs and expand it to multisigned complete graphs. We establish the relationship between the multisigns of Hamiltonian cycles and the multisigns of triangles in a multisigned complete graph. To achieve this, we utilize the Hourglass Lemma and the Consistent Triangle Multisign Lemma. In the special case of signs, this shows the complete relationship between the signs of Hamiltonian cycles and the signs of triangles in a signed complete graph. 2. Preliminaries A signed graph \Sigma=(\Gamma,\sigma) consists of an underlying graph \Gamma=(V,E) , where V denotes the set of vertices and E the set of edges, and a sign function \sigma that assigns either + or - to each edge in \Gamma . A multisigned graph \Sigma=(\Gamma,\sigma,G) consists of the following components: The base graph is \Gamma=(V,E) . The group G:=\{-1,+1\}^{m} with componentwise multiplication. The identity element of G is denoted by e . The multisign function is \sigma:E\to G . The multisign of a multisigned cycle P , denoted by \sigma(P) , is defined as the product of the multisigns of all edges of P . \Sigma is called balanced if every cycle has multisign e . 3. Hourglass Lemma: Sign Consistency of Hamiltonian Cycles Lemma 3.1 (Hourglass Lemma) . Let v_{1},v_{2},\dots,v_{n} be vertices of a multisigned complete graph \Sigma=(K_{n},\sigma,G) . Two Hamiltonian cycles v_{1}v_{2}\dots v_{n} and v_{1}v_{2}\dots v_{i}v_{j}v_{j-1}\dots v_{i+1}v_{j+1}\dots v_{n} , have the same multisign if and only if \sigma(v_{i}v_{i+1})\sigma(v_{j}v_{j+1})=\sigma(v_{i}v_{j})\sigma(v_{i+1}v_{j+1}) , where j>i and v_{i},v_{i+1},v_{j},v_{j+1} are distinct for some i,j\in\{1,2,\dots,n\} . Figure 1. Illustration of the Hourglass Shape used in the proof of Lemma 3.1 . Proof. Consider two Hamiltonian cycles v_{1}v_{2}\dots v_{i}v_{j}v_{j-1}\dots v_{i+1}v_{j+1}\dots v_{n} and v_{1}v_{2}\dots v_{n} , where j>i and v_{i},v_{i+1},v_{j},v_{j+1} are distinct. Let A=\sigma(v_{1}v_{2}\dots v_{n})\sigma(v_{1}v_{2}\dots v_{i}v_{j}v_{j-1}\dots v_{i+1}v_{j+1}\dots.v_{n}). Break each multisign of the Hamiltonian cycle into the product of the multisigns of its edges. We get \displaystyle A= \displaystyle\sigma(v_{1}v_{2})\sigma(v_{2}v_{3})\dots\sigma(v_{n}v_{1})\cdot\sigma(v_{1}v_{2})\sigma(v_{2}v_{3})\dots\sigma(v_{i-1}v_{i})\sigma(v_{i}v_{j}) \displaystyle\cdot\sigma(v_{j}v_{j-1})\dots\sigma(v_{i+2}v_{i+1})\sigma(v_{i+1}v_{j+1})\sigma(v_{j+1}v_{j+2})\dots\sigma(v_{n}v_{1}). That is, A=\sigma(v_{i}v_{i+1})\sigma(v_{j}v_{j+1})\sigma(v_{i}v_{j})\sigma(v_{i+1}v_{j+1}). Therefore, if the two Hamiltonian cycles have the same multisign, A has a multisign e . This implies \sigma(v_{i}v_{i+1})\sigma(v_{j}v_{j+1})=\sigma(v_{i}v_{j})\sigma(v_{i+1}v_{j+1}). Conversely, if the two Hamiltonian cycles have different multisigns, the above equation does not hold. As required. ∎ 4. Characterization of Unbalanced Complete Graphs and Consistent Triangle Multisign Lemma Lemma 4.1 . Let P be a cycle in a multisigned complete graph with vertices v_{1},v_{2},\dots,v_{k} . After adding edges v_{1}v_{3},v_{1}v_{4},\dots,v_{1}v_{k-1} to P , decompose the resulting graph into triangles \triangle v_{1}v_{2}v_{3},\triangle v_{1}v_{3}v_{4},\dots,\triangle v_{1}v_{k-1}v_{k}. Then the multisign of P is equal to the product of the multisigns of all these triangles. Lemma 4.2 . A multisigned complete graph \Sigma is unbalanced if and only if \Sigma contains a triangle with a non-identity multisign. Proof. Consider a multisigned complete graph \Sigma that is unbalanced. Assume, for contradiction, that all triangles have multisign e . By Lemma 4.1 , all cycles in \Sigma would then have multisign e . This implies that \Sigma is balanced, which contradicts the assumption that \Sigma is unbalanced. Thus, \Sigma contains a triangle with a non-identity multisign. Conversely, suppose \Sigma contains a triangle with a non-identity multisign. Then by definition, \Sigma is unbalanced. ∎ Lemma 4.3 . If all the Hamiltonian cycles have the same multisign in a multisigned complete graph \Sigma , where n\geq 4 , then all triangles have the same multisign. Figure 2. Illustration for the proof of Lemma 4.3 . Proof. Let the vertices of \Sigma be labeled 1,2,\dots,n . Let \triangle lmq and \triangle lpq be two triangles that share an edge lq . Consider two Hamiltonian cycles lmpqv_{1}v_{2}\dots v_{n-4} and lpmqv_{1}v_{2}\dots v_{n-4} . Since we assume that all the Hamiltonian cycles in \Sigma have the same multisign, by the Hourglass Lemma we have \sigma(pq)\sigma(lm)=\sigma(lp)\sigma(mq). This implies \sigma(lm)\sigma(mq)\sigma(lq)=\sigma(pq)\sigma(lp)\sigma(lq). That is equivalent to \sigma(\triangle lmq)=\sigma(\triangle lpq). Hence, these two triangles have the same multisign. Let \triangle v_{i}v_{j}v_{k} and \triangle v_{r}v_{s}v_{t} be any two triangles in \Sigma , for distinct i,j,k,r,s,t\in\{1,2,\dots,n\} . By the result from last paragraph, we have \sigma(\triangle v_{i}v_{j}v_{k})=\sigma(\triangle v_{i}v_{j}v_{r})=\sigma(\triangle v_{i}v_{r}v_{s})=\sigma(\triangle v_{r}v_{s}v_{t}). If two indices are equal, e.g., i=t , the argument is the same. This implies that all the triangles in \Sigma have the same multisign. As required. ∎ 5. Signs of Hamiltonian Cycles The relationship between the signs of Hamiltonian cycles and the signs of triangles is as follows: Theorem 5.1 . Consider a signed complete graph \Sigma_{n,\sigma}=(K_{n},\sigma) , where n\geq 4 . (a) All Hamiltonian cycles are negative if and only if all triangles are negative and n is odd, while all Hamiltonian cycles are positive if and only if all triangles are negative and n is even, or all triangles are positive. (b) A signed complete graph \Sigma_{n,\sigma} contains both a positive Hamiltonian cycle and a negative Hamiltonian cycle if and only if it contains at least one positive triangle and at least one negative triangle. Proof. We deduce Theorem 5.1 from Theorem 5.2 by taking m=1 . ∎ Theorem 5.2 . Consider a multisigned complete graph \Sigma=(K_{n},\sigma,G) , where n\geq 4 and m\geq 1 . (a) Let g be a fixed non-identity element of the multisign group G . All Hamiltonian cycles in \Sigma have the same multisign g if and only if all triangles have multisign g and n is odd. Similarly, all Hamiltonian cycles have multisign e if and only if either all triangles have the same non-identity multisign and n is even, or all triangles have multisign e . (b) The graph \Sigma contains at least two Hamiltonian cycles with different multisigns if and only if it contains at least two triangles with different multisigns. Proof. Proof of part (a). Let P be any Hamiltonian cycle in \Sigma with vertices v_{1},v_{2},...,v_{n} . Construct triangles as in Lemma 4.1 . By Lemma 4.1 , we have \sigma(P)=\sigma(\triangle v_{1}v_{2}v_{3})\sigma(\triangle v_{1}v_{3}v_{4})\dots\sigma(\triangle v_{1}v_{n-1}v_{n}). If all triangles have the same non-identity multisign g and n is odd, then \sigma(P)=g^{n-2}=g. Thus, all Hamiltonian cycles have multisign g . Conversely, assume all Hamiltonian cycles have the same non-identity multisign g . By Lemma 4.3 , all triangles have the same multisign. Since the graph is unbalanced, it contains a triangle with a non-identity multisign h\in G by Lemma 4.2 , which implies that all triangles have the same multisign h . Let P be any Hamiltonian cycle. From Lemma

Read the complete text