Maximum matchings and minimum dominating sets in Apollonian networks and extended tower of Hanoi graphs

DOI10.1016/j.tcs.2017.08.024zbMath1380.05182arXiv1709.04404OpenAlexW2752776682MaRDI QIDQ1676361

Yujia Jin, Zhong-Zhi Zhang, Hu-An Li

Publication date: 7 November 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1709.04404

zbMATH Keywords

matching numbermaximum matchingdomination numbercomplex networkminimum dominating setApollonian networktower of Hanoi graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (5)

MAXIMUM MATCHINGS IN A PSEUDOFRACTAL SCALE-FREE WEB ⋮ Enumeration of maximum matchings in the Hanoi graphs using matching polynomials ⋮ Modeling spatial networks by contact graphs of disk packings ⋮ Some two-vertex resistances of the three-towers Hanoi graph formed by a fractal graph ⋮ EDGE DOMINATION NUMBER AND THE NUMBER OF MINIMUM EDGE DOMINATING SETS IN PSEUDOFRACTAL SCALE-FREE WEB AND SIERPIŃSKI GASKET

Cites Work

• Unnamed Item
• Unnamed Item
• Enumerating minimal connected dominating sets in graphs of bounded chordality
• Inapproximability of dominating set on power law graphs
• On the number of minimal dominating sets on some graph classes
• A survey and classification of Sierpiński-type graphs
• Domination number and minimum dominating sets in pseudofractal scale-free web and Sierpiński graph
• Maximum matchings in scale-free networks with identical degree distribution
• Applications of graphical condensation for enumerating matchings and tilings
• The complexity of computing the permanent
• Graphical condensation of plane graphs: a combinatorial approach
• Spanning trees on the Sierpinski gasket
• Dimer coverings on the Sierpinski gasket
• Exact and asymptotic enumeration of perfect matchings in self-similar graphs
• Matching theory
• Graphical condensation for enumerating perfect matchings
• Error-correcting codes on the Towers of Hanoi graphs
• Maximum matching in regular and almost regular graphs
• A quadratic identity for the number of perfect matchings of plane graphs
• Enumeration problems for classes of self-similar graphs
• The number of spanning trees in Apollonian networks
• Efficient sub-5 approximations for minimum dominating sets in unit disk graphs
• Codes and \(L(2,1)\)-labelings in Sierpiński graphs
• Pfaffian orientations and perfect matchings of scale-free networks
• The degree profile and weight in Apollonian networks and k-trees
• The Tower of Hanoi – Myths and Maths
• Applications of Perfect Matchings in Chemistry
• Emergence of Scaling in Random Networks
• Enumeration of spanning trees on Apollonian networks
• Finding a maximum matching in a sparse random graph in O ( n ) expected time
• The Complexity of Enumeration and Reliability Problems
• Perfect codes on the towers of Hanoi graph
• A Survey of Combinatorial Gray Codes
• The Structure and Function of Complex Networks
• On Estimating Maximum Matching Size in Graph Streams
• 1-perfect codes in Sierpiński graphs
• Combinatorial bounds via measure and conquer
• Collective dynamics of ‘small-world’ networks
• Crossing numbers of Sierpiński‐like graphs
• Dimer–monomer model on the Towers of Hanoi graphs

This page was built for publication: Maximum matchings and minimum dominating sets in Apollonian networks and extended tower of Hanoi graphs