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 permutation graphs

We give an upper bound of the number of edges of a permutation graph. We introduce some necessary conditions for a graph to be a permutation graph, and we discuss the independence of these necessary conditions. We show that they are altogether not sufficient for a graph to be a permutation graph.     

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.     

On 3-skein isomorphisms of graphs

It is shown that a 3-skein isomorphism between 3-connected graphs with at least 5 vertices is induced by an isomorphism. These graphs have no loops but may be infinite and have multiple edges.     

On n-skein isomorphisms of graphs

H. Whitney [Amer. J. Math.54 (1932), 150–168] proved that edge isomorphisms between connected graphs with at least five vertices are induced by isomorphisms and that circuit isomorphisms between 3-connected graphs are induced by isomorphisms. R. Halin and H. A. Jung [J. London Math. Soc.42 (1967), 254–256] generalized these results by showing that for n ≥ 2, n-skein isomorphisms between (n+1)-connected graphs are induced by isomorphisms. In this paper we show that for n ≥ 2, n-skein isomorphisms between 3-connected graphs having (n+1)-skeins are induced by isomorphisms.     

On the geodetic number of permutation graphs

A vertex set S in a graph G is a geodetic set if every vertex of G lies on some u?v geodesic of G, where u,v∈S. The geodetic number g(G) of G is the minimum cardinality over all geodetic sets of G. Let G ₁ and G ₂ be disjoint copies of a graph G, and let σ:V(G ₁)→V(G ₂) be a bijection. Then, a permutation graph G _σ =(V,E) has the vertex set V=V(G ₁)∪V(G ₂) and the edge set E=E(G ₁)∪E(G ₂)∪{uv∣v=σ(u)}. For any connected graph G of order n≥3, we prove the sharp bounds 2≤g(G _σ )≤2n?(1+△(G)), where △(G) denotes the maximum degree of G. We give examples showing that neither is there a function h ₁ such that g(G)<h ₁(g(G _σ )) for all pairs (G,σ), nor is there a function h ₂ such that h ₂(g(G))>g(G _σ ) for all pairs (G,σ). Further, we characterize permutation graphs G _σ satisfying g(G _σ )=2|V(G)|?(1+△(G)) when G is a cycle, a tree, or a complete k-partite graph.     

Extending partial isomorphisms of graphs

Theorem Let X be a finite graph. Then there exists a finite graph Z containing X as an induced subgraphs, such that every isomorphism between induced subgraphs of X extends to an automorphism of Z.The graphZ may be required to be edge-transitive. The result implies that for anyn, there exists a notion of a genericn-tuple of automorphism of the Rado graphR (the random countable graph): for almost all automorphism ₁,..., _n and ₁ ofR (in the sense of Baire category), (R,₁,..., _n ), (R,₁,..., _n ). The problem arose in a recent paper of Hodges, Hodgkinson, Lascar and Shelah, where the theorem is used to prove the small index property forR.Work supported by a Sloan Fellowship and by NSF grant DMS-8903378.     

Search for minimal trivalent cycle permutation graphs with girth nine

The question of the girth of cycle permutation graphs is discussed. It is demonstrated by a computer search, that there are no cycle permutation graphs with girth 9 on less than 60 vertices, and that precisely two non-isomorphic examples exist on 60 vertices.     

Double-threshold permutation graphs

Journal of Algebraic Combinatorics - Double-threshold graphs are defined in terms of two real thresholds that break the real line into three regions, alternating as NO-YES-NO. If real ranks can be...     

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.     

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.     

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.     

Mauldin-Williams graphs, Morita equivalence and isomorphisms

We describe a method for associating some non-self-adjoint algebras to Mauldin-Williams graphs and we study the Morita equivalence and isomorphism of these algebras.

We also investigate the relationship between the Morita equivalence and isomorphism class of the -correspondences associated with Mauldin-Williams graphs and the dynamical properties of the Mauldin-Williams graphs.

     

On the cycle space of graphs

It is known that the cycle space of a planar graph G is generated by boundaries of faces of an embedding of G in the plane. We generalize this result as follows.     

Parallel algorithms for permutation graphs

In this paper, parallel algorithms are presented for solving some problems on permutation graphs. The coloring problem is solved inO(log² n) time usingO(n ³/logn) processors on the CREW PRAM, orO(logn) time usingO(n ³) processors on the CRCW PRAM. The weighted clique problem, the weighted independent set problem, the cliques cover problem, and the maximal layers problem are all solved with the same complexities. We can also show that the longest common subsequence problem belongs to the class NC.     

Coloring permutation graphs in parallel

A coloring of a graph G is an assignment of colors to its vertices so that no two adjacent vertices have the same color. We study the problem of coloring permutation graphs using certain properties of the lattice representation of a permutation and relationships between permutations, directed acyclic graphs and rooted trees having specific key properties. We propose an efficient parallel algorithm which colors an n-node permutation graph in O(log² n) time using O(n²/log n) processors on the CREW PRAM model. Specifically, given a permutation π we construct a tree T^*[π], which we call coloring-permutation tree, using certain combinatorial properties of π. We show that the problem of coloring a permutation graph is equivalent to finding vertex levels in the coloring-permutation tree.