Search engine for discovering works of Art, research articles, and books related to Art and Culture
Javascript must be enabled to continue!
On the number of perfect matchings in random polygonal chains
View through CrossRef
Abstract
Let
G
G
be a graph. A perfect matching of
G
G
is a regular spanning subgraph of degree one. Enumeration of perfect matchings of a (molecule) graph is interest in chemistry, physics, and mathematics. But the enumeration problem of perfect matchings for general graphs (even in bipartite graphs) is non-deterministic polynomial (NP)-hard. Xiao et al. [C. Xiao, H. Chen, L. Liu, Perfect matchings in random pentagonal chains, J. Math. Chem. 55 (2017), 1878–1886] have studied the problem of perfect matchings for random odd-polygonal chain (i.e., with odd polygons). In this article, we further present simple counting formulae for the expected value of the number of perfect matchings in random even-polygonal chains (i.e., with even polygons). Based on these formulae, we obtain the average values of the number for perfect matchings with respect to the set of all even-polygonal chains with
n
n
polygons.
Title: On the number of perfect matchings in random polygonal chains
Description:
Abstract
Let
G
G
be a graph.
A perfect matching of
G
G
is a regular spanning subgraph of degree one.
Enumeration of perfect matchings of a (molecule) graph is interest in chemistry, physics, and mathematics.
But the enumeration problem of perfect matchings for general graphs (even in bipartite graphs) is non-deterministic polynomial (NP)-hard.
Xiao et al.
[C.
Xiao, H.
Chen, L.
Liu, Perfect matchings in random pentagonal chains, J.
Math.
Chem.
55 (2017), 1878–1886] have studied the problem of perfect matchings for random odd-polygonal chain (i.
e.
, with odd polygons).
In this article, we further present simple counting formulae for the expected value of the number of perfect matchings in random even-polygonal chains (i.
e.
, with even polygons).
Based on these formulae, we obtain the average values of the number for perfect matchings with respect to the set of all even-polygonal chains with
n
n
polygons.
Related Results
Seismic characteristics of polygonal fault systems in the Great South Basin, New Zealand
Seismic characteristics of polygonal fault systems in the Great South Basin, New Zealand
Abstract
A well-developed multi-tier polygonal fault system is located in the Great South Basin offshore New Zealand’s South Island. The system has been characterise...
Research on Wheel Polygonal Wear of Metro Vehicles Based on Wheel/Rail Vertical Coupling
Research on Wheel Polygonal Wear of Metro Vehicles Based on Wheel/Rail Vertical Coupling
Wheel polygonal wear is a critical form of non-uniform tread degradation in metro systems, leading to abnormal vibration, noise, and accelerated deterioration of wheel-rail compone...
Parallelization of sequential algorithms
Parallelization of sequential algorithms
Abstract
In this chapter we show several implementations of sequential algorithms. Unfortunately in the case of parallel matchings such an approach does not usually ...
Polygonal spatiotemporal optical vortices wavepackets with a prescribed vortex structure
Polygonal spatiotemporal optical vortices wavepackets with a prescribed vortex structure
Spatiotemporal optical vortices (STOVs) are a type of light beams that carry transverse orbital angular momentum (T-OAM), enabling the generation and control of additional degrees ...
Disjoint Compatibility Graph of Non-Crossing Matchings of Points in Convex Position
Disjoint Compatibility Graph of Non-Crossing Matchings of Points in Convex Position
Let $X_{2k}$ be a set of $2k$ labeled points in convex position in the plane. We consider geometric non-intersecting straight-line perfect matchings of $X_{2k}$. Two such matchings...
Popular Critical Matchings in the Many-to-Many Setting
Popular Critical Matchings in the Many-to-Many Setting
We consider the many-to-many bipartite matching problem in the presence of two-sided preferences and two-sided lower quotas. The input to our problem is a bipartite graph G=(A U B,...
Construction Period and Characteristics of Polygonal Buildings during the Three Kingdoms to the Unified Silla Dynasty Periods
Construction Period and Characteristics of Polygonal Buildings during the Three Kingdoms to the Unified Silla Dynasty Periods
The polygonal buildings from the Three Kingdoms Period are deemed related to religious buildings associated with temples, namely wooden pagodas. With the investigation of a presume...
Parallel algorithms for f-matchings
Parallel algorithms for f-matchings
Abstract
In this chapter we present randomized and deterministic NC-algorithms for maximum and (inclusion) maximal f-matchings (which are natural generalizations of ...