Results 21 to 30 of about 553 (214)
Annihilating random walks and perfect matchings of planar graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2003 We study annihilating random walks on $\mathbb{Z}$ using techniques of P.W. Kasteleyn and $R$. Kenyonon perfect matchings of planar graphs. We obtain the asymptotic of the density of remaining particles and the partition function of the underlying ...
Massimiliano Mattera
doaj +1 more source
Revisiting a Cutting-Plane Method for Perfect Matchings
Open Journal of Mathematical Optimization, 2020 In 2016, Chandrasekaran, Végh, and Vempala (Mathematics of Operations Research, 41(1):23–48) published a method to solve the minimum-cost perfect matching problem on an arbitrary graph by solving a strictly polynomial number of linear programs.
Chen, Amber Q. +3 more
doaj +1 more source
Perfect Matchings and Cluster Algebras of Classical Type [PDF]
Discrete Mathematics & Theoretical Computer Science, 2008 In this paper we give a graph theoretic combinatorial interpretation for the cluster variables that arise in most cluster algebras of finite type. In particular, we provide a family of graphs such that a weighted enumeration of their perfect matchings ...
Gregg Musiker
doaj +1 more source
Packing Plane Perfect Matchings into a Point Set [PDF]
Discrete Mathematics & Theoretical Computer Science, 2015 Given a set $P$ of $n$ points in the plane, where $n$ is even, we consider the following question: How many plane perfect matchings can be packed into $P$? For points in general position we prove the lower bound of ⌊log2$n$⌋$-1$.
Ahmad Biniaz +3 more
doaj +1 more source
Near―perfect non-crossing harmonic matchings in randomly labeled points on a circle [PDF]
Discrete Mathematics & Theoretical Computer Science, 2005 Consider a set $S$ of points in the plane in convex position, where each point has an integer label from $\{0,1,\ldots,n-1\}$. This naturally induces a labeling of the edges: each edge $(i,j)$ is assigned label $i+j$, modulo $n$.
József Balogh +2 more
doaj +1 more source
Electronic Journal of Graph Theory and Applications, 2017 In decomposition theory, extreme sets have been studied extensively due to its connection to perfect matchings in a graph. In this paper, we first define extreme sets with respect to degree-matchings and next investigate some of their properties.
Radosław Cymer
doaj +1 more source
Almost all Steiner triple systems are almost resolvable
Forum of Mathematics, Sigma, 2020 We show that for any n divisible by 3, almost all order-n Steiner triple systems admit a decomposition of almost all their triples into disjoint perfect matchings (that is, almost all Steiner triple systems are almost resolvable).
Asaf Ferber, Matthew Kwan
doaj +1 more source
Generalized Matching Preclusion in Bipartite Graphs
Theory and Applications of Graphs, 2018 The matching preclusion number of a graph with an even number of vertices is the minimum number of edges whose deletion results in a graph that has no perfect matchings. For many interconnection networks, the optimal such sets are precisely sets of edges
Zachary Wheeler +4 more
doaj +1 more source
International Journal of Mathematics and Mathematical Sciences, 1987 Explicit recurrences are derived for the matching polynomials of the basic types of hexagonal cacti, the linear cactus and the star cactus and also for an associated graph, called the hexagonal crown.
E. J. Farrell
doaj +1 more source
Classical Dimers on Penrose Tilings
Physical Review X, 2020 We study the classical dimer model on rhombic Penrose tilings, whose edges and vertices may be identified as those of a bipartite graph. We find that Penrose tilings do not admit perfect matchings (defect-free dimer coverings).
Felix Flicker +2 more
doaj +1 more source