Graceful Signed Graphs

A (p, q)-sigraph S is an ordered pair (G, s) where G = (V, E) is a (p, q)-graph and s is a function which assigns to each edge of G a positive or a negative sign. Let the sets E ⁺ and E ^– consist of m positive and n negative edges of G, respectively, where m + n = q. Given positive integers k and d, S is said to be (k, d)-graceful if the vertices of G can be labeled with distinct integers from the set {0, 1, ..., k + (q – 1)d such that when each edge uv of G is assigned the product of its sign and the absolute difference of the integers assigned to u and v the edges in E ⁺ and E ^– are labeled k, k + d, k + 2d, ..., k + (m – 1)d and –k, – (k + d), – (k + 2d), ..., – (k + (n – 1)d), respectively.In this paper, we report results of our preliminary investigation on the above new notion, which indeed generalises the well-known concept of (k, d)-graceful graphs due to B. D. Acharya and S. M. Hegde.     

关于正形置换多项式的注记

n为正整数，m为大于1的正整数，本文证明了当n≡0，1（mod m）时，F2^n上不存在2^m-1次正形置换多项式，并给出了该结果的几个推论：F2^n上不存在次数为3的正形置换多项式；n〉2时，F2^n上的4次正形置换多项式都是仿射多项式．     

在对称群Sm中解循环方程组

本文研究了在对称群S_m中解循环方程组:x_mX_(m+1)…x_(ω+k-1)σ_m,其中σ_m∈S_m,ω=1,2,…,s,确定了这个循环方程组有解的充分必要条件和解的个数,而且给出了求解过程。     

Stories about groups and sequences

The main theme of this article is that counting orbits of an infinite permutation group on finite subsets or tuples is very closely related to combinatorial enumeration; this point of view ties together various disparate stories. Among these are reconstruction problems, the relation between connected and arbitrary graphs, the enumeration of N-free posets, and some of the combinatorics of Stirling numbers.Dedicated to Hanfried Lenz on the occasion of his 80th birthday.     

A Hecke Algebra Quotient and Some Combinatorial Applications

Let (W, S) be a Coxeter group associated to a Coxeter graph which has no multiple bonds. Let H be the corresponding Hecke Algebra. We define a certain quotient \-H of H and show that it has a basis parametrized by a certain subset W _cof the Coxeter group W. Specifically, W _cconsists of those elements of W all of whose reduced expressions avoid substrings of the form sts where s and t are noncommuting generators in S. We determine which Coxeter groups have finite W _cand compute the cardinality of W _cwhen W is a Weyl group. Finally, we give a combinatorial application (which is related to the number of reduced expressions for w W _cof an exponential formula of Lusztig which utilizes a specialization of a subalgebra of \-H.     

The permutational power of a priority queue

A priority queue transforms an input permutation of some set of sizen into an output permutation. It is shown that the number of such pairs (, ) is (n + 1) ^n–1. Some related enumerative and algorithmic questions are also considered.Supported by the National Science and Engineering Research Council of Canada under Grant A4219.     

Stereogenicity/Astereogenicity as Global/Local Permutation-Group Symmetry and Relevant Concepts for Restructuring Stereochemistry

Molecules of ligancy 4 that have been derived from an allene, an ethylene, a tetrahedral, and a square-planar skeleton have been investigated to show that their symmetries are dually and distinctly controlled by point groups and permutation groups. Insomuch as the point-group symmetry was exhibited to control the chirality/achirality of a molecule, sphericity in a molecule, and enantiomeric relationship between molecules [S. Fujita, J. Am. Chem. Soc. 112 (1990) 3390], the permutation-group symmetry has been now clarified to control the stereogenicity of a molecule, tropicity in a molecule, and diastereomeric relationship between molecules. To characterize permutation groups, proper and improper permutations have been defined by comparing proper and improper rotations. Thereby, such permutation groups are classified into stereogenic and astereogenic ones. After a coset representation (CR) of a permutation group has been ascribed to an orbit (equivalence class), the tropicity of the orbit has been defined in term of the global stereogenicity and the local stereogenicity of the CR. As a result, the conventional stereogenicity has now been replaced by the concept local stereogenicity of the present investigation. The terms homotropic, enantiotropic, and hemitropic are coined and used to characterize prostereogenicity. Thus, a molecule is defined as being prostereogenic if it has at least one enantiotropic orbit. Since this definition has been found to be parallel with the definition of prochirality, relevant concepts have been discussed with respect to the parallelism between stereogenicity and chirality in order to restructure the theoretical foundation of stereochemistry and stereoisomerism. The derivation of the skeletons has been characterized by desymmetrization due to the subduction of CRs. The Cahn–Ingold–Prelog (CIP) system has been discussed from the permutational point of view to show that it specifies diastereomeric relationships only. The apparent specification of enantiomeric relationships by the CIP system has been shown to stem from the fact that diastereomeric relationships and enantiomeric ones overlap occasionally in case of tetrahedral molecules.     

Chemical applications of topology and group theory

The 60 even permutations of the ligands in the five-coordinate complexes, ML ₅, form the alternating group A ₅, which is isomorphic with the icosahedral pure rotation group I. Using this idea, it is shown how a regular icosahedron can be used as a topological representation for isomerizations of the five-coordinate complexes, ML ₅, involving only even permutations if the five ligands L correspond either to the five nested octahedra with vertices located at the midpoints of the 30 edges of the icosahedron or to the five regular tetrahedra with vertices located at the midpoints of the 20 faces of the icosahedron. However, the 120 total permutations of the ligands in five-coordinate complexes ML ₅ cannot be analogously represented by operations in the full icosahedral point group I _h, since I _his the direct product I×C₂ whereas the symmetric group S ₅ is only the semi-direct product A ₅S₂. In connection with previously used topological representations on isomerism in five-coordinate complexes, it is noted that the automorphism groups of the Petersen graph and the Desargues-Levi graph are isomorphic to the symmetric group S ₅ and to the direct product S ₅×S ₂, respectively. Applications to various fields of chemistry are briefly outlined.     

Sphericity governs both stereochemistry in a molecule and stereoisomerism among molecules

The concept of sphericity and relevant fundamental concepts that we have proposed have produced a systematized format for comprehending stereochemical phenomena. Permutability of ligands in conventional approaches is discussed from a stereochemical point of view. After the introduction of orbits governed by coset representations, the concepts of subduction and sphericity are proposed to characterize desymmetrization processes, with a tetrahedral skeleton as an example. The stereochemistry and stereoisomerism of the resulting promolecules (molecules formulated abstractly) are discussed in terms of the concept of sphericity as a common mathematical and logical framework. Thus, these promolecules are characterized by point group and permutation group symmetry. Prochirality, stereogenicity, prostereogenicity, and relevant topics are described in terms of the concept of sphericity.     

Colourings of cubic graphs inducing isomorphic monochromatic subgraphs

A -bisection of a bridgeless cubic graph is a -colouring of its vertex set such that the colour classes have the same cardinality and all connected components in the two subgraphs induced by the colour classes ( monochromatic components in what follows) have order at most . Ban and Linial Conjectured that every bridgeless cubic graph admits a -bisection except for the Petersen graph. A similar problem for the edge set of cubic graphs has been studied: Wormald conjectured that every cubic graph with has a -edge colouring such that the two monochromatic subgraphs are isomorphic linear forests (ie, a forest whose components are paths). Finally, Ando conjectured that every cubic graph admits a bisection such that the two induced monochromatic subgraphs are isomorphic. In this paper, we provide evidence of a strong relation of the conjectures of Ban-Linial and Wormald with Ando's Conjecture. Furthermore, we also give computational and theoretical evidence in their support. As a result, we pose some open problems stronger than the above-mentioned conjectures. Moreover, we prove Ban-Linial's Conjecture for cubic-cycle permutation graphs. As a by-product of studying -edge colourings of cubic graphs having linear forests as monochromatic components, we also give a negative answer to a problem posed by Jackson and Wormald about certain decompositions of cubic graphs into linear forests.