On natural isomorphisms of cycle permutation graphs

Two problems are approached in this paper. Given a permutation onn elements, which permutations onn elements yield cycle permutation graphs isomorphic to the cycle permutation graph yielded by the given permutation? And, given two cycle permutation graphs, are they isomorphic? Here the author deals only with natural isomorphisms, those isomorphisms which map the outer and inner cycles of one cycle permutation graph to the outer and inner cycles of another cycle permutation graph. A theorem is stated which then allows the construction of the set of permutations which yield cycle permutation graphs isomorphic to a given cycle permutation graph by a natural isomorphism. Another theorem is presented which finds the number of such permutations through the use of groups of symmetry of certain drawings of cycles in the plane. These drawings are also used to determine whether two given cycle permutation graphs are isomorphic by a natural isomorphism. These two methods are then illustrated by using them to solve the first problem, restricted to natural isomorphism, for a certain class of cycle permutation graphs.     

On factorable degree sequences

We call a degree sequence graphic (respectively, k-factorable, connected k-factorable) if there exists a graph (respectively, a graph with a k-factor, a graph with a connected k-factor) with the given degree sequence. In this paper we give a necessary and sufficient condition for a k-factorable sequence to be connected k-factorable when k ? 2. We also prove that every k-factorable sequence is (k − 2) factorable and 2-factorable, and also 1-factorable, when the sequence is of even length. Some conjectures are stated and it is also proved that, if {d_i} and {d_i − k} are graphic, then {d_i − r} is graphic for 0 ≤ r ≤ k provided rn is even.     

关于图的（g，f）－因子分解的一些新结果

本文讨论图的（ｇ，ｆ）－因子分解问题，推广了文［１］关于图的因子分解的理论，改进了文［２］的一些结果，给出了一个图Ｇ是（ｇ，ｆ）－可因子化的若干充分条件．     

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.     

An algebraic theory of graph factorization

An algebraic theory of graph factorization is introduced. For a factor h, a graph G(h) is constructed whose structure contains information about h-factorability. The 1-factorable and cycle factorable graphs over $\text{Z}$₂ are characterized, and properties of the corresponding graph G(h) are obtained.     

The harmonious coloring problem is NP-complete for interval and permutation graphs

In this paper, we prove that the harmonious coloring problem is NP-complete for connected interval and permutation graphs. Given a simple graph G, a harmonious coloring of G is a proper vertex coloring such that each pair of colors appears together on at most one edge. The harmonious chromatic number is the least integer k for which G admits a harmonious coloring with k colors. Extending previous work on the NP-completeness of the harmonious coloring problem when restricted to the class of disconnected graphs which are simultaneously cographs and interval graphs, we prove that the problem is also NP-complete for connected interval and permutation graphs.     

Domination in permutation graphs

O(n³) algorithms to solve the weighted domination and weighted independent domination problems in permutation graphs, and an O(n²) algorithm to solve the cardinality domination problem in permutation graphs are presented.     

An efficient algorithm to find next-to-shortest path on permutation graphs

In this paper, we present an efficient algorithm to find next-to-shortest path between any pair of vertices u,v on permutation graphs with n vertices which runs in O(n ²) time.     

Solving Partition Problems with Colour-Bipartitions

Polar, monopolar, and unipolar graphs are defined in terms of the existence of certain vertex partitions. Although it is polynomial to determine whether a graph is unipolar and to find whenever possible a unipolar partition, the problems of recognizing polar and monopolar graphs are both NP-complete in general. These problems have recently been studied for chordal, claw-free, and permutation graphs. Polynomial time algorithms have been found for solving the problems for these classes of graphs, with one exception: polarity recognition remains NP-complete in claw-free graphs. In this paper, we connect these problems to edge-coloured homomorphism problems. We show that finding unipolar partitions in general and finding monopolar partitions for certain classes of graphs can be efficiently reduced to a polynomial-time solvable 2-edge-coloured homomorphism problem, which we call the colour-bipartition problem. This approach unifies the currently known results on monopolarity and extends them to new classes of graphs.     

Split Permutation Graphs

