The commutation graph for the longest signed permutation

Using the standard Coxeter presentation for the signed symmetric group ${\mathfrak{S}}_{n+1}^B$ on $n+1$ letters, two reduced expressions for a given signed permutation are in the same commutation class if one expression can be obtained from the other one by applying a finite sequence of commutations. The commutative classes of a given signed permutation can be seen as the vertices of a graph, called the commutation graph, where two classes are connected by an edge if there are elements in those classes that differ by a long braid relation. We define a rank function for the commutation graph for the longest signed permutation, and use this function to compute the diameter and the radius of the graph. We also prove that the commutation graph for the longest signed permutation is not planar for $n>2$, and identify the classes with a single element.     

Fast parallel graph searching with applications

This paper presents fast parallel algorithms for the following graph theoretic problems: breadth-depth search of directed acyclic graphs; minimum-depth search of graphs; finding the minimum-weighted paths between all node-pairs of a weighted graph and the critical activities of an activity-on-edge network. The first algorithm hasO(logdlogn) time complexity withO(n ³) processors and the remaining algorithms achieveO(logd loglogn) time bound withO(n ²[n/loglogn]) processors, whered is the diameter of the graph or the directed acyclic graph (which also represents an activity-on-edge network) withn nodes. These algorithms work on an unbounded shared memory model of the single instruction stream, multiple data stream computer that allows both read and write conflicts.     

Loops,regular permutation sets and graph colourings

We establish a correspondence among loops, regular permutation sets and directed graphs with a suitable edge colouring and relate some algebraic properties of the loop to configurations of the associated graph.     

Marginal permutation invariant covariance matrices with applications to linear models

The goal of the present paper is to perform a comprehensive study of the covariance structures in balanced linear models containing random factors which are invariant with respect to marginal permutations of the random factors. We shall focus on model formulation and interpretation rather than the estimation of parameters. It is proven that permutation invariance implies a specific structure for the covariance matrices. Useful results are obtained for the spectra of permutation invariant covariance matrices. In particular, the reparameterization of random effects, i.e., imposing certain constraints, will be considered. There are many possibilities to choose reparameterization constraints in a linear model, however not every reparameterization keeps permutation invariance. The question is if there are natural restrictions on the random effects in a given model, i.e., such reparameterizations which are defined by the covariance structure of the corresponding factor. Examining relationships between the reparameterization conditions applied to the random factors of the models and the spectrum of the corresponding covariance matrices when permutation invariance is assumed, restrictions on the spectrum of the covariance matrix are obtained which lead to “sum-to-zero” reparameterization of the corresponding factor.     

Finding a minimum independent dominating set in a permutation graph

We give a linear time reduction of the problem of finding a minimum independent dominating set in a permutation graph, into that of finding a shortest maximal increasing subsequence. We then give an O(n log²n)-time algorithm for solving the second (and hence the first) problem. This improves on the O(n³)-time algorithm given in [4] for solving the problem of finding a minimum independent dominating set in a permutation graph.     

Some applications of graph contractions

Results in diverse areas, such as the Nielsen-Schreier theorem on subgroups of free groups and a proof of A. T. White's conjecture on the genus of subgroups are shown to be immediate consequences of a lemma which has already proved useful in investigating topological properties and automorphism group of graphs.     

Efficient algorithms to compute all articulation points of a permutation graph

Based on the geometric representation, an efficient algorithm is designed to find all articulation points of a permutation graph. The proposed algorithm takes onlyO(n logn) time andO(n) space, wheren represents the number of vertices. The proposed sequential algorithm can easily be implemented in parallel which takesO(logn) time andO(n) processors on an EREW PRAM. These are the first known algorithms for the problem on this class of graph.     

Matrices permutation equivalent to irreducible matrices and applications

Dedicated to Leon Mirsky on the occasion of his sixtieth birthday.     

Enumerating maximal independent sets with applications to graph colouring

We give tight upper bounds on the number of maximal independent sets of size k (and at least k and at most k) in graphs with n vertices. As an application of the proof, we construct improved algorithms for graph colouring and computing the chromatic number of a graph.     

