Counting perfect matchings in n-extendable graphs

The structural theory of matchings is used to establish lower bounds on the number of perfect matchings in n-extendable graphs. It is shown that any such graph on p vertices and q edges contains at least ⌈(n+1)!/4[q-p-(n-1)(2Δ-3)+4]⌉ different perfect matchings, where Δ is the maximum degree of a vertex in G.     

Matchings in benzene chains

An explicit recurrence relation is derived for the matching polynomial of the general benzene chain B_n. A table is given for chains of length up to 6. Explicit formulae are then obtained for the first five coefficients of the matching polynomial of B_n. Finally, results are deduced for the number of perfect matchings and the number of matchings with two nodes.     

Perfect Matchings of Cellular Graphs

We introduce a family of graphs, called cellular, and consider the problem of enumerating their perfect matchings. We prove that the number of perfect matchings of a cellular graph equals a power of 2 times the number of perfect matchings of a certain subgraph, called the core of the graph. This yields, as a special case, a new proof of the fact that the Aztec diamond graph of order n introduced by Elkies, Kuperberg, Larsen and Propp has exactly 2 ^n(n+1)/2 perfect matchings. As further applications, we prove a recurrence for the number of perfect matchings of certain cellular graphs indexed by partitions, and we enumerate the perfect matchings of two other families of graphs called Aztec rectangles and Aztec triangles.     

On construction of vertex-transitive partitions of the <Emphasis Type="Italic">n</Emphasis>-cube into perfect codes

Two methods are presented to construct some vertex-transitive and 2-transitive partitions of the n-cube into perfect codes. Some lower bounds are given on the number of transitive, vertex-transitive, and 2-transitive partitions of the n-cube into perfect codes.     

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.     

Matching structure and the matching lattice

The matching polyhedron, i.e., the convex hull of (incidence vectors of) perfect matchings of a graph was characterized by Edmonds; this result is the key to a large part of polyhedral combinatorics and is used in many combinatorial algorithms. The linear hull of perfect matchings was characterized by Naddef, and by Edmonds, Lovász, and Pulleyblank. In this paper we describe the lattice generated by these vectors, i.e., the set of all integer linear combinations of perfect matchings. It turns out that the Petersen graph is, in a sense, the only difficult example. Our results also imply a characterization of the linear hull of perfect matchings over fields of characteristic different from 0. The main method is a decomposition theory developed by Kotzig, Lovász, and Plummer, which breaks down every graph into a number of graphs called bricks with very good matching properties. The number of Petersen graphs among these bricks will turn out to be an essential parameter of the matching lattice. Some refinements of the decomposition theory are also given. Among others, we show that the list of bricks obtained during the decomposition procedure is independent of the special choices made during the procedure.     

Forcing matching numbers of fullerene graphs

The forcing number or the degree of freedom of a perfect matching M of a graph G is the cardinality of the smallest subset of M that is contained in no other perfect matchings of G. In this paper we show that the forcing numbers of perfect matchings in a fullerene graph are not less than 3 by applying the 2-extendability and cyclic edge-connectivity 5 of fullerene graphs obtained recently, and Kotzig’s classical result about unique perfect matching as well. This lower bound can be achieved by infinitely many fullerene graphs.     

Incomparable integrals and approximate calculation of monotone Boolean functions

The number of incomparable k-dimensional intervals in the Boolean n-cube is estimated. The result is used to estimate the complexity of approximate computation of an arbitrary monotone Boolean function of n variables.     

A triangulation of the n-cube

This paper is concerned with estimating ?(n), the minimum number of n-simplices required to triangulate an n-cube.     

Clique matchings in the <Emphasis Type="Italic">k</Emphasis>-ary <Emphasis Type="Italic">n</Emphasis>-dimensional cube

A clique matching in the k-ary n-dimensional cube (hypercube) is a collection of disjoint one-dimensional faces. A clique matching is called perfect if it covers all vertices of the hypercube. We show that the number of perfect clique matchings in the k-ary n-dimensional cube can be expressed as the k-dimensional permanent of the adjacency array of some hypergraph. We calculate the order of the logarithm of the number of perfect clique matchings in the k-ary n-dimensional cube for an arbitrary positive integer k as n→∞.     

Matching preclusion and conditional matching preclusion for regular interconnection networks

The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings. For many interconnection networks, the optimal sets are precisely those induced by a single vertex. Recently, the conditional matching preclusion number of a graph was introduced to look for obstruction sets beyond those induced by a single vertex. It is defined to be the minimum number of edges whose deletion results in a graph with no isolated vertices and neither perfect matchings nor almost-perfect matchings. In this paper, we prove general results regarding the matching preclusion number and the conditional matching preclusion number as well as the classification of their respective optimal sets for regular graphs. We then use these general results to study the problems for Cayley graphs generated by 2-trees and the hyper Petersen networks.     