The class of split permutation graphs is the intersection of two important classes, the split graphs and permutation graphs. It also contains an important subclass, the threshold graphs. The class of threshold graphs enjoys many nice properties. In particular, these graphs have bounded clique-width and they are well-quasi-ordered by the induced subgraph relation. It is known that neither of these two properties is extendable to split graphs or to permutation graphs. In the present paper, we study the question of extendability of these two properties to split permutation graphs. We answer this question negatively with respect to both properties. Moreover, we conjecture that with respect to both of them the split permutation graphs constitute a critical class.     

Point-symmetric graphs and digraphs of prime order and transitive permutation groups of prime degree

In this paper the following two problems are solved: Given any point-symmetric graph or digraph Γ of prime order the automorphism group of Γ is explicitly determined and given any transitive permutation group G of prime degree p the number of digraphs and graphs of order p having G as their automorphism group is determined.     

Every connected regular graph of even degree is a Schreier coset graph

Using Petersen's theorem, that every regular graph of even degree is 2-factorable, it is proved that every connected regular graph of even degree is isomorphic to a Schreier coset graph. The method used is a special application of the permutation voltage graph construction developed by the author and Tucker. This work is related to graph imbedding theory, because a Schreier coset graph is a covering space of a bouquet of circles.     

Vertex splitting and the recognition of trapezoid graphs

Trapezoid graphs are the intersection family of trapezoids where every trapezoid has a pair of opposite sides lying on two parallel lines. These graphs have received considerable attention and lie strictly between permutation graphs (where the trapezoids are lines) and cocomparability graphs (the complement has a transitive orientation). The operation of “vertex splitting”, introduced in (Cheah and Corneil, 1996) [3], first augments a given graph G and then transforms the augmented graph by replacing each of the original graph’s vertices by a pair of new vertices. This “splitted graph” is a permutation graph with special properties if and only if G is a trapezoid graph. Recently vertex splitting has been used to show that the recognition problems for both tolerance and bounded tolerance graphs is NP-complete (Mertzios et al., 2010) [11]. Unfortunately, the vertex splitting trapezoid graph recognition algorithm presented in (Cheah and Corneil, 1996) [3] is not correct. In this paper, we present a new way of augmenting the given graph and using vertex splitting such that the resulting algorithm is simpler and faster than the one reported in (Cheah and Corneil, 1996) [3].     

Connected permutation graphs

A permutation graph is a simple graph associated with a permutation. Let c_n be the number of connected permutation graphs on n vertices. Then the sequence {c_n} satisfies an interesting recurrence relation such that it provides partitions of n! as . We also see that, if uniformly chosen at random, asymptotically almost all permutation graphs are connected.     

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.     

Distance-transitive representations of the sporadic groups

A permutation representation of a finite group is multiplicity-free if all the irreducible constituents in the permutation character are distinct. There are three main reasons why these representations are interesting: it has been checked that all finite simple groups have such permutation representations, these are often of geometric interest, and the actions on vertices of distance-transitive graphs are multiplicity-free.

In this paper we classify the primitive multiplicity-free representations of the sporadic simple groups and their automorphism groups. We determine all the distance-transitive graphs arising from these representations. Moreover, we obtain intersection matrices for most of these actions, which are of further interest and should be useful in future investigations of the sporadic simple groups.     

The number of equivalence classes of symmetric sign patterns

This paper shows that the number of sign patterns of totally non-zero symmetric n-by-n matrices, up to conjugation by permutation and signature matrices and negation, is equal to the number of unlabelled graphs on n vertices.     

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.     

On the 3-restricted edge connectivity of permutation graphs

An edge cut W of a connected graph G is a k-restricted edge cut if G−W is disconnected, and every component of G−W has at least k vertices. The k-restricted edge connectivity is defined as the minimum cardinality over all k-restricted edge cuts. A permutation graph is obtained by taking two disjoint copies of a graph and adding a perfect matching between the two copies. The k-restricted edge connectivity of a permutation graph is upper bounded by the so-called minimum k-edge degree. In this paper some sufficient conditions guaranteeing optimal k-restricted edge connectivity and super k-restricted edge connectivity for permutation graphs are presented for k=2,3.