An extremal problem for sets with applications to graph theory

Let X₁, …, X_n be n disjoint sets. For 1 ? i ? n and 1 ? j ? h let A_ij and B_ij be subsets of X_i that satisfy |A_ij| ? r_i and |B_ij| ? s_i for 1 ? i ? n, 1 ? j ? h, $\text{(∪}{}_{\mathrm{i}}\text{A}{}_{\mathrm{ij}}\text{) ∩ (∪}{}_{\mathrm{i}}\text{B}{}_{\mathrm{ij}}\text{) = ?}$ for 1 ? j ? h, $\text{(∪}{}_{\mathrm{i}}\text{A}{}_{\mathrm{ij}}\text{) ∩ (∪}{}_{\mathrm{i}}\text{B}{}_{\mathrm{il}}\text{) ≠ ?}$ for 1 ? j < l ? h. We prove that $\text{h?}\text{Π}\text{i=1}\text{n}\text{r}{}_{\mathrm{i}}\text{+s}{}_{\mathrm{i}}\text{r}{}_{\mathrm{i}}$. This result is best possible and has some interesting consequences. Its proof uses multilinear techniques (exterior algebra).     

Inequalities for real number sequences with applications in spectral graph theory

Czechoslovak Mathematical Journal - Let a = (a1,a2, …, an) be a nonincreasing sequence of positive real numbers. Denote by S = {1, 2, …, n} the index set and by Jk = {I = {r1, r2,...     

A graph based model for survivability applications

Many problems found in standard security and survivability applications can be transformed into graph and scheduling problems, thereby opening up the problems to a wealth of potential solutions or knowledge of limitations, infeasibility, scalability or intractability. This paper introduces a model to aid in the design, analysis, or operations of applications with security and survivability concerns. Specifically, a five step model is presented that transforms such applications into a parameterized graph model that, together with model abstraction and representations, can be the basis for solutions derived from graph and scheduling algorithms. A reverse transformation translates the solutions back to the application domain. The model is demonstrated using migratory agent security and fault-tolerant agreement and their transformation into chain constrained and group scheduling problems, respectively.     

Global gradient estimate on graph and its applications

Continuing our previous work(ar Xiv:1509.07981v1),we derive another global gradient estimate for positive functions,particularly for positive solutions to the heat equation on finite or locally finite graphs.In general,the gradient estimate in the present paper is independent of our previous one.As applications,it can be used to get an upper bound and a lower bound of the heat kernel on locally finite graphs.These global gradient estimates can be compared with the Li–Yau inequality on graphs contributed by Bauer et al.[J.Differential Geom.,99,359–409(2015)].In many topics,such as eigenvalue estimate and heat kernel estimate(not including the Liouville type theorems),replacing the Li–Yau inequality by the global gradient estimate,we can get similar results.     

On some applications of graph theory,I

In a series of papers, of which the present one is Part I, it is shown that solutions to a variety of problems in distance geometry, potential theory and theory of metric spaces are provided by appropriate applications of graph theoretic results.     

On some applications of graph theory,I

In a series of papers, of which the present one is Part I, it is shown that solutions to a variety of problems in distance geometry, potential theory and theory of metric spaces are provided by appropriate applications of graph theoretic results.     

Minimax-type inequalities for a family of functions with applications

In the present paper there are given a number of minimax-type inequalities for a family of functions, involving two multivalued mappings, one being strongly decomposable and the other monotone. Hence some applications to the variational-type inequality theory and to the fixed point theory. Supported both by the National Natural Science Foundation of China and by the Institute of Mathematics, Academia Sinica     

A new Chebyshev family with applications to Abel equations

We prove that a family of functions defined through some definite integrals forms an extended complete Chebyshev system. The key point of our proof consists of reducing the study of certain Wronskians to the Gram determinants of a suitable set of new functions. Our result is then applied to give upper bounds for the number of isolated periodic solutions of some perturbed Abel equations.