Unicycle graphs and uniquely restricted maximum matchings

A matching M is called uniquely restricted in a graph G if it is the unique perfect matching of the subgraph induced by the vertices that M saturates. G is a unicycle graph if it owns only one cycle. Golumbic, Hirst and Lewenstein observed that for a tree or a graph with only odd cycles the size of a maximum uniquely restricted matching is equal to the matching number of the graph. In this paper we characterize unicycle graphs enjoying this equality. Moreover, we describe unicycle graphs with only uniquely restricted maximum matchings. Using these findings, we show that unicycle graphs having only uniquely restricted maximum matchings can be recognized in polynomial time.     

LU decomposition of M-matrices by elimination without pivoting

It is shown that if A or ?A is a singular M-matrix satisfying the generalized diagonal dominance condition y^TA?0 for some vector y? 0, then A can be factored into A = LU by a certain elimination algorithm, where L is a lower triangular M-matrix with unit diagonal and U is an upper triangular M-matrix. The existence of LU decomposition of symmetric permutations of A and for irreducible M-matrices and symmetric M-matrices follow as colollaries. This work is motivated by applications to the solution of homogeneous systems of linear equations Ax = 0, where A or ?A is an M-matrix. These applications arise, e.g., in the analysis of Markov chains, input-output economic models, and compartmental systems. A converse of the theorem metioned above can be established by considering the reduced normal form of A.     

An application of the structural theory of acyclic skew-symmetric graphs

It is known that if an undirected graph G contains a unique perfect matching M, then M contains at least one of bridges of G. In this paper an alternative proof of this statement is presented. The proof is based on the structural theory of acyclic skew-symmetric graphs developed by the author.     

A remark on the space of metrics having nontrivial harmonic spinors

Let M be a closed spin manifold of dimension n ≡ 3 mod 4. We give a simple proof of the fact that the space of metrics on M with invertible Dirac operator is either empty or it has infinitely many path components.     

On forcing matching number of boron-nitrogen fullerene graphs

Let G be a graph that admits a perfect matching M. A forcing set S for a perfect matching M is a subset of M such that it is contained in no other perfect matchings of G. The smallest cardinality of forcing sets of M is called the forcing number of M. Computing the minimum forcing number of perfect matchings of a graph is an NP-complete problem. In this paper, we consider boron-nitrogen (BN) fullerene graphs, cubic 3-connected plane bipartite graphs with exactly six square faces and other hexagonal faces. We obtain the forcing spectrum of tubular BN-fullerene graphs with cyclic edge-connectivity 3. Then we show that all perfect matchings of any BN-fullerene graphs have the forcing number at least two. Furthermore, we mainly construct all seven BN-fullerene graphs with the minimum forcing number two.     

Homotopy finiteness theorems and Helly’s theorem

A new proof is presented of the noncriticality of the distance function on a neighborhood of the diagonal inM ×M, whereM is a compactn-dimensional manifold with diameter ≤D ₀, volume ≥v ₀ > 0, and sectional curvature ≥ ?Λ, with the size of the neighborhood depending only onn,D ₀,v ₀, and Λ. This gives a generalization of the Grove-Petersen finiteness theorem and elucidates the role of the sectional curvature bound, as opposed to just a Ricci curvature lower bound, in such theorems.     

Lifts of tensor fields to the frame bundle

LetM be a differentiable manifold,T M its tangent bundle andF M its frame bundle. The theory of lifts toT M of tensor fields onM has been extensively studied by many authors. In this paper, a similar theory for the frame bundle is developed by introducing the complete, horizontal and diagonal lifts toF M of tensor fields onM, with the aim of making this study as closely comparable with that forT M as possible.     

On superperfect noncomparability graphs