Another universality property for crumpled cubes

Let C denote a crumpled n-cube in the n-sphere Sⁿ such that every Cantor set in its boundary is tamely embedded in Sⁿ. The main theorem shows C to be universal in the sense that however it is sewn to a crumpled n-cube D of type 2A, a large class containing most of the explicitly described examples, the resultant space is homeomorphic to Sⁿ.     

Matching binary convexities

We showed in an earlier paper that the Radon number of an n-dimensional binary convexity equals the Radon number of the n-cube, except for a well-determined sequence of dimensions, in which case the Radon number may be one unit larger. Examples of the latter are obtained in every predicted dimension. The basic tool is a matching procedure which works for binary convexities.     

Stochastic Enumeration Method for Counting NP-Hard Problems

We present a new generic sequential importance sampling algorithm, called stochastic enumeration (SE) for counting #P-complete problems, such as the number of satisfiability assignments and the number of perfect matchings (permanent). We show that SE presents a natural generalization of the classic one-step-look-ahead algorithm in the sense that it: Runs in parallel multiple trajectories instead of a single one; Employs a polynomial time decision making oracle, which can be viewed as an n-step-look-ahead algorithm, where n is the size of the problem. Our simulation studies indicate good performance of SE as compared with the well-known splitting and SampleSearch methods.     

Observations on a class of nasty linear complementarity problems

Earlier papers by Murty [16] and Fathi [7] have exhibited classes of linear complementarity problems for which the computational effort (number of pivot steps) required to solve them by Lemke's algorithm [13] or Murty's algorithm [15] grows exponentially with the pronlem size (number of variables). In this paper we consider the sequences of complementary bases that arise as these problems are solved by the aforementioned algorithms. There is a natural correspondence between these bases and binary n-vectors through which the basis sequences can be identified with particular hamiltonian paths on the unit n-cube and with the binary Gray code representations of the integers from 0 to 2ⁿ-1.     

Bounding the size of square-free subgraphs of the hypercube

We investigate the maximum size of a subset of the edges of the n-cube that does not contain a square, or 4-cycle. The size of such a subset is trivially at most 3/4 of the total number of edges, but the proportion was conjectured by Erd?s to be asymptotically 1/2. Following a computer investigation of the 4-cube and the 5-cube, we improve the known upper bound from 0.62284… to 0.62256… in the limit.     

Highly Symmetric Subgraphs of Hypercubes

Two questions are considered, namely (i) How many colors are needed for a coloring of the n-cube without monochromatic quadrangles or hexagons? We show that four colors suffice and thereby settle a problem of Erdös. (ii) Which vertex-transitive induced subgraphs does a hypercube have? An interesting graph has come up in this context: If we delete a Hamming code from the 7-cube, the resulting graph is 6-regular, vertex-transitive and its edges can be two-colored such that the two monochromatic subgraphs are isomorphic, cubic, edge-transitive, nonvertex-transitive graphs of girth 10.     

On balanced colorings of the <Emphasis Type="Italic">n</Emphasis>-cube

A 2-coloring of the n-cube in the n-dimensional Euclidean space can be considered as an assignment of weights of 1 or 0 to the vertices. Such a colored n-cube is said to be balanced if its center of mass coincides with its geometric center. Let B _n,2k be the number of balanced 2-colorings of the n-cube with 2k vertices having weight 1. Palmer, Read, and Robinson conjectured that for n≥1, the sequence \(\{B_{n,2k}\}_{k=0,1,\ldots,2^{n-1}}\) is symmetric and unimodal. We give a proof of this conjecture. We also propose a conjecture on the log-concavity of B _n,2k for fixed k, and by probabilistic method we show that it holds when n is sufficiently large.     

Non-P-recursiveness of numbers of matchings or linear chord diagrams with many crossings

The number con_n counts matchings X on {1,2,…,2n}, which are partitions into n two-element blocks, such that the crossing graph of X is connected. Similarly, cro_n counts matchings whose crossing graph has no isolated vertex. (If it has no edge, Catalan numbers arise.) We apply generating functions techniques and prove, using a more generally applicable criterion, that the sequences (con_n) and (cro_n) are not P-recursive. On the other hand, we show that the residues of con_n and cro_n modulo any fixed power of 2 can be determined P-recursively. We consider also the numbers sco_n of symmetric connected matchings. Unfortunately, their generating function satisfies a complicated differential equation which we cannot handle.