Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpiński gasket

DOI10.1016/J.TCS.2018.02.022MaRDI QIDQ1704581zbMATH OpenOpenAlexFDO

Authors Liren Shan, Hu-An Li, Zhongzhi Zhang

Publication date 12 March 2018

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

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

zbMATH Keywords

complex networkindependence numbermaximum independent setminimum vertex coverscale-free networkSierpiński gasket

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: As a fundamental subject of theoretical computer science, the maximum independent set (MIS) problem not only is of purely theoretical interest, but also has found wide applications in various fields. However, for a general graph determining the size of a MIS is NP-hard, and exact computation of the number of all MISs is even more difficult. It is thus of significant interest to seek special graphs for which the MIS problem can be exactly solved. In this paper, we address the MIS problem in the pseudofractal scale-free web and the Sierpi'nski gasket, which have the same number of vertices and edges. For both graphs, we determine exactly the independence number and the number of all possible MISs. The independence number of the pseudofractal scale-free web is as twice as the one of the Sierpi'nski gasket. Moreover, the pseudofractal scale-free web has a unique MIS, while the number of MISs in the Sierpi'nski gasket grows exponentially with the number of vertices.

Recommendations

• Domination number and minimum dominating sets in pseudofractal scale-free web and Sierpiński graph
• Maximum matchings in a pseudofractal scale-free web
• Edge domination number and the number of minimum edge dominating sets in pseudofractal scale-free web and Sierpiński gasket
• scientific article; zbMATH DE number 1305487
• The complexity of some problems on maximal independent sets in graphs

Cites work

• A priori optimization for the probabilistic maximum independent set problem
• A sufficient condition to extend polynomial results for the maximum independent set problem
• Algorithms for maximum independent sets
• An exact algorithm for maximum independent set in degree-5 graphs
• Confining sets and avoiding bottleneck cases: a simple maximum independent set algorithm in degree-3 graphs
• Domination number and minimum dominating sets in pseudofractal scale-free web and Sierpiński graph
• Emergence of Scaling in Random Networks
• Exact exponential algorithms.
• Fast local search for the maximum independent set problem
• Finding a maximal weighted independent set in wireless networks
• Finding a Maximum Independent Set
• Graphs with unique maximum independent sets
• Greed is good: Approximating independent sets in sparse and bounded-degree graphs
• scientific article; zbMATH DE number 1003268 (Why is no real title available?)
• Inapproximability of dominating set on power law graphs
• Matching theory
• Maximum independent set and maximum clique algorithms for overlap graphs
• On maximum independent set of categorical product and ultimate categorical ratios of graphs
• On the hardness of optimization in power-law graphs
• On the maximum independent set problem in subclasses of subcubic graphs
• Pfaffian orientations and perfect matchings of scale-free networks
• Reducibility among combinatorial problems
• SDP-based algorithms for maximum independent set problems on hypergraphs
• The average distances in random graphs with given expected degrees
• The complexity of computing the permanent
• The Complexity of Enumeration and Reliability Problems
• The maximum clique problem
• The resolution complexity of independent sets and vertex covers in random graphs
• The Structure and Function of Complex Networks

Cited in

(6)

• Random walks on Fibonacci treelike models
• Combinatorial properties of Farey graphs
• Edge domination number and the number of minimum edge dominating sets in pseudofractal scale-free web and Sierpiński gasket
• Maximum matchings in a pseudofractal scale-free web
• Domination number and minimum dominating sets in pseudofractal scale-free web and Sierpiński graph
• COMBINATORIAL PROPERTIES FOR A CLASS OF SIMPLICIAL COMPLEXES EXTENDED FROM PSEUDO-FRACTAL SCALE-FREE WEB

This page was built for publication: Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpiński gasket

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1704581)