The class of superperfect graphs, which was previously studied by A. J. Hoffman, E. L. Johnson, and M. C. Golumbic, is a proper subclass of the class of perfect graphs; further, it properly contains the class of comparability graphs. In his book, Golumbic proves that, for split graphs, G is a comparability graph if and only if G is superperfect. Moreover, the fact that split graphs are exactly those graphs which are both triangulated and cotriangulated motivated Golumbic to ask if it is true or false that, for triangulated (or cotriangulated) graphs, G is a comparability graph if and only if G is superperfect. In the present paper, we determine those members of Gallai's list of minimal noncomparability graphs which are superperfect and, as a consequence, we find that the answer to the above question is “false” for triangulated and “true” for cotriangulated graphs.     

On the forbidden induced subgraph sandwich problem

We consider the sandwich problem, a generalization of the recognition problem introduced by Golumbic et al. (1995) [15], with respect to classes of graphs defined by excluding induced subgraphs. We prove that the sandwich problem corresponding to excluding a chordless cycle of fixed length k is NP-complete. We prove that the sandwich problem corresponding to excluding K_r?e for fixed r is polynomial. We prove that the sandwich problem corresponding to 3PC(⋅,⋅)-free graphs is NP-complete. These complexity results are related to the classification of a long-standing open problem: the sandwich problem corresponding to perfect graphs.     

A trace inequality for M-matrices and the symmetrizability of a real matrix by a positive diagonal matrix

The question of whether a real matrix is symmetrizable via multiplication by a diagonal matrix with positive diagonal entries is reduced to the corresponding question for M-matrices and related to Hadamard products. In the process, for a nonsingular M-matrix A, it is shown that tr(A^-1A^T) ? n, with equality if and only if A is symmetric, and that the minimum eigenvalue of A^-1 ° A is ? 1 with equality in the irreducible case if and only if A is positive diagonally symmetrizable.     

Deformation spaces of one-dimensional formal modules and their cohomology

Let Mm be the formal scheme which represents the functor of deformations of a one-dimensional formal module over equipped with a level-m-structure. By work of Boyer (in equal characteristic) and Harris and Taylor, the ?-adic étale cohomology of the generic fibre Mm of Mm realizes simultaneously the local Langlands and Jacquet-Langlands correspondences. The proofs given so far use Drinfeld modular varieties or Shimura varieties to derive this local result. In this paper we show without the use of global moduli spaces that the Jacquet-Langlands correspondence is realized by the Euler-Poincaré characteristic of the cohomology. Under a certain finiteness assumption on the cohomology groups, it is shown that the correspondence is realized in only one degree. One main ingredient of the proof consists in analyzing the boundary of the deformation spaces and in studying larger spaces which can be considered as compactifications of the spaces Mm.     

On square roots of M-matrices

The question of the existence and uniqueness of an M-matrix which is a square root of an M-matrix is discussed. The results are then used to derive some new necessary and sufficient conditions for a real matrix with nonpositive off diagonal elements to be an M-matrix.     

Geometric existence theory for the control-affine nonlinear optimal regulator

For infinite horizon nonlinear optimal control problems in which the control term enters linearly in the dynamics and quadratically in the cost, well-known conditions on the linearised problem guarantee existence of a smooth globally optimal feedback solution on a certain region of state space containing the equilibrium point. The method of proof is to demonstrate existence of a stable Lagrangian manifold M and then construct the solution from M in the region where M has a well-defined projection onto state space. We show that the same conditions also guarantee existence of a nonsmooth viscosity solution and globally optimal set-valued feedback on a much larger region. The method of proof is to extend the construction of a solution from M into the region where M no-longer has a well-defined projection onto state space.     

Weighted inverse maximum perfect matching problems under the Hamming distance

Given an undirected network G(V, E, c) and a perfect matching M ⁰, the inverse maximum perfect matching problem is to modify the cost vector as little as possible such that the given perfect matching M ⁰ can form a maximum perfect matching. The modification can be measured by different norms. In this paper, we consider the weighted inverse maximum perfect matching problems under the Hamming distance, where we use the weighted Hamming distance to measure the modification of the edges. We consider both of the sum-type and the bottleneck-type problems. For the general case of the sum-type case, we show it is NP-hard. For the bottleneck-type, we present a strongly polynomial algorithm which can be done in O(m · n ³).     

