Pfaffian orientations and perfect matchings of scale-free networks. (English) Zbl 1306.05198
Summary: Counting perfect matchings is of great interest in theoretical computer science, mathematics, among other disciplines. However, explicitly determining the number of perfect matchings of general graphs is a challenge. In this paper, we present a first analytical study of the enumeration problem of perfect matchings on scale-free networks, which are ubiquitous in real-life systems. We focus on two iteratively growing scale-free networks: one is fractal, while the other is non-fractal. For each network, we construct an orientation and prove that it is Pfaffian. Then, based on the connection between the number of perfect matchings and determinant of the skew adjacency matrix corresponding to a Pfaffian orientation, we derive the recursive expressions for the number of perfect matchings of the networks at two successive iterations. Furthermore, using the recursive relations, we show that for both scale-free networks, their entropy is zero, which is in sharp contrast to the previously obtained results for other networks without scale-free behavior, but having the same average degree as the studied networks, such as square lattice and honeycomb lattice, whose entropies are larger than zero. Our results indicate from another angle that scale-free networks have a distinct architecture in comparison with those lattices lacking the power-law property.
MSC:
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05C82 | Small world graphs, complex networks (graph-theoretic aspects) |
References:
| [1] | McHugh, J., Algorithmic Graph Theory (1990), Prentice Hall · Zbl 0755.68056 |
| [2] | Montroll, E. W., Lattice statistics, (Beckenbach, E., Applied Combinatorial Mathematics (1964), Wiley: Wiley New York), 96-143 · Zbl 0141.15503 |
| [3] | Trinajstic, N., Chemical Graph Theory (1992), CRC Press: CRC Press Boca Raton, Florida |
| [4] | Lovász, L.; Plummer, M. D., Matching Theory, Annals of Discrete Mathematics, vol. 29 (1986), North-Holland: North-Holland New York · Zbl 0618.05001 |
| [5] | Kasteleyn, P. W., The statistics of dimers on a lattice: I. The number of dimer arrangements on a quadratic lattice, Physica, 27, 1209-1225 (1961) · Zbl 1244.82014 |
| [6] | Vukičević, D., Applications of perfect matchings in chemistry, (Dehmer, M., Structural Analysis of Complex Networks (2011), Birkhäuser: Birkhäuser Boston), 463-482 · Zbl 1221.05272 |
| [7] | Fisher, M. E., On the dimer solution of planar Ising models, J. Math. Phys., 7, 1776-1781 (1966) |
| [8] | Green, H. S.; Hurst, C. A., Order-Disorder Phenomena (1964), Interscience Publishers: Interscience Publishers New York · Zbl 0138.22301 |
| [9] | Swinbome-Sheldrake, R.; Herndon, W.; Gutman, I., Kekulé structures and resonance energies of benzenoid hydrocarbons, Tetrahedron Lett., 16, 755-758 (1975) |
| [10] | Cioslowski, J., The generalized McClelland formula, MATCH Commun. Math. Comput. Chem., 20, 95-101 (1986) |
| [11] | Valiant, L., The complexity of computing the permanent, Theoret. Comput. Sci., 8, 189-201 (1979) · Zbl 0415.68008 |
| [12] | Valiant, L., The complexity of enumeration and reliability problems, SIAM J. Comput., 8, 410-421 (1979) · Zbl 0419.68082 |
| [13] | Yan, W.; Zhang, F., Enumeration of perfect matchings of graphs with reflective symmetry by Pfaffians, Adv. Appl. Math., 32, 655-668 (2004) · Zbl 1053.05065 |
| [14] | Robertson, N.; Seymour, P.; Thomas, R., Permanents, Pfaffian orientations, and even directed circuits, Ann. Math., 150, 929-976 (1999) · Zbl 0947.05066 |
| [15] | Yan, W.; Zhang, F., Enumeration of perfect matchings of a type of Cartesian products of graphs, Discrete Appl. Math., 154, 145-157 (2006) · Zbl 1083.05035 |
| [16] | Yan, W.; Zhang, F., A quadratic identity for the number of perfect matchings of plane graphs, Theoret. Comput. Sci., 409, 405-410 (2008) · Zbl 1171.05041 |
| [17] | Propp, J., Enumeration of matchings: problems and progress, (Billera, L.; Björner, A.; Greene, C.; Simeon, R.; Stanley, R. P., New Perspectives in Geometric Combinatorics (1999), Cambridge University Press: Cambridge University Press Cambridge), 255-291 · Zbl 0937.05065 |
| [18] | D’Angeli, D.; Donno, A.; Nagnibeda, T., Counting dimer coverings on self-similar Schreier graphs, European J. Combin., 33, 1484-1513 (2012) · Zbl 1246.05128 |
| [19] | Mahajan, M.; Varadarajan, K. R., A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs, (Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing. Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, STOC, Portland, OR, USA (2000)), 351-357 · Zbl 1296.05187 |
| [20] | Vazirani, V. V., NC algorithms for computing the number of perfect matchings in \(K_{3, 3}\)-free graphs and related problems, Inform. Comput., 80, 152-164 (1989) · Zbl 0673.05075 |
| [21] | Kuo, E. H., Applications of graphical condensation for enumerating matchings and tilings, Theoret. Comput. Sci., 319, 29-57 (2004) · Zbl 1043.05099 |
| [22] | Yan, W.; Yeh, Y.-N.; Zhang, F., Graphical condensation of plane graphs: a combinatorial approach, Theoret. Comput. Sci., 349, 452-461 (2005) · Zbl 1086.05066 |
| [23] | Li, W.; Zhang, H., Dimer statistics of honeycomb lattices on Klein bottle, Möbius strip and cylinder, Phys. A, 391, 3833-3848 (2012) |
| [24] | Lu, F.; Zhang, L., Dimers on two types of lattices on the Klein bottle, J. Phys. A, 45, 494012 (2012) · Zbl 1257.82027 |
| [25] | Barabási, A.; Albert, R., Emergence of scaling in random networks, Science, 286, 509-512 (1999) · Zbl 1226.05223 |
| [26] | Zhang, Z.; Wu, B.; Comellas, F., The number of spanning trees in Apollonian networks, Discrete Appl. Math., 169, 206-213 (2014) · Zbl 1288.05066 |
| [27] | Zhang, Z.; Liu, H.; Wu, B.; Zou, T., Spanning trees in a fractal scale-free lattice, Phys. Rev. E, 83, 016116 (2011) |
| [28] | Miralles, A.; Comellas, F.; Chen, L.; Zhang, Z., Planar unclustered scale-free graphs as models for technological and biological networks, Phys. A, 389, 1955-1964 (2010) |
| [29] | Temperley, H.; Fisher, M., Dimer problem in statistical mechanics - an exact result, Philos. Mag., 6, 1061-1063 (1961) · Zbl 0126.25102 |
| [30] | Newman, M. E., Power laws, Pareto distributions and Zipf’s law, Contemp. Phys., 46, 323-351 (2005) |
| [31] | Newman, M. E.J., The structure and function of complex networks, SIAM Rev., 45, 167-256 (2003) · Zbl 1029.68010 |
| [32] | Watts, D.; Strogatz, S., Collective dynamics of ‘small-world’ networks, Nature, 393, 440-442 (1998) · Zbl 1368.05139 |
| [33] | Song, C.; Havlin, S.; Makse, H., Self-similarity of complex networks, Nature, 433, 392-395 (2005) |
| [34] | Song, C.; Gallos, L. K.; Havlin, S.; Makse, H. A., How to calculate the fractal dimension of a complex network: the box covering algorithm, J. Stat. Mech. Theory Exp., 2007, P03006 (2007) |
| [35] | Kim, J. S.; Goh, K.-I.; Kahng, B.; Kim, D., Fractality and self-similarity in scale-free networks, New J. Phys., 9, 177 (2007) |
| [36] | Kasteleyn, P. W., Dimer statistics and phase transitions, J. Math. Phys., 4, 287-293 (1963) |
| [37] | Kasteleyn, P. W., Graph theory and crystal physics, (Harary, F., Graph Theory and Theoretical Physics (1967), Academic Press), 43-110 · Zbl 0205.28402 |
| [38] | Wu, F. Y., Dimers on two-dimensional lattices, Internat. J. Modern Phys. B, 20, 5357-5371 (2006) · Zbl 1106.82009 |
| [39] | Wu, F. Y., Dimers and spanning trees: some recent results, Internat. J. Modern Phys. B, 16, 1951-1962 (2002) · Zbl 1073.82529 |
| [40] | Watts, D. J.; Strogatz, S. H., Collective dynamics of ‘small-world’ networks, Nature, 393, 440-442 (1998) · Zbl 1368.05139 |
| [41] | Small, M.; Xu, X.; Zhou, J.; Zhang, J.; Sun, J.; Lu, J.-A., Scale-free networks which are highly assortative but not small world, Phys. Rev. E, 77, 066112 (2008) |
| [42] | Lin, F.; Zhang, L., Pfaffian orientation and enumeration of perfect matchings for some Cartesian products of graphs, Electron. J. Combin., 16, R52 (2009) · Zbl 1180.05054 |
| [43] | Phares, A.; Wunderlich, F., Thermodynamics and molecular freedom of dimers on plane honeycomb and Kagomé lattices, Nuovo Cimento B, 101, 653-686 (1988) |
| [44] | Liu, Y.-Y.; Slotine, J.-J.; Barabási, A.-L., Controllability of complex networks, Nature, 473, 167-173 (2011) |
| [45] | Zdeborová, L.; Mézard, M., The number of matchings in random graphs, J. Stat. Mech. Theory Exp., 2006, P05003 (2006) · Zbl 1456.05153 |
| [46] | Karp, R. M.; Sipser, M., Maximum matching in sparse random graphs, (IEEE 54th Annual Symposium on Foundations of Computer Science (1981), IEEE), 364-375 |
| [47] | Chaiken, S., A combinatorial proof of the all minors matrix tree theorem, SIAM J. Algebra Discrete Math., 3, 319-329 (1982) · Zbl 0495.05018 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
