Double Signs of Hamiltonian Circles in Doubly Signed Complete Graphs

Xiyong Yan · 2025

Read Double Signs of Hamiltonian Circles in Doubly Signed 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-2509-16646.txt.

Introduction

Xiyong Yan studies loops in signed graphs in a 2025 solo math paper. Each edge in the graph carries a label from a small set. A loop that visits every vertex once is called Hamiltonian. Its total label, summed around the loop, is its double sign. Yan asks when loops can achieve all four possible signs.

He proves that three distinct signs among small triangles are enough. The proof leans on triangle bases in a binary cycle space. It also uses the structure of tiny subgraphs and builds loops by hand. The result ties a local clue, signs on triangles, to a global trait of the whole graph.

Catalog record

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

Source: https://arxiv.org/abs/2509-16646

Browse the full library · About the Tower of Babel

Full text

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

Double Signs of Hamiltonian Circles in Doubly Signed Complete Graphs Xiyong Yan Abstract . We study Hamiltonian circles in the doubly signed complete graph Σ n = ( K n , σ , 𝔽 2 2 ) \Sigma_{n}=(K_{n},\sigma,\mathbb{F}_{2}^{2}) . A circle’s double sign is defined as the sum of its edge labels. I establish conditions under which Hamiltonian circles realize all four possible double signs and prove that this occurs when the set of triangle double signs contains at least three distinct values. The proof is based on an analysis of triangle bases of the binary cycle space, structural properties of K 4 K_{4} subgraphs, and explicit Hamiltonian constructions. 1 1 1 2020 Mathematics Subject Classification Primary: 05C45 (Hamiltonian graphs); Secondary: 05C22 (Signed and weighted graphs) 1. Introduction Signed graphs, introduced by Harary in the 1950s, assign to each edge a sign from the group \mathbb{F}_{2} . A central object of study is the sign of a circle, defined as the sum of its edge signs. Our research question originates in the problem collection “Negative (and Positive) Circles in Signed Graphs” [ 1 ] , where the author asks: if a signed graph is unbalanced and has a Hamiltonian circle, must it contain a negative Hamiltonian circle? A positive one? In [ 2 ] I prove that a signed complete graph on n vertices contains both a positive and a negative Hamiltonian circle if and only if it also contains both a positive and a negative triangle. In this paper we consider the case of doubly signed graphs , where each edge of the complete graph K_{n} is labeled by an element of \mathbb{F}_{2}^{2} . For a circle C\subseteq K_{n} , its double sign is the sum of the labels of its edges. Every circle therefore has one of four possible values, and understanding which values occur is a natural problem. Triangles are of particular importance since they form a basis for the binary cycle space Z_{2}(K_{n}) and thus determine the behavior of all circles. Our focus is on Hamiltonian circles in \Sigma_{n}=(K_{n},\sigma,\mathbb{F}_{2}^{2}) , where n>5 . Determining the range of their double signs turns out to depend only on the diversity of double signs realized by triangles. The main theorem shows that if triangles are restricted to at most two signs, then the Hamiltonian circles cannot achieve the full set (See Lemma 2.1 and the remark 1). Conversely, if the triangles of \Sigma_{n} produce at least three distinct double signs, then Hamiltonian circles realize all four possible values in \mathbb{F}_{2}^{2} (See Lemma 2.5 , 3.3 ). 2. Triangle Double Signs: One, Two, or Three Cases The (binary) cycle space of an undirected graph is the set of its even-degree subgraphs, denoted as Z_{2}(G) , where the undirected graph is G=(V,E) . Let \Sigma_{n}=(K_{n},\sigma,\mathbb{F}_{2}^{2}) , with vertices v_{1},v_{2},\ldots,v_{n} , where \sigma\colon E\to\mathbb{F}_{2}^{2} . Choose a triangle basis of the cycle space Z_{2}(K_{n}) : \mathcal{B}=\{{T_{1ij}}:2\leq i<j\leq n\},\quad\text{where the triangle }{T_{1ij}}:=\triangle\{v_{1},v_{i},v_{j}\}. Lemma 2.1 . If the double signs of all triangles in \Sigma_{n} are either x or y , where x,y\in\mathbb{F}_{2}^{2} , then \Sigma_{n} does not contain all possible double signs of Hamiltonian circles. Proof. Let H be any Hamiltonian circle of \Sigma_{n} . Note that the vertex v_{1} is in H , and H contains the sequence of vertices v_{1},v_{2}^{\prime},v_{3}^{\prime},\ldots,v_{n}^{\prime} , where the distinct vertices v_{2}^{\prime},v_{3}^{\prime},\ldots,v_{n}^{\prime}\in\{v_{2},v_{3},\ldots,v_{n}\} . We can decompose H into triangles T_{1i(i+1)}:=\triangle\{v_{1},v_{i}^{\prime},v_{i+1}^{\prime}\} , for i=2,3,\ldots,n-1 . Then, \sigma({H})=\sum_{i=2}^{n-1}\sigma(T_{1i(i+1)})=ax+by, since all triangles have double signs either x or y , where a,b\in\{0,1,\ldots,n-2\} and a+b=n-2 . We now consider two cases based on the parity of n : Case 1. n is odd. Then n-2 is odd, so the sum ax+by must be either x or y . Thus, \Sigma_{n} cannot contain all possible double signs of Hamiltonian circles. Case 2. n is even. Then n-2 is even, so the possible values of ax+by are limited to x+y or e=(0,0) . Again, \Sigma_{n} cannot contain all possible double signs of Hamiltonian circles. ∎ Remark 1 . If all triangles have the same double sign x , then \sigma(H)=\sum_{i=2}^{n-1}\sigma(T_{1i(i+1)})=t\,x with t\in\{0,1\} . Definition 1 (Normalization at a vertex) . To normalize a vertex v means to perform a switching so that every edge incident with v is labeled by the identity e=(0,0) . Proposition 2.2 . If \Sigma_{n} contains only three distinct double signs among all triangles, then after normalizing a vertex v of \Sigma_{n} , every edge of \Sigma_{n}\backslash v has a double sign among these three types. Proof. Let v_{i}v_{j} be any edge in \Sigma_{n}\backslash v . Then, \sigma(\triangle v_{i}v_{j}v)=\sigma(v_{i}v_{j})+e+e=\sigma(v_{i}v_{j}). ∎ Lemma 2.3 . If \Sigma_{n} has at most three distinct triangle double signs, then every K_{4}\subseteq\Sigma_{n} has at most two distinct triangle double signs. Proof (Contrapositive). Suppose there exists a K_{4}\subseteq\Sigma_{n} whose four triangles realize at least three distinct double signs. Choose three triangles from this K_{4} with distinct double signs x,y,z\in\mathbb{F}_{2}^{2} . The fourth triangle then has double sign x+y+z . Since x,y,z are distinct, the element x+y+z is the element of \mathbb{F}_{2}^{2} not in \{x,y,z\} . Hence \Sigma_{n} exhibits four distinct triangle double signs, contradicting the assumption that there are at most three. ∎ Lemma 2.4 . If \Sigma_{n} contains only three distinct double signs among all triangles, then the basis \mathcal{B} contains triangles realizing each of these three signs. Proof. Let the three distinct double signs be x,y,z\in\mathbb{F}_{2}^{2} . Suppose no triangle in \mathcal{B} has double sign x . Then, Without loss of generality, say some triangle T_{234} outside \mathcal{B} has double sign x . Consider the induced K_{4} on \{v_{1},v_{2},v_{3},v_{4}\} . The triangle T_{123} has double sign \alpha\in\{y,z\} . Observe that \sigma(T_{123})+\sigma(T_{234})=\sigma(T_{124})+\sigma(T_{134}) . That is \alpha+x=\sigma(T_{124})+\sigma(T_{134}) . By Lemma 2.3 , K_{4} cannot realize three distinct double signs, so one of T_{124} or T_{134} must have double sign x , contradicting the assumption that \mathcal{B} contains no triangle of double sign x . The same argument applies to y and z . ∎ Definition 2 . We say that three triangles T_{1ab},T_{1bc},T_{1cd}\in\mathcal{B} are consecutive if they share successive edges at the common vertex v_{1} , that is, T_{1ab} and T_{1bc} share the edge v_{1}v_{b} , and T_{1bc} and T_{1cd} share the edge v_{1}v_{c} , with a,b,c,d distinct. Lemma 2.5 . If \Sigma_{n} contains only three distinct double signs among all triangles, then \Sigma_{n} contains all possible double signs of Hamiltonian circles. Proof. By Lemma 2.4 , \mathcal{B} contains all three distinct double signs among its triangles. We consider two cases. Case 1. Suppose there exist three consecutive triangles in \mathcal{B} with distinct double signs x,y,z\in\mathbb{F}_{2}^{2} ; Without loss of generality, label their five vertices v_{1},v_{2},v_{3},v_{4},v_{5} as in the figure 1 . x y z v_{1} v_{2} v_{3} v_{4} v_{5} Figure 1. Normalize at v_{5} . Then the edge v_{1}v_{4} has double sign z . There are exactly two isomorphism types of assignments for the induced subgraph K_{4} on \{v_{1},v_{2},v_{3},v_{4}\} , where distinct r,t\in\{x,y\} , as follows : v_{1} v_{2} v_{3} v_{4} r t z z t z v_{1} v_{2} v_{3} v_{4} y z z z x z Figure 2. To show that there are exactly two isomorphism classes of assignments, we distinguish two cases. Observe that \sigma(v_{1}v_{4})=z and \sigma(T_{134})=y , so \sigma(v_{1}v_{3})+\sigma(v_{3}v_{4})+z=y . Since each

Read the complete text