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

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

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item