On the b -Independence Number of Sparse Random Graphs

DOI10.1017/S0963548304006108MaRDI QIDQ4819243zbMATH OpenOpenAlexWikidataFDO

Authors Geoffrey Atkinson, Alan Frieze

Publication date 24 September 2004

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/s0963548304006108

zbMATH Keywords

\(b\)-independence numberrandom graphs

Mathematics Subject Classification ID

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

Review text

Consider a graph \(G = (V, E)\). A subset \(S\) of \(V\) is said to be \(b\)-independent (where \(b\) is an integer at least 1) if \(u, v\in S\) implies \(d_G\) \((u, v) > b\), where \(d_G(u,v)\) is the least distance in the graph \(G\) between the vertices \(u, v\). The size of the largest \(b\)-independent subset of \(G\) is called its \(b\)-independence number and is denoted by \(\alpha_b(G)\). This paper is concerned with this parameter in relation to the random graphs \(G_{n,p}\) \((p =\frac dn\) when \(d\) is a largest constant). The main result of this paper is as follows: Let \(b\) be a positive integer constant and let \(\varepsilon > 0\) be given. Assume that \(d\) is a constant, greater than some fixed \(d_{e,b}\). Then with high probability we have \[ \left| \alpha_b(G_{n,p})-\frac{2bn}{d^b}\left(\log d -\frac{\log\log d}{b}-\frac{\log 2b}{b}+\frac 1b\right)\right|\leq \frac{\varepsilon n}{d^b}. \]

Recommendations

• On the independence number of sparse graphs
• Independence numbers of random sparse hypergraphs
• On the independence number of random graphs
• Independent sets in random sparse graphs
• On Counting Independent Sets in Sparse Graphs
• On the independence number of random interval graphs
• New lower bounds for the independence number of sparse graphs and hypergraphs
• scientific article; zbMATH DE number 5532162

Cited in

(10)

• Revisit the Lovász local lemma
• Optimization of eigenvalue bounds for the independence and chromatic number of graph powers
• On inertia and ratio type bounds for the k-independence number of a graph and their relationship
• On distance edge-colourings and matchings
• On the Lovász Theta Function for Independent Sets in Sparse Graphs
• Spectral bounds for the \(k\)-independence number of a graph
• On trees with given diameter and extremal number of distance-k independent sets
• Algebraic bounds for the independence and chromatic number of graph powers
• On the k-independence number of graph products
• Distance edge-colourings and matchings

This page was built for publication: On the $b$ -Independence Number of Sparse Random Graphs

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