Covariant and equivariant formality theorems

We give a proof of Kontsevich's formality theorem for a general manifold using Fedosov resolutions of algebras of polydifferential operators and polyvector fields. The main advantage of our construction of the formality quasi-isomorphism is that it is based on the use of covariant tensors unlike Kontsevich's original proof, which is based on ∞-jets of polydifferential operators and polyvector fields. Using our construction we prove that if a group G acts smoothly on a manifold M and M admits a G-invariant affine connection then there exists a G-equivariant quasi-isomorphism of formality. This result implies that if a manifold M is equipped with a smooth action of a finite or compact group G or equipped with a free action of a Lie group G then M admits a G-equivariant formality quasi-isomorphism. In particular, this gives a solution of the deformation quantization problem for an arbitrary Poisson orbifold.     

Structure of invertible (bi)infinite totally positive matrices

An l_∞-invertible nonfinite totally positive matrix A is shown to have one and only one “main diagonal.” This means that exactly one diagonal of A has the property that all finite sections of A principal with respect to this diagonal are invertible and their inverses converge boundedly and entrywise to A^-1. This is shown to imply restrictions on the possible shapes of such a matrix. In the proof, such a matrix is also shown to have an l_∞-invertible LDU factorization. In addition, decay of the entries of such a matrix away from the main diagonal is demonstrated. It is also shown that a bounded sign-regular matrix carrying some bounded sequence to a uniformly alternating sequence must have all its columns in c₀.     

Distance-restricted matching extension in planar triangulations

A graph G is said to have property E(m,n) if it contains a perfect matching and for every pair of disjoint matchings M and N in G with |M|=m and |N|=n, there is a perfect matching F in G such that M⊆F and N∩F=0?. In a previous paper (Aldred and Plummer 2001) [2], an investigation of the property E(m,n) was begun for graphs embedded in the plane. In particular, although no planar graph is E(3,0), it was proved there that if the distance among the three edges is at least two, then they can always be extended to a perfect matching. In the present paper, we extend these results by considering the properties E(m,n) for planar triangulations when more general distance restrictions are imposed on the edges to be included and avoided in the extension.     

Reducing complex matrices to condensed forms by unitary congruence transformations

We show that any n × n conjugate-normal matrix can be brought by a unitary congruence transformation to block-tridiagonal form with the orders of the consecutive diagonal blocks not exceeding 1, 2, 3, ..., respectively. The proof is constructive; namely, a finite process is described that implements the reduction to the desired form. Sufficient conditions are indicated for the orders of the diagonal blocks to stabilize. In this case, the condensed form is a band matrix.     

Spanning quadrangulations of triangulated surfaces

In this paper we study alternating cycles in graphs embedded in a surface. We observe that 4-vertex-colorability of a triangulation on a surface can be expressed in terms of spanninq quadrangulations, and we establish connections between spanning quadrangulations and cycles in the dual graph which are noncontractible and alternating with respect to a perfect matching. We show that the dual graph of an Eulerian triangulation of an orientable surface other than the sphere has a perfect matching M and an M-alternating noncontractible cycle. As a consequence, every Eulerian triangulation of the torus has a nonbipartite spanning quadrangulation. For an Eulerian triangulation G of the projective plane the situation is different: If the dual graph \(G^*\) is nonbipartite, then \(G^*\) has no noncontractible alternating cycle, and all spanning quadrangulations of G are bipartite. If the dual graph \(G^*\) is bipartite, then it has a noncontractible, M-alternating cycle for some (and hence any) perfect matching, G has a bipartite spanning quadrangulation and also a nonbipartite spanning quadrangulation.