COMBINATORIAL PROPERTIES FOR A CLASS OF SIMPLICIAL COMPLEXES EXTENDED FROM PSEUDO-FRACTAL SCALE-FREE WEB

DOI10.1142/S0218348X23500226zbMATH Open1517.05184arXiv2301.03230MaRDI QIDQ6158062FDOQ6158062

Authors: Yucheng Wang, W. Y. Xu, Wei Li, Zhongzhi Zhang 

Publication date: 22 June 2023

Published in: Fractals (Search for Journal in Brave)

Abstract: Simplicial complexes are a popular tool used to model higher-order interactions between elements of complex social and biological systems. In this paper, we study some combinatorial aspects of a class of simplicial complexes created by a graph product, which is an extension of the pseudo-fractal scale-free web. We determine explicitly the independence number, the domination number, and the chromatic number. Moreover, we derive closed-form expressions for the number of acyclic orientations, the number of root-connected acyclic orientations, the number of spanning trees, as well as the number of perfect matchings for some particular cases.

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

zbMATH Keywords

spanning treessimplicial complexdomination numberchromatic numberperfect matchingindependence numberacyclic orientationscombinatorial problemgraph productpseudo-fractal

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Combinatorial aspects of simplicial complexes (05E45) Fractals (28A80)

Cites Work

• Clique topology reveals intrinsic geometric structure in neural correlations
• Title not available (Why is that?)
• Emergence of Scaling in Random Networks
• The Structure and Function of Complex Networks
• A Contribution to the Theory of Chromatic Polynomials
• Collective dynamics of `small-world' networks
• Matching theory
• On the Interpretation of Whitney Numbers Through Arrangements of Hyperplanes, Zonotopes, Non-Radon Partitions, and Orientations of Graphs
• Algebraic Graph Theory
• The complexity of computing the permanent
• Acyclic orientations of graphs
• The Complexity of Enumeration and Reliability Problems
• The hierarchical product of graphs
• On the number of minimal dominating sets on some graph classes
• Minimum connected dominating sets and maximal independent sets in unit disk graphs
• On Dominating Sets and Independent Sets of Graphs
• Inverted Berezinskii-Kosterlitz-Thouless singularity and high-temperature algebraic order in an Ising model on a scale-free hierarchical-lattice small-world network
• Inapproximability of dominating set on power law graphs
• Matchings and phylogenetic trees
• Maximum matching in regular and almost regular graphs
• Title not available (Why is that?)
• Network science. With Márton Pósfai
• Invariants of E-graphs
• Domination number and minimum dominating sets in pseudofractal scale-free web and Sierpiński graph
• Simplicial complexes and complex systems
• Networks beyond pairwise interactions: structure and dynamics
• Incompatibility networks as models of scale-free small-world graphs
• Maximizing the Number of Spanning Trees in a Connected Graph
• Exact calculations of first-passage properties on the pseudofractal scale-free web
• Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpiński gasket
• On maximum independent set of categorical product and ultimate categorical ratios of graphs
• \(P\)-persistent homology of finite topological spaces
• Applications of E-graphs in network design
• Edge domination number and the number of minimum edge dominating sets in pseudofractal scale-free web and Sierpiński gasket
• The Master Stability Function for Synchronization in Simplicial Complexes
• Lazy random walks on pseudofractal scale-free web with a perfect trap
• Maximum matchings in a pseudofractal scale-free web

This page was built for publication: COMBINATORIAL PROPERTIES FOR A CLASS OF SIMPLICIAL COMPLEXES EXTENDED FROM PSEUDO-FRACTAL SCALE-FREE WEB

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