Natural Isomorphism Classes of Cycle Permutation Graphs Over a Graph

 A permutation graph over a graph was introduced by Lee and Sohn in [8] as a generalization of both a graph bundle over a graph and a standard permutation graph, and they gave a characterization of a natural isomorphism and an automorphism of a given permutation graph over a graph. In this paper, we enumerate the natural isomorphism classes of cycle permutation graphs over a graph. Received: October 21, 1996 Revised: August 25, 1997     

Concept of a vertex in a matroid and 3-connected graphs

The concept of a matroid vertex is introduced. The vertices of a matroid of a 3-connected graph are in one-to-one correspondence with vertices of the graph. Thence directly follows Whitney's theorem that cyclic isomorphism of 3-connected graphs implies isomorphism. The concept of a vertex of a matroid leads to an equally simple proof of Whitney's theorem on the unique embedding of a 3-connected planar graph in the sphere. It also leads to a number of new facts about 3-connected graphs. Thus, consideration of a vertex in a matroid that is the dual of the matroid of a graph leads to a natural concept of a nonseparating cycle of a graph. Whitney's theorem on cyclic isomorphism can be strengthened (even if the nonseparating cycles of a graph are considered, the theorem is found to work) and a new criterion for planarity of 3-connected graphs is obtained (in terms of nonseparating cycles).     

A non-factorial algorithm for canonical numbering of a graph

A graph certificate or canonical form is a short unique (up to isomorphism) representation of the graph. Thus two graphs are isomorphic iff their certificates are identical. In this paper an O(cⁿ) graph isomorphism algorithm which also yields a certificate of the graph is presented. The certificate produced by this algorithm is a canonical numbering of the vertices of the graph.     

Enumeration of weak isomorphism classes of signed graphs

A signed graph is a graph in which each line has a plus or minus sign. Two signed graphs are said to be weakly isomorphic if their underlying graphs are isomorphic through a mapping under which signs of cycles are preserved, the sign of a cycle being the product of the signs of its lines. Some enumeration problems implied by such a definition, including the problem of self-dual configurations, are solved here for complete signed graphs by methods of linear algebra over the two-element field. It is also shown that weak isomorphism classes of complete signed graphs are equal in number to other configurations: unlabeled even graphs, two-graphs and switching classes.     

Gray code for permutations with a fixed number of cycles

We give the first Gray code for the set of n-length permutations with a given number of cycles. In this code, each permutation is transformed into its successor by a product with a cycle of length three, which is optimal. If we represent each permutation by its transposition array then the obtained list still remains a Gray code and this allows us to construct a constant amortized time (CAT) algorithm for generating these codes. Also, Gray code and generating algorithm for n-length permutations with fixed number of left-to-right minima are discussed.     

Asymptotics of the moments of the number of cycles of a random A-permutation

We consider random permutations uniformly distributed on the set of all permutations of degree n whose cycle lengths belong to a fixed set A (the so-called A-permutations). In the present paper, we establish an asymptotics of the moments of the total number of cycles and of the number of cycles of given length of this random permutation as n → ∞.     

Isomorphisms of finite semi-Cayley graphs

Let G be a finite group. A Cayley graph over G is a simple graph whose automorphism group has a regular subgroup isomorphic to G. A Cayley graph is called a CI-graph(Cayley isomorphism) if its isomorphic images are induced by automorphisms of G. A well-known result of Babai states that a Cayley graph Γ of G is a CI-graph if and only if all regular subgroups of Aut(Γ) isomorphic to G are conjugate in Aut(Γ). A semi-Cayley graph(also called bi-Cayley graph by some authors) over G is a simple graph whose automorphism group has a semiregular subgroup isomorphic to G with two orbits(of equal size). In this paper, we introduce the concept of SCI-graph(semi-Cayley isomorphism)and prove a Babai type theorem for semi-Cayley graphs. We prove that every semi-Cayley graph of a finite group G is an SCI-graph if and only if G is cyclic of order 3. Also, we study the isomorphism problem of a special class of semi-Cayley graphs.     

Hamilton cycle rich two‐factorizations of complete graphs

For all integers n ≥ 5, it is shown that the graph obtained from the n‐cycle by joining vertices at distance 2 has a 2‐factorization is which one 2‐factor is a Hamilton cycle, and the other is isomorphic to any given 2‐regular graph of order n. This result is used to prove several results on 2‐factorizations of the complete graph K_n of order n. For example, it is shown that for all odd n ≥ 11, K_n has a 2‐factorization in which three of the 2‐factors are isomorphic to any three given 2‐regular graphs of order n, and the remaining 2‐factors are Hamilton cycles. For any two given 2‐regular graphs of even order n, the corresponding result is proved for the graph K_n ‐ I obtained from the complete graph by removing the edges of a 1‐factor. © 2004 Wiley Periodicals, Inc.     

