Maximum matchings in scale-free networks with identical degree distribution

Abstract

The size and number of maximum matchings in a network have found a large variety of applications in many fields. As a ubiquitous property of diverse real systems, power-law degree distribution was shown to have a profound influence on size of maximum matchings in scale-free networks, where the size of maximum matchings is small and a perfect matching often does not exist. In this paper, we study analytically the maximum matchings in two scale-free networks with identical degree sequence, and show that the first network has no perfect matchings, while the second one has many. For the first network, we determine explicitly the size of maximum matchings, and provide an exact recursive solution for the number of maximum matchings. For the second one, we design an orientation and prove that it is Pfaffian, based on which we derive a closed-form expression for the number of perfect matchings. Moreover, we demonstrate that the entropy for perfect matchings is equal to that corresponding to the extended Sierpiński graph with the same average degree as both studied scale-free networks. Our results indicate that power-law degree distribution alone is not sufficient to characterize the size and number of maximum matchings in scale-free networks.

References in corpus (15)

• Emergence of scaling in random networks
• The structure and function of complex networks
• Assortative mixing in networks
• Self-similarity of complex networks
• Dynamical and correlation properties of the Internet
• How to calculate the fractal dimension of a complex network: the box covering algorithm
• The number of matchings in random graphs
• Inverted Berezinskii-Kosterlitz-Thouless Singularity and High-Temperature Algebraic Order in an Ising Model on a Scale-Free Hierarchical-Lattice Small-World Network
• Self-similarity, small-world, scale-free scaling, disassortativity, and robustness in hierarchical lattices
• Dimers on two-dimensional lattices
• Farey Graphs as Models for Complex Networks
• Enumeration of Matchings: Problems and Progress
• The number and degree distribution of spanning trees in the Tower of Hanoi graph
• Different thresholds of bond percolation in scale-free networks with identical degree sequence
• Counting dimer coverings on self-similar Schreier graphs

Cited by in corpus (7)

• Maximum matchings and minimum dominating sets in Apollonian networks and extended Tower of Hanoi graphs
• Phase Transitions between Different Spin-Glass Phases and between Different Chaoses in Quenched Random Chiral Systems
• Topologically robust zero-sum games and Pfaffian orientation -- How network topology determines the long-time dynamics of the antisymmetric Lotka-Volterra equation
• A Lower Lower-Critical Spin-Glass Dimension from Quenched Mixed-Spatial-Dimensional Spin Glasses
• Spectra, hitting times, and resistance distances of $q$-subdivision graphs
• Maximally Random Discrete-Spin Systems with Symmetric and Asymmetric Interactions and Maximally Degenerate Ordering
• Some Combinatorial Problems in Power-law Graphs