Search

A connected graph G is H - removable if H is a subgraph of G , G has at least | V (H) | + 2 vertices and G − V (H ′) has a perfect matching for every subgraph H ′ of G isomorphic to H. So a connected graph is k K 2 -removable if and only if it is k -extendable, where k K 2 is a matching of size k. Further G is an H - forced graph if G − V (H ′) has a unique perfect matching for every subgraph H ′ of G isomorphic to H. In this paper, we first characterize k K 2 -forced graphs for k ≥ 2 as K 2 k + 2 and K k + 1 , k + 1 by using randomly matchable graphs. Let P i denote a path with i vertices. We show that P 3 - and P 4 -removable graphs are factor-critical and 1-extendable respectively. By using ear decomposition, we obtain that a connected graph G is P 3 -forced if and only if G is K 5 or C 2 k + 1 (k ≥ 2). Finally we prove that a connected graph G is P 4 -forced if and only if G is isomorphic to K 6 , K 3 , 3 , C 2 k (k ≥ 3), the Petersen graph, a uniform theta graph Θ 3 n (n ≥ 3) or C 12 +. [ABSTRACT FROM AUTHOR]

The perfect matching polytope of a graph G is the convex hull of the incidence vectors of all perfect matchings of G. A graph G is PM-compact if the 1-skeleton graph of the prefect matching polytope of G is complete. Equivalently, a matchable graph G is PM-compact if and only if for each even cycle C of G, G ∔ V(C) has at most one perfect matching. This paper considers the class of graphs from which deleting any two adjacent vertices or nonadjacent vertices, respectively, the resulting graph has a unique perfect matching. The PM-compact graphs in this class of graphs are presented. [ABSTRACT FROM AUTHOR]

An even cycle C in a graph G is a nice cycle if G − V (C) has a perfect matching. A graph G is cycle-nice if each even cycle in G is a nice cycle. An even cycle C in an orientation of a graph G is clockwise odd if the number of its edges directed in the clockwise sense is odd. A graph G is Pfaffian if there is an orientation of G such that each nice cycle of G is clockwise odd. The significance of Pfaffian graphs is that the number of perfect matchings of a Pfaffian graph may be computed in polynomial time. Clearly, if G is a cycle-nice graph, then G is Pfaffian if and only if G admits an orientation such that each even cycle in G is clockwise odd. In this paper we obtain complete characterizations of 3-connected and 2-connected claw-free graphs that are cycle-nice. Using these characterizations, we can decide if a cycle-nice 2-connected claw-free graph is Pfaffian. [ABSTRACT FROM AUTHOR]

Abstract: Let G be a graph and let Pm denote the number of perfect matchings of G. We denote the path with m vertices by and the Cartesian product of graphs G and H by . In this paper, as the continuance of our paper [W. Yan, F. Zhang, Enumeration of perfect matchings of graphs with reflective symmetry by Pfaffians, Adv. Appl. Math. 32 (2004) 175–188], we enumerate perfect matchings in a type of Cartesian products of graphs by the Pfaffian method, which was discovered by Kasteleyn. Here are some of our results: 1. Let T be a tree and let denote the cycle with n vertices. Then Pm, where the product ranges over all eigenvalues of T. Moreover, we prove that Pm is always a square or double a square. 2. Let T be a tree. Then Pm, where the product ranges over all non-negative eigenvalues of T. 3. Let T be a tree with a perfect matching. Then Pm where the product ranges over all positive eigenvalues of T. Moreover, we prove that Pm. [Copyright &y& Elsevier]

The Pfaffian method enumerating perfect matchings of plane graphs was discovered by Kasteleyn. We use this method to enumerate perfect matchings in a type of graphs with reflective symmetry which is different from the symmetric graphs considered in [J. Combin. Theory Ser. A 77 (1997) 67, MATCH—Commun. Math. Comput. Chem. 48 (2003) 117]. Here are some of our results: (1) If G is a reflective symmetric plane graph without vertices on the symmetry axis, then the number of perfect matchings of G can be expressed by a determinant of order &z.sfnc;G&z.sfnc;/2, where &z.sfnc;G&z.sfnc; denotes the number of vertices of G. (2) If G contains no subgraph which is, after the contraction of at most one cycle of odd length, an even subdivision of K2,3, then the number of perfect matchings of G×K2 can be expressed by a determinant of order &z.sfnc;G&z.sfnc;. (3) Let G be a bipartite graph without cycles of length 4s, s∈{1,2,…}. Then the number of perfect matchings of G×K2 equals ∏(1+θ2)mθ, where the product ranges over all non-negative eigenvalues θ of G and mθ is the multiplicity of eigenvalue θ. Particularly, if T is a tree then the number of perfect matchings of T×K2 equals ∏(1+θ2)mθ, where the product ranges over all non-negative eigenvalues θ of T and mθ is the multiplicity of eigenvalue θ. [Copyright &y& Elsevier]