On the complexity of crossings in permutations

We investigate crossing minimization problems for a set of permutations, where a crossing expresses a disarrangement between elements. The goal is a common permutation π^∗ which minimizes the number of crossings. In voting and social science theory this is known as the Kemeny optimal aggregation problem minimizing the Kendall-τ distance. This rank aggregation problem can be phrased as a one-sided two-layer crossing minimization problem for a series of bipartite graphs or for an edge coloured bipartite graph, where crossings are counted only for monochromatic edges. We contribute the max version of the crossing minimization problem, which attempts to minimize the discrimination against any permutation. As our results, we correct the construction from [C. Dwork, R. Kumar, M. Noar, D. Sivakumar, Rank aggregation methods for the Web, Proc. WWW10 (2001) 613-622] and prove the NP-hardness of the common crossing minimization problem for k=4 permutations. Then we establish a 2−2/k-approximation, improving the previous factor of 2. The max version is shown NP-hard for every k≥4, and there is a 2-approximation. Both approximations are optimal, if the common permutation is selected from the given ones. For two permutations crossing minimization is solved by inspecting the drawings, whereas it remains open for three permutations.     

Homogeneoys graphs

Let Γ be a finite graph with vertex set VΓ, and let U, V be arbitrary subsets of VΓ. Γ is homogeneoys (resp. ultrahomogeneous) if whenever the induced subgraphs 〈U〉, 〈V〉 are isomorphic, some isomorphism (resp. every isomorphism) of 〈U〉 onto 〈V〉 extends to an automorphism of Γ. We extend a theorem of Sheehan on ultrahomogeneous graphs to the homogeneous case, and complete his classification of ultrahomogenous graphs.     

Sorting with networks of data structures

We consider the problem of sorting a permutation using a network of data structures as introduced by Knuth and Tarjan. In general the model as considered previously was restricted to networks that are directed acyclic graphs (DAGs) of stacks and/or queues. In this paper we study the question of which are the smallest general graphs that can sort an arbitrary permutation and what is their efficiency. We show that certain two-node graphs can sort in time Θ(n²) and no simpler graph can sort all permutations. We then show that certain three-node graphs sort in time Ω(n^3/2), and that there exist graphs of k nodes which can sort in time Θ(nlog_kn), which is optimal.     

Some remarks on permutation designs

A definition of isomorphism of two permutation designs is proposed, which differs from the definition in Bandt [J. Combinatorial Theory Ser. A21 (1976), 384–392]. The proposed definition has the (generally required) property that the allowed permutations always transform a permutation design into a permutation design. It is shown that the n permutation designs coming from the partitioning of S_n into permutation designs, as constructed in Bandt [J. Combinatorial Theory Ser. A21 (1976), 384–392] are all isomorphic. Further we find that this modified definition does not increase the number of nonisomorphic (6, 4) permutation designs. The same investigation showed that one of the designs, claimed to be a (6, 4) permutation design in [J. Combinatorial Theory Ser. A21 (1976), 384–392], is actually not a (6, 4) permutation design.     

The Topology of Algebra: Combinatorics of Squaring

We study the graph each of whose edges connects an element of a given ring with the square of itself. For a finite commutative group (e.g., for the multiplicative group of coprime residue classes modulo a positive integer), we describe this graph explicitly: each of its connected components is an oriented attracting cycle equipped with identical -vertex rooted trees of special form whose roots reside on the cycle. We also compute the graphs of permutation groups on not too many elements and of the subgroups of even permutations; the connected components of these graphs are also uniformly equipped cycles.     

On cycle permutation graphs

Permutation graphs were first introduced by Chartrand and Harary in 1967 [5]. The purpose of this paper is to study some properties of cycle permutation graphs. A determination of some of their crossing numbers, in keeping with the topological nature of the Chartrand and Harary paper is followed by the determination of all permutations yielding certain isomorphic permutation graphs, extending the algebraic results for planar graphs obtained by those authors.     

A non-Abelian analogue of Whitney’s 2-isomorphism theorem

We give a non-Abelian analogue of Whitney’s 2-isomorphism theorem for graphs. Whitney’s theorem states that the cycle space determines a graph up to 2-isomorphism. Instead of considering the cycle space of a graph which is an Abelian object, we consider a mildly non-Abelian object, the 2-truncation of the group algebra of the fundamental group of the graph considered as a subalgebra of the 2-truncation of the group algebra of the free group on the edges. The analogue of Whitney’s theorem is that this is a complete invariant of 2-edge connected graphs: let G, G′ be 2-edge connected finite graphs; if there is a bijective correspondence between the edges of G and G′ that induces equality on the 2-truncations of the group algebras of the fundamental groups, then G and G′ are isomorphic.     

