Large induced distance matchings in certain sparse random graphs
Given a graph \(G\) and a distance \(k\), a set of edges \(M_k \subseteq E(G)\) is said to form a distance \(k\)-matching if no two members of \(M_k\) are at distance at most \(k\) in \(G\).\N\NThe authors study the asymptotics of distance matchings in random graphs and more specifically, in graphs sampled from \(\mathbb{G}(n,C/n)\), where \(C>0\) is some sufficiently large constant.\N\N\textit{R. J. Kang} and \textit{P. Manggala} [Discrete Appl. Math. 160, No. 16--17, 2435--2439 (2012; Zbl 1329.05111)] proved that given \(k \geq 2\) a graph \(G \sim \mathbb{G}(n,C/n)\) asymptotically almost surely has the property that distance \(k\)-matchings have size at most \(\left(1+o(1) \right)\frac{kn \log c}{2c^{k-1}}\). For \(k=2\), \textit{O. Cooley} et al. [SIAM J. Discrete Math. 35, No. 1, 267--280 (2021; Zbl 1459.05297)] proved that this bound is, in fact, tight. Here, the authors venture further and establish that \(G \sim \mathbb{G}(n,C/n)\) asymptotically almost surely has the property that distance \(k\)-matchings have size at least \(\left(1+o(1) \right)\frac{kn \log c}{4c^{k-1}}\), whenever \(k \geq 3\).
- Bounding the strong chromatic index of dense random graphs
- Distance edge-colourings and matchings
- Existence of rainbow matchings in strongly edge-colored graphs
- scientific article; zbMATH DE number 731847 (Why is no real title available?)
- scientific article; zbMATH DE number 6960780 (Why is no real title available?)
- Induced matchings
- Induced matchings in subcubic graphs
- Large induced matchings in random graphs
- The distance-t chromatic index of graphs
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
- The Strong Chromatic Index of Random Graphs
- The strong matching number of a random graph
This page was built for publication: Large induced distance matchings in certain sparse random graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6993728)
