Electronic Journal of Graph Theory and Applications 14 .
, 83Ae98 Graph-theoretic properties of inversiontranspositions Atsuko KatanagaO,a .
Takahiro Shiratamab Faculty of Education.
Iwate University, 18-33.
Ueda 3-chome.
Morioka, 020-8550.
Iwate.
Japan b Prime Co.
, 2-10-7 Suido.
Bunkyo-ku.
Excel Building 3F.
Tokyo.
Japan katanaga@iwate-u.
O corresponding author Abstract Dynes established the connection between labeled trees in Graph Theory and factorizations of cyclic permutations by means of transpositions.
In this paper, we introduce the notion of an inversion-transposition, which has both the properties of an inversion and a transposition.
For a cyclic permutation, we define the graph associated with each minimal representation using only inversion-transpositions and consider the properties.
P The main result is that a spanning tree T reconstructs the original permutation if and only if vOOV dT .
) = 2.
Oe .
, which provides a precise reconstruction criterion.
Keywords: graph theory, inversion, transposition, permutation Mathematics Subject Classification : 05C50, 05A05 DOI: 10.
5614/ejgta.
Introduction Around 1900.
Hurwitz posed the problem of counting the number of representations of a given permutation of degree n as the product of w transpositions .
Dynes .
in 1959 showed that the number of representations of a given cyclic permutation of degree n by means of the product of a minimal number of transpositions is equal to the number of trees with n labeled These trees associated with transpositions are called labeled graphs and have been studied by Eden and Schytzenberger .
Moszkowski .
Tujie and Uchiumi .
, among others.
Received: 23 August 2025.
Revised: 10 January 2026.
Accepted: 18 January 2026.
Graph-theoretic properties of inversion-transpositions Katanaga and T.
Shiratama In this paper, we introduce a new notion "inversion-transposition" which has both the properties of an inversion and a transposition, and geometrize this notion as a graph.
Since the associated graph of inversion-transpositions can be regarded as a labeled graph, we can study their graphtheoretic properties.
An advantage of geometrizing permutations is that the inverse permutation can be easily identified as the graph of the linear symmetry with the graph of the original permutation.
Additionally, the signature of a permutation can be obtained geometrically without calculating the inversion number.
We consider the edge ordering of a labeled graph in Graph Theory, and show that the edge ordering has a partial ordering.
Moreover, this partial ordering becomes a well-ordering.
Therefore, any permutation can be reconstructed by the edge ordering.
The novelty of this research lies in two main contributions.
First, the new concept of inversionAetranspositions is introduced and criteria for determining the reconstructibility of permutations is provided.
Second, the classical results of Dynes on transpositions are reinterpreted within the framework of inversionAetranspositions by considering additional geometric and order-theoretic The contents of this paper are as follows: In Section 2, we express a permutation E as an associated graph LnE on the first quadrant in the 2-dimensional Euclidean space for any n.
Then, the number of inversions for a permutation E is shown to be equal to the number of right-ascending lines on the graph.
In Section 3, we review the known facts in Graph Theory and introduce the edge ordering for a labeled graph, which was also studied in .
Then, we show that the edge ordering has a partial ordering.
In Section 4, we introduce the new notion "inversion-transposition", a transposition with the property of an inversion.
By applying the results obtained in Section 3, we study the graph-theoretic properties of the graph LnE and LCnE , where LCnE is one of minimal graphs of LnE .
Finally, as the main result, we show that the spanning tree associated graph with total distance LCnE can reconstruct the original permutation E OO Sn by the proper edge-ordering as defined in Section 3.
Geometrization Let Sn be the n-th symmetric group on .
= .
, 2, .
, .
The m-th order cyclic permutation is expressed as c = .
1 , i2 , .
, im ), and a transposition is denoted as Ekl or .
, .
For a permutation E OO Sn and i, j OO .
, a pair .
, .
satisfying the conditions i < j and E.
< E.
is called an inversion, and the total number of inversions denotes the inversion number inv(E) := o{.
, .
| i, j OO .
, i < j.
< E.
Then, the signature of a permutation is defined as sgn(E) := (Oe.
inv(E) .
Note that a transposition .
, .
is not necessarily an inversion in general.
In order to geometrize a permutation, we define the graph associated with the permutation on the first quadrant in R2 .
Hereafter, unless specifically noted.
E means an elements of Sn for any n OO N, and we assume that i < j for i, j OO .
Definition 2.
For a set .
, .
, the point cij has the coordinate .
Oe 1, n Oe .
on the first quadrant in R2 .
The slope of the line segment cij ckl linking the two different points cij = .
Oe1, nOe.
and clk = .
Oe 1, n Oe .
is expressed as slope.
ij ckl ).
Theorem 2.
The set .
, .
is the inversion of E if and only if the slope of the line segment ciE.
is positive.
Graph-theoretic properties of inversion-transpositions Katanaga and T.
Shiratama Proof.
Suppose a set .
, .
is the inversion of E.
From i Oe j < 0 and E.
Oe E.
< 0, then iOej iOej slope.
) = > 0.
Conversely, if slope.
) = > 0, we E.
Oe E.
Oe E.
have E.
< E.
from the assumption i < j.
Thus, the set .
, .
is the inversion of E.
Corollary 2.
inv(E) = o.
OC R2 | slope.
) > .
Therefore, the total number of inversions is equal to the total number of right-ascending line segments in R2 , and the signature of a permutation is determined by the total number of rightascending line segments on the first quadrant in R2 .
Here, we define the graph LnE associated with a permutation E below.
Note that LnE is always a simple graph and may contain cycles since a completely decreasing subsequence of length at least three in the permutation gives rise to a cycle in the graph LnE , as in Example 2.
L3E13 .
Definition 2.
LnE := .
OC R2 | slope.
) > .
Example 2.
For a full cyclic permutation E = .
, 3, 2, .
OO S4 , the associated graph L4E is constructed as below:
inv(E) = o{.
, .
, .
, .
, .
, .
, .
, .
, .
, .
} = o.
13 c32 , c24 c32 , c13 c41 , c24 c41 , c32 c41 } = 5.
In fact, the associated graph of any full cyclic permutation is always connected.
L4.
,3,2,.
Example 2.
For the symmetric groups of relatively small degree .
= 2, 3, .
, the associated graphs are composed of paths, stars, and cycles: L4.
,2,4,.
is a path.
L4.
,2,3,.
is a star, and L4E13 E24 is a cycle.
The symbol O denotes an inverse permutation.
If two permutations which are inverse to each other, then the associated graphs are isomorphic.
L2e
L2E12
Graph-theoretic properties of inversion-transpositions L3e
L3E12
L3.
,2,.
L3E13
Katanaga and T.
Shiratama
L3E23
L3.
,3,.
L4E13
L4E24
L4E14 E23
L4e
L4E12
L4E14
L4E34
L4E12 E34
L4E13 E24
L4.
,2,.
L4.
,3,.
L4.
,3,.
L4.
,4,.
L4.
,4,.
L4.
,3,.
L4E23
L4.
,2,.
L4.
,4,.
Graph-theoretic properties of inversion-transpositions L4.
,2,3,.
L4.
,4,3,.
Katanaga and T.
Shiratama L4.
,2,4,.
L4.
,3,2,.
L4.
,3,4,.
L4.
,4,2,.
Labeled Graphs with Edge Orderings In order to study the graph theoretical properties of LnE , we regard LnE as an undirected graph.
First we quickly review the basic and known facts in Graph Theory.
Labeled Graph Let V = .
and E be finite sets and be a map from E to a power set 2V , and : E Ie 2V satisfying |.
| = 1 or |.
| = 2 for an arbitrary element e OO E.
The set (V.
E, ) is called an undirected graph G .
t is just called a graph hereafte.
, and sets V and E are the vertex set and the edge set of G, respectively.
A walk from x0 to xr of a graph G is an alternating sequence of vertices and edges x0 , e1 , x1 , e1 , x2 , .
, xrOe1 , er , xr , in which each edge ei is incident with the two points xiOe1 , xi , and is expressed as x0 x1 A A A xr .
When x0 = xr in G, this walk is called a closed The closed walk is called a cycle if each two vertices excluding x0 = xr are different and any two edges are also different.
It is a trail if all the edges are distinct, and a path if all the points .
nd necessarily all the edge.
are distinct.
A graph G is connected if a path exists between two arbitrary vertices on G.
Furthermore, a connected graph without a cycle is called a tree, and a graph without cycles is called a forest.
A subgraph H of G is a graph consisting of some vertices and edges in G.
Let G1 and G2 be graphs.
A mapping f from V (G1 ) to V (G2 ) is a homomorphism if f .
and f .
are adjacent in G2 when i and j are adjacent in G1 .
Two graphs G1 and G2 are isomorphic .
ritten G1 O = G2 ) if there exists a one-to-one correspondence between their vertices sets which preserve adjacency.
The following results are known in Graph Theory.
Proposition 3.
1 (Harary .
The following are the equivalent for a graph G with n vertices:
G is a tree.
Every two points of G are joined by a unique path.
G is connected and has n Oe 1 edges.
Definition 3.
A graph G = (V.
E, ) is called a labeled graph if each edge eij in E with .
ij ) = .
, .
corresponds to the transposition Eeij = Eij OO Sn .
The vertices of a labeled graph are called the labeled vertices.
Dynes connected Linear Algebra and Graph Theory, and Moszkowski gave the exact bijection between them as follows:
Graph-theoretic properties of inversion-transpositions Katanaga and T.
Shiratama Theorem 3.
3 (Dynes .
Moszkowski .
The number of representations of a given cyclic permutation of degree n by means of a product of a minimal number of transpositions is equal to the number of trees with n labeled vertices.
Remark 3.
Eden and Schytzenberger .
obtained the number of associated cyclic permutations under the sorted equivalence for a given tree .
Theorem 3.
Edge Orderings In set theory, it follows from the axiom of choice that every set can be well-ordered.
Therefore, we can define a well-ordering for a labeled graph.
Let G be a graph and O := .
1 , e2 , .
, em ), where ei is an edge of G for 1 O i O m.
Definition 3.
An edge ordering O of a graph G is a linear order OO on the edge set E such that ei OO ej for i O j.
Definition 3.
Fn := {(G.
OO ) | G is a forest with n vertices.
OO is an edge ordering of G}.
Definition 3.
For any E OO Sn , we define the labeled forest set Fn (E) := {(G.
OO ) OO Fn | Eem A A A Ee2 Ee1 = E}, where Eej is the transposition related to the edge ej .
Theorem 3.
We introduce a partial ordering among the edges of (G.
OO ) in Fn (E), and show that E can be reconstructed by composing the transpositions according to the induced ordering.
Let E be a permutation Sn and E = cm A A A c2 c1 be the cycle decomposition of E.
For any k in (E) .
and i, j OO Supp.
k ) .
ee, the definition of the support belo.
, we define the distance di .
from i to j as follows:
(E)
Definition 3.
:= min.
OO N | j = E r .
The order between two edges eij1 and eij2 sharing a common vertex i is defined by using the (E) above distance di as follows:
(E)
(E)
Definition 3.
eij1 OE eij2 is defined by di .
1 ) O di .
2 ).
For two edges that do not share a vertex, the order is defined by requiring that the order between adjacent edges be preserved at each vertex along the path containing them.
Let i0 i1 A A A ir be a path on (G.
OO ) in Fn (E).
(E)
(E)
Definition 3.
ei0 i1 OE eirOe1 ir is defined by dis 1 .
s ) O dis 1 .
s 2 ), .
O s O r Oe .
Since the graph is a forest, the path connecting the two edges is unique.
Therefore, the order, whenever it exists, is uniquely determined.
Lemma 3.
The order OE is a partial ordering on the set of all edges of (G.
OO ) in Fn (E).
Graph-theoretic properties of inversion-transpositions Katanaga and T.
Shiratama Proof.
It is clear from the definition of the order that the reflection and transition rules hold.
Note that eij OE ekl and ekl OE eij .
The anti-symmetry law also holds since there exists only one path connecting any two vertices i and l in G by .
Let ei and ej be in E with i < j.
A set (G.
OE ) is a well-ordered set if and only if ej O ei is not satisfied.
Note that there are non-comparable parts in the well-ordered set.
multiple wellorderings are possible.
The well-ordering of (G.
OE ) can be regarded as the total-ordering.
If the elements of (G.
OE ) are well-ordered, they are sorted as e1 , e2 , .
, em and this can be expressed as OE = .
1 , e2 , .
, em ).
We show that E can be reconstructed by following the well-ordering (G.
OE ).
First, we prepare Theorem 3.
Any permutation E OO Sn is expressed as the product E1 E2 A A A Er of transpositions E1 .
E2 , .
Er , where the transposition product is taken from right to left of E1 E2 A A A Er .
The minimum value of the total number of transpositions denotes PE .
The length r cyclic permutation has a minimal transposition representation with PE = r Oe 1.
Let E = .
1 , i2 , .
, ir ) be a cyclic permutation and denote the support of E.
Supp(E) := .
1 , i2 , .
, ir }.
Two cyclic permutations are prime to each other if their supports share no common parts.
The decomposition into the product of the prime cyclic permutations is called Pr a cycle decomposition.
For the cycle decomposition E = cr A A A c2 c1 of a permutation E.
PE = i=1 Pci .
Lemma 3.
Let E be a transposition in the product of a minimal number of transpositions of a permutation E.
Then there exists only one cyclic permutation c that appears in the cycle decomposition such that Supp(E ) OC Supp.
Proof.
Let E = cr A A A c2 c1 be the cycle decomposition for a permutation E OO Sn .
Let E = Em A A A E2 E1 be the minimum transposition representation.
Then PE = m.
0 = PEOe1 E = PE1 E2 aEm cr .
ac2 c1 If Supp(Em ) O Supp.
r ) = OI, exchange Em and cr .
Then, there exists a cyclic permutation ck such that Supp(Em ) O Supp.
k ) = OI.
When Supp(Em ) OC Supp.
k ), 0 = PE1 E2 aEmOe1 cr = aEm ck ac2 c1 PE1 E2 aEmOe1 cr ack ac2 c1 Oe 1 since PEm ck = Pck Oe 1.
When Supp(Em ) OO Supp.
k ), 0 = PE1 E2 aEmOe1 cr = aEm ck ac2 c1 PE1 E2 aEmOe1 cr ack ac2 c1 1 since PEm ck = Pck 1.
The same operation is applied to each Ei .
Let p be the number of the transpositions Ei with Supp(Ei ) OC Supp.
k ), and q be the number of the transpositions Ei with Supp(Ei ) OO Supp.
k ).
It follows from 0 = PE Oe p q and P 0 O p, q O PE .
On the other hand, forPthe cycle decomposition E = cr A A A cP Oe i=1 Pci q is obtained since PE = i=1 Pci .
From PE Oe p q O PE Oe i=1 Pci q, we obtain ri=1 Pci O p.
Thus, it follows from p O PE that p = PE and q = 0.
Lemma 3.
Let E = El A A A E2 E1 be the minimal transposition representation for any permutation (E) (E) E OO Sn and let Es = Eij and Et = Eik for 1 O s, t O l.
Then, s < t if and only if di .
< di .
(E)
(E)
Proof.
(Necessit.
First, we show that if s < t, then di .
< di .
From Theorem 3.
12, it is sufficient to show the case of the minimal transposition representation for a cyclic permutation.
Hereafter, let E OO Sn be a cyclic permutation.
Assume that E = El A A A Et A A A Es A A A E1 is the minimal transposition representation.
The products from E1 to EtOe1 are decomposed into prime cyclic permutations, this is set to EtOe1 A A A Es A A A E1 = cm A A A c2 c1 , where, without losing generality, cm can be a cyclic permutation cm = .
, i1 , .
, j, .
Graph-theoretic properties of inversion-transpositions Katanaga and T.
Shiratama ir ), .
Ou .
including i, j.
Then.
Et cm = Eik .
, i1 , .
, j, .
, ir ) = .
, i1 , .
, j, .
, ir , .
Hence, (E c ) (E c ) di t m .
< di t m .
For Et cm , it is shown that multiplying cp .
O p < .
from the right side of Et cm or Eq .
< q O .
from the left side of Et cm does not change the relationship in terms of the distance from i to k and j in the product.
First, we show that even if we multiply cp .
O p < .
from the right side, the distance does not change.
For the case where c1 , .
, cm are all primes, the common part of cp and Et cm is just Let cp = .
, j1 , j2 , .
, jrp ) and Et cm = .
, i1 , i2 , .
, j, .
, ir , .
, respectively.
This product (E c c ) (E c c ) Et cm cp = .
, i1 , i2 , .
, j, .
, ir , j1 , j2 , .
, jrp , .
It follows from di t m p .
< di t m p .
that (E c ac ac ) (E c ac ac ) di t m p 1 .
< di t m p 1 .
Next, we show that, even if we multiply Et cm A A A cp A A A c1 with Eq , .
< q O .
from the left side, the distance does not change.
The case when the relative distances may change is multiplication Ejk from the left side.
However, three transpositions Eij .
Eik , and Ejk make a cycle, this is contradictory (E) to the assumption that E = El A A A Et A A A Es A A A E1 is a cyclic permutation.
Therefore, di .
< (E) di .
(Sufficienc.
The sufficient condition can be shown in the similar way.
Reconstruction It follows from Theorem 3.
13 that we can reconstruct any permutation E in Sn by a wellordering of (G.
OE ).
Theorem 3.
Let (G.
OO ) OO Fn (E) be a labeled graph.
Then the edge ordering O = .
1 , e2 , .
em ) is a well-ordering of (G.
OE ).
Proof.
From Theorem 3.
12, the transpositions in the minimum transposition representation belong to the support of one cyclic permutation in the cycle decomposition.
Therefore, transpositions belonging to the supports of different cycles in (G.
OE ) cannot be compared: it does not become ej OE ei for i < j.
It is sufficient to show that the sub-sequence comprising the edges corresponding to the minimum transposition representation of each cyclic permutation is well-ordered.
Let the minimum transposition representation of cyclic permutation c appearing in the cycle decomposition of E be c = Eir A A A Ei2 Ei1 .
O i1 < i2 < A A A < ir O .
Let the edge corresponding to each transposition Ei be ei OO (G.
OE ).
Assume that, for 1 O p < q O ir , there exists eq OE ep .
From this assumption and the definition of partial ordering OE , we can take a sequence of line segments ep0 =q O ep1 O A A A O epr =p such that adjacent edges have a common point.
It follows from Theorem 3.
13 that there is ps < ps 1 for an arbitrary 0 O s O r Oe 1.
Hence, we have q < p, which is a contradiction.
The minimal transposition representation c = Eir .
Ei2 Ei1 gives the well-ordering of the corresponding edge sequence .
i1 , ei2 , .
, eir ).
For a permutation E OO Sn , let Em A A A E2 E1 and Em A A A E2A E1A be two minimal transposition representations of E.
Definition 3.
The sorted equivalence Em A A A E2 E1 O Em A A A E2A E1A means that these two representations coincide by mutually sorting the transpositions.
Graph-theoretic properties of inversion-transpositions Katanaga and T.
Shiratama Theorem 3.
Let (G.
OO ) OO Fn (E) be a labeled graph and .
A1 , eA2 .
A A A , eAm ) be a well-ordering A A A A E2A E1A , where is the edge corresponding to each transposition of (G.
OE ).
Then Em A A A E2 E1 O Em Ei be ei OO (G.
OO ) and Ei be ei OO (G.
OE ).
Proof.
Two edges which cannot be compared on (G.
OE ) do not have a common vertex from the definition of partially ordering OE .
Therefore, the corresponding transpositions are prime to each A A A A E2A E1A .
From the definition of the equivalence, we obtain Em A A A E2 E1 O Em Application Minimal labeled graphs of LnE In this section, we treat LnE as a graph by disregarding the coordinates from A2, i.
, the point ciE.
in the graph LnE as the vertex i and the line segment ciE.
as the edge eij = .
, .
Furthermore, the edge eij corresponds to the inversion-transposition .
, .
from the definition of LnE .
From Theorem 3.
12, it is enough to only consider the cyclic permutations.
For this graph, we apply the edge ordering introduced in A3.
In general.
LnE has a cycle.
There the ordering OE is the pseudo-order, where the pseudo-order means that the partial ordering in which anti-symmetry is not satisfied.
We introduce a new notion "inversion-transposition".
Let .
, .
be a transposition for k, l OO .
= .
, 2, .
, .
Definition 4.
A transposition .
, .
is called an inversion-transposition .
, .
, .
is an inversion.
This restriction to inversions is natural since inversion-transpositions correspond exactly to edges of LnE and preserve the geometric structure of the graph.
Since there is no unique minimum inversion-transposition representation for a permutation E OO Sn , we must specify one minimal representation in order to define one of a minimal graph.
Definition 4.
Let E OO Sn be a permutation.
Specify one minimal inversion-transpositionAos representation as E = Em A A A E2 E1 , where m is the minimal number of inversion-transpositions of E.
The minimal inversion-transposition graph LCnE=Em aE2 E1 is defined as the labeled graph in which each edge corresponds to an inversion-transposition.
We denote {LCnE } as the set of minimal inversiontransposition graphs for a permutation E OO Sn .
Therefore, the cardinality of {LCnE } is equal to the number of the minimal inversion-transpositionAos representations for E.
In general, it is known that the permutation of an inversion number l is represented by the products of l transpositions.
For the existence of LCnE=Em aE2 E1 , we show that any permutation is expressed by only inversion-transpositions.
Theorem 4.
An arbitrary permutation E OO Sn can be expressed by a product of a minimal number of inversion-transpositions.
Graph-theoretic properties of inversion-transpositions Katanaga and T.
Shiratama Proof.
Any permutation E can be decomposed into the product of the prime cyclic permutations.
Therefore, it is enough to consider the case of prime cyclic permutations.
The proof proceeds by iteratively extracting inversion-transpositions corresponding to maximal elements, thereby reducing the cyclic permutation length step by step.
Let c = .
1 , i2 , .
, ir ) be a prime cyclic permutation.
Step 1.
Let c be reordered so that the rightmost element of c is the largest element: c = .
1 , i2 , .
, im ), where im := max.
1 , i2 , .
, im }.
Step 2.
For this im , take out the elements which are inversions in order, and if an element which is not an inversion appears, back to Step1: for this im , .
m , imOe1 ) is always an inversion since im is the largest element.
Then we have c = .
1 , i2 , .
, imOe1 ).
mOe1 , im ], where .
mOe1 , im ] is an inversion-transposition.
Next, check whether .
k , im ), .
O k O m Oe .
is an inversion of c.
Let is1 be the last element to be an inversion for im .
there exists s1 OO .
, .
, m Oe .
such that .
s1 , im ] is an inversion, but .
s1 Oe1 , im ) is not an inversion.
Then, we have c = .
1 , i2 , .
, is1 ).
mOe1 , im ].
mOe2 , im ] A A A .
s1 , im ].
Let cs1 := .
1 , i2 , .
, is1 ).
Subsequently, repeat the operation from Step1.
Let cs1 be the A reordered cyclic permutation of cs1 such that the largest element of cs1 is at the right end: cs1 := A A A A A A A A .
1 , i2 , .
, is1 ), where is1 := max.
1 , i2 , .
, is1 }.
Note that is1 = is1 since .
s1 Oe1 , im ) is not an A A A A A A A A .
s1 Oe1 , is1 ) is always an inversion.
is1 Oe1 < is1 since is1 := max.
1 , i2 , .
, is1 }.
In the A A case of s1 = 1, we have c.
s1 Oe1 ) = c.
s1 ) = is1 1 and c.
s1 ) = c.
1 ) = i2 .
Since .
s1 , im ] is A A an inversion, is1 1 = c.
s1 ) > c.
m ) = i1 > i2 .
In case of s1 = 1, we have c.
s1 Oe1 ) = is1 and A A A A A A A A A A s1 ) = i1 .
Therefore, c.
s1 Oe1 ) = is1 > i1 = c.
s1 ) since is1 := max.
1 , i2 , .
, is1 }.
The operation is continued until an element which is not an inversion appears.
Let is2 be the last element that becomes an inversion for is1 .
Then, c = .
1 , i2 , .
, is2 ).
s1 Oe1 , is1 ].
s1 Oe2 , is1 ] A A A .
s2 , is1 ]A .
mOe1 , im ].
mOe2 , im ] A A A .
s1 , im ].
The operation ends with a finite number since the number of sl .
O l O .
is finite.
Minimality is obvious since the elements are removed one by one.
Example 4.
A graph of {LCnE } is determined only by inversion-transpositions, rather than by the order of the composition of them.
Additionally, for a permutation, its graph may be different according to the minimum inversion-transpositionAos representation: E = .
, 3, 2, .
OO S4 .
LCnE=E24 E34 E14 becomes a star graph sharing one point, and LCnE=E14 E13 E23 becomes a path.
These examples demonstrate the non-uniqueness of minimal inversion-transposition graphs and the structural diversity of such realizations.
LCnE=E24 E34 E14 LCnE=E14 E13 E23 Example 4.
Consider E OO Sn for n = 2, 3 and 4.
Under sorted equivalence, the cardinality of {LCnE } is 1 for n = 2, 5 for n = 3, and 37 for n = 4.
The case in which the element of {LCnE } differs Graph-theoretic properties of inversion-transpositions Katanaga and T.
Shiratama from LnE are shown as below.
Here.
O represents a reverse inversion relationship.
LC3E13
LC4E13
LC4E14
LC4E24
LC4E13 E24
LC4E14 E23
LC4.
,3,.
LC4.
,4,.
LC4.
,2,.
LC4.
,4,.
Let E = .
, 3, 2, .
, and the set {LC4E } is as follows:
LC4E=E13 E24 E34
LC4E=E34 E14 E23
LC4E=E13 E23 E24
LC4E=E14 E13 E23
LC4E=E23 E24 E14
LC4E=E24 E14 E13
LC4E=E13 E34 E23
LC4E=E24 E34 E14
Let E = .
, 4, 2, .
, and the set {LC4E } is as follows:
LC4E=E13 E24 E12
LC4E=E12 E14 E23
LC4E=E24 E23 E13
LC4E=E14 E24 E23
LC4E=E23 E13 E14
LC4E=E13 E14 E24
LC4E=E24 E12 E23
LC4E=E13 E12 E14
Remark 4.
Let E be a n (Ou .
degree cyclic permutation.
Under sorted equivalence, the cardinality of {LCnE } is 192 if n = 5, the cardinality is 3, 180 if n = 6, and the cardinality is 58, 986 if Graph-theoretic properties of inversion-transpositions Katanaga and T.
Shiratama n = 7.
The connected labeled graph can be one of 3 types: paths, stars, and the composition of paths and stars.
Reconstructions by edge orderings of LCnE We apply the method developed in A3 in order to reconstruct the cyclic permutation from a given graph since LCnE=AO is the element of Fn (E) from the definition.
Lemma 4.
The order OE is a partial ordering on the set of all edges of LCnE .
The set comprising all the edges with semi-order in LCnE=AO is expressed as (LCnE=AO .
OE ) = .
1 , e2 , .
, em }.
Let i, j OO (LCnE .
O) with i < j.
If they are sorted so that it does not become lj OE li , this sorting is called (LCnE .
O) well-ordering.
As well-ordering allows the replacement of non-comparable parts, it is not necessarily the only one.
When the elements of (LCnE .
OE ) are ordered so that they are sorted as lm .
A A A , l2 , l1 , this can be expressed as lm A A A l2 l1 .
We show that E can be reconstituted by ordering (LCnE .
OE ).
It follows from Theorem 3.
13 that we can reconstruct E by well-ordering of (LCnE .
OE ).
Theorem 4.
Let E = Em A A A E2 E1 be the minimal inversion- transposition representation of E OO Sn .
Let li be the edge of (LCnE=Em aE2 E1 .
OE ) corresponding to the inversion-transposition Ei .
Then .
1 , l2 .
A A A , lm ) is a well-ordering.
Theorem 4.
For E OO Sn , let lm A A A l2 l1 be a well-ordering of (LCnE=Em aE2 E1 .
OE ) and EiA be the A A A A E2A E1A .
inversion-transposition corresponding to each edge li .
Then Em A A A E2 E1 O Em Example 4.
For E = .
, 3, 2, .
OO S4 , consider the following graph LC4E .
Each line segment
(E)
(E)
l13 := c13 c32 , l14 := c13 c41 , l23 := c24 c32 .
From d1 .
= 1 and d1 .
= 3, we obtain l13 OE l14 .
(E)
(E)
From d3 .
= 1 and d3 .
= 3, we obtain l32 OE l31 .
Therefore we can arrange the line segments as l23 OE l13 OE l14 .
The minimal inversion-transposition representation corresponding to this well-ordering is E = E14 E13 E23 .
In fact, the above graph can be obtained from this minimal inversion-transposition representation.
The relation between LnE and LCnE In this section, we compare LnE and LCnE by using the concept of a spanning tree.
A permutation E OO Sn is called a full cyclic permutation if E is a cyclic permutation of length n.
Dynes .
proved that the graph obtained from a full cyclic permutation is tree.
Let G be a graph.
A spannig subgraph is a subgraph containing all points of G.
A spanning subgraph with no cycles is called a spanning forest, and a spanning tree if G is connected.
Graph-theoretic properties of inversion-transpositions Katanaga and T.
Shiratama Remark 4.
In the case of full cyclic permutations for n = 2, 3 and 4, the set of spanning trees of LnE is isomorphic to {LCnE }.
Then, by using the method in Section 4.
2, we can reconstruct the permutation E from one of {LCnE }.
Otherwise, a spanning tree of LnE does not necessarily coincide with one of {LCnE }: the permutation E = E13 E24 for n = 4 since E = E13 E24 is of length 2.
Remark 4.
In the case of n = 5, there exists a spanning tree that we can not reconstruct the permutation E: for E = .
, 3, 4, 2, .
, the graph T on the right side below is one of spanning trees of L5.
,3,4,2,.
, which is not contained in {LC5.
,3,4,2,.
no matter how we take a product of the inversion-transpositions E23 .
E45 .
E25 and E15 corresponding for each edge on T , the permutation E can not be reconstructed.
L5.
,3,4,2,.
From the above Theorem 4.
12, a spanning tree is not enough to reconstruct a given permutation.
In order to obtain the necessary and sufficient conditions of the graph which can reconstruct a full cyclic permutation, we prepare some terminologies in Algebraic Graph Theory following Tsujie and Uchiumi .
, and Mohar and Thomassen .
Let G = (V.
E, ) be a graph.
For a vertex v OO V , let IG .
:= .
OO E | v OO .
} be the set of edges of G incident to a vertex v.
When IG .
:= .
1 , e2 , .
, em }, a cyclic order Av on IG .
is an equivalence class .
1 , .
, em ] of linear orders on IG .
obtained by identifying .
1 , e2 , .
, em ) with its circular shift .
2 , .
, em , e1 ).
A rotation system of G is a collection A := (Av )vOOV consisting of cyclic orders.
We consider the pair (G.
A).
Let DG := {.
, .
OO E y V | e OO IG .
} be a set and the element is called a dart.
A map : DG Ie DG is defined by .
, .
:= .
, .
= .
, .
A map : DG Ie DG is defined by .
i , .
:= (Av .
i ), .
= .
i 1 , .
, where Av = .
1 , .
, em ].
Then, a bijection map : DG Ie DG is defined by := .
We use the same representations as in Section 3.
Given an edge ordering O = .
1 , e2 , .
, em ).
AO := Eem A A A Ee1 .
For a vertex v OO V .
TO .
:= .
i OO E | Eei EeiOe1 A A A Ee2 Ee1 .
= EeiOe1 A A A Ee2 Ee1 .
for i Ou 2.
Ee0 .
= v for i = .
is the subset of E.
When TO .
= .
j1 , .
, ejs }, .
O j1 < A A A < js O .
, we define a trail Ov := .
j1 , .
, ejs ) from v to AO .
When a graph is a tree, any trail becomes a path since there are no cycles in the graph.
A path of length r from x to y in a graph is a sequence of r 1 distinct vertices starting with x and ending with y, such that consecutive vertices are adjacent.
The distance d.
, .
between two vertices u and v in G is the length of the shortest path joining them.
Theorem 4.
Let E OO Sn be a full cyclic permutation and T be a tree.
Then the following are Graph-theoretic properties of inversion-transpositions Katanaga and T.
Shiratama .
There exists an edge order O = .
1 , e2 , .
, enOe1 ) of T such that AO = E.
dT .
) = 2.
Oe .
, where dT .
) is the distance between v and E.
on T .
vOOV Proof.
Ne .
From the assumption .
, let O be the edge ordering of G such that AO = E.
Then, we have dT .
) = dT .
AO .
Moreover, since Ov is a trail on the tree T , dT .
AO .
) is equal to the length of the trail Ov .
Hence, vOOV dT .
) is equal to the total number of edges of trails.
It is enough to show that the total number of edges of trails is 2.
Oe .
The cyclic order AO,v is determined by O on each IG .
for a vertex v OO V .
Let AO := (AO,v )vOOV be a rotation system associated with AO .
Consider this pair (G.
AO ).
Let DG := {.
, .
OO E y V | e OO IG .
} be a set of darts, and the map : DG Ie DG is defined by .
, .
:= .
, .
= .
, .
The map O : DG Ie DG is defined by O .
i , .
:= (AO,v .
i ), .
= .
i 1 , .
, where AO,v = .
1 , .
, em ].
Then, the map O : DG Ie DG is defined by O := O associated with O.
Let the edge fv be the smallest element of IG .
associated with O, and OO .
v , .
:= .
O (.
v , .
) | k OO ZOu0 } be an orbit of O starting from a dart .
v , .
Then, there exists the minimum positive integer k0 satisfying AOk0 .
= v and the set .
AO .
, .
AOk0 Oe1 .
} = .
and k0 = n since E is a full cyclic permutation.
Hence, the orbit OO .
v , .
becomes the connected closed walk connecting the endpoint of OAOqOe1 .
and the starting point of OAOq .
for 0 O q O k0 Oe 1 in order of trails Ov .
OAO .
, .
OAOk0 Oe1 .
Therefore, the length of the orbit OO .
v , .
is equal to the total number of edges of trails, i.
, the cardinal number of DG which is 2.
Oe .
since only one orbit exists and O is bijective.
Therefore, the total number of edges of trails is 2.
Oe .
Next.
We show the contraposition of .
Ne .
Suppose that AO = E for any edge ordering of G.
Then, there exists a vertex v OO V such that AO .
= E.
For this v, the trail Ov does not coincide with the path from v to E.
Hence, the total number of all paths is not equal to 2.
Oe .
This main theorem provides a complete graph-theoretic characterization of when a spanning tree reconstructs a full cyclic permutation.
Note that Theorem 4.
13 is true for transpositions without restricting inversion-transpositions.
By combining Theorem 3.
3 and Theorem 4.
3, the graph-theoretic properties that allow the cyclic permutation to be reconstructed from LCnE are stated in Theorem 4.
Corollary 4.
Let E be a full cyclic permutation of Sn for any n.
The set of spanning trees of LnE satisfying the condition .
of Theorem 4.
13 is isomorphic to the set {LCnE }.
Remark 4.
Let E be a full cyclic permutation of Sn for any n.
The graph that reconstructs E does not necessarily come from LnE or LCnE : for E = .
, 2, 4, .
, the tree T blow does not coincide with L4E = LC4E .
However.
E can be reconstructed with the edge ordering O = .
1 , e2 , e3 ).
Graph-theoretic properties of inversion-transpositions Katanaga and T.
Shiratama Conclusion In this paper, we have introduced inversion-transpositions and have investigated their associated graphs and edge orderings, providing a graph-theoretic reconstruction criterion for full cyclic As a result, we have extended the classical results of Dynes by clarifying how geometric and order-theoretic structures on labeled graphs encode permutation data.
There are two natural directions for future research arising from this work.
First, one may consider extending the framework to the case of non-cyclic permutations.
Second, as mentioned in Theorem 4.
6, the number of elements in the set {LCnE } grows explosively, raising algorithmic problems concerning the enumeration of minimal inversion-transposition graphs.
One possible approach is to investigate connections with the Cayley graphs of the corresponding groups associated with LCnE .
Such a viewpoint may provide a more structural understanding and further deepen the scope of the inversion-transpositions framework.
Acknowledgement The authors wish to thank Professor Yasuhide Numata for his useful contributions in the early stages of this research.
This work has been supported in part by JSPS KAKENHI Grant Number JP23H05437.
References