Sliding puzzles and rotating puzzles on graphs

Sliding puzzles on graphs are generalizations of the Fifteen Puzzle. Wilson has shown that the sliding puzzle on a 2-connected graph always generates all even permutations of the tiles on the vertices of the graph, unless the graph is isomorphic to a cycle or the graph θ₀ [R.M. Wilson, Graph puzzles, homotopy, and the alternating group, J. Combin. Theory Ser. B 16 (1974) 86–96]. In a rotating puzzle on a graph, tiles are allowed to be rotated on some of the cycles of the graph. It was shown by Scherphuis that all even permutations of the tiles are also obtainable for the rotating puzzle on a 2-edge-connected graph, except for a few cases. In this paper, Scherphuis’ Theorem is generalized to every connected graph, and Wilson’s Theorem is derived from the generalized Scherphuis’ Theorem, which will give a uniform treatise for these two families of puzzles and reveal the structural relation of the graphs of the two puzzles.     

An algorithm for constructing star-shaped drawings of plane graphs

A straight-line planar drawing of a plane graph is called a convex drawing if every facial cycle is drawn as a convex polygon. Convex drawings of graphs is a well-established aesthetic in graph drawing, however not all planar graphs admit a convex drawing. Tutte [W.T. Tutte, Convex representations of graphs, Proc. of London Math. Soc. 10 (3) (1960) 304–320] showed that every triconnected plane graph admits a convex drawing for any given boundary drawn as a convex polygon. Thomassen [C. Thomassen, Plane representations of graphs, in: Progress in Graph Theory, Academic Press, 1984, pp. 43–69] gave a necessary and sufficient condition for a biconnected plane graph with a prescribed convex boundary to have a convex drawing.In this paper, we initiate a new notion of star-shaped drawing of a plane graph as a straight-line planar drawing such that each inner facial cycle is drawn as a star-shaped polygon, and the outer facial cycle is drawn as a convex polygon. A star-shaped drawing is a natural extension of a convex drawing, and a new aesthetic criteria for drawing planar graphs in a convex way as much as possible. We give a sufficient condition for a given set A of corners of a plane graph to admit a star-shaped drawing whose concave corners are given by the corners in A, and present a linear time algorithm for constructing such a star-shaped drawing.     

Classification of some metric automorphisms defined by Standish

Let F be a finite set with a probability distribution {P_i: i?F} and (Ω $\text{F}$, P) denote the product space of countably many copies of (F, P). A permutation (bijection) φ of the integers induces an invertible measure preserving transformation T_φ on (Ω $\text{F}$, P) given by the equation (T_φw)_i = w_φ(j). Such metric automorphisms we call S-automorphisms.We show in this paper that S-automorphisms are ergodic if and only they are Bernoulli shifts and two ergodic S-automorphisms are isomorphic if and only if their associated permutations are conjugate.We also show that S-automorphisms have discrete spectrum if and only if they have zero entropy and every S-automorphism is either a Bernoulli shift, has discrete spectrum, or is a product of a Bernoulli shift and an automorphism with discrete spectrum.S-automorphism with discrete spectrum are those whose associated permutations contain only cycles of finite length. These automorphisms are studied according to the number of such finite cycles. Those whose permutations have infinitely many finite cycles with unbounded lengths are shown to be antiperiodic and those whose permutations have infinitely many finite cycles of bounded length are periodic with almost no fixed points. An example is given of two automorphisms of this latter type which are isomorphic but whose permutations are not conjugate.A complete isomorphism invariant is given for S-automorphisms whose associated permutations consist of finitely many finite cycles. Using this invariant we show that if φ is either a product of k disjoint cycles of prime power p^α, or a single cycle of length pq where p and q are primes, or a product of k disjoint cycles of prime lengths p₁ < p₂ < ··· < p_kand if ψ is a permutation such that T_ψand T_φ are isomorphic then ψ is conjugate to φ.     

A graph isomorphism algorithm using pseudoinverses

For a graph ofm nodes andn edges, an algorithm for testing the isomorphism of graphs is given. The complexity of the algorithm is a maximum ofO(mn ²) in almost all cases, with a considerable reduction if sparsity is exploited. If isomorphism is present, the pseudoinverses of the Laplace matrices of the graphs will be row and column permutations of each other. Advantage can be taken of certain features of the incidence matrices or of properties of the graphs to reduce computation time.     

Generalized petersen graphs which are cycle permutation graphs

A cycle permutation graph is obtained by taking two n-cycles each labeled 1, 2,…, n, along with the edges obtained by joining i in the first copy to α(i) in the second, where α ∈ S_n. A characterization of the intersection between cycle permutation graphs and the generalized Petersen graphs as defined by Watkins (J. Combin. Theory6 (1969), 152–164), is given.