Large Cliques in a Power-Law Random Graph

DOI10.1239/JAP/1294170524zbMath1214.05156arXiv0905.0561OpenAlexW2090814296MaRDI QIDQ3067852

Svante Janson, Tomasz Łuczak, Ilkka Norros

Publication date: 13 January 2011

Published in: Journal of Applied Probability (Search for Journal in Brave)

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

zbMATH Keywords

greedy algorithmcliquepower-law random graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (18)

Finding Induced Subgraphs in Scale-Free Inhomogeneous Random Graphs ⋮ Large communities in a scale-free network ⋮ Inhomogeneous long-range percolation on the hierarchical lattice ⋮ Phase transitions in a power-law uniform hypergraph ⋮ On the distances within cliques in a soft random geometric graph ⋮ New techniques for approximating optimal substructure problems in power-law graphs ⋮ Dense subgraphs of power-law random graphs ⋮ Large cliques in sparse random intersection graphs ⋮ Potential energy principles in networked systems and their connections to optimization problems on graphs ⋮ Cliques in rank-1 random graphs: the role of inhomogeneity ⋮ Cliques in hyperbolic random graphs ⋮ Number of edges in inhomogeneous random graphs ⋮ Superlogarithmic Cliques in Dense Inhomogeneous Random Graphs ⋮ Large dicliques in a directed inhomogeneous random graph ⋮ Parameterized clique on inhomogeneous random graphs ⋮ Clustering in preferential attachment random graphs with edge-step ⋮ New analytical lower bounds on the clique number of a graph ⋮ Distinguishing power-law uniform random graphs from inhomogeneous random graphs through small subgraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Generating simple random graphs with prescribed degree distribution
• Number of cliques in random scale-free network ensembles
• Distance in random graphs with infinite mean degrees
• Connected components in random graphs with given expected degree sequences
• The phase transition in inhomogeneous random graphs
• On a conditionally Poissonian graph process
• The Small Giant Component in Scale-Free Random Graphs

This page was built for publication: Large Cliques in a Power-Law Random Graph