Cubic graphs with small independence ratio

MaRDI QIDQ1733918zbMATH OpenFDO

Authors József Balogh, Xujun Liu, Alexandr Kostochka

Publication date 22 March 2019

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1708.03996, https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i1p43

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35)

Abstract: Let $i(r,g)$ denote the infimum of the ratio $fracalpha(G)|V(G)|$ over the $r$-regular graphs of girth at least $g$, where $alpha(G)$ is the independence number of $G$, and let $i(r,infty):=limlimit{s}_{goinfty}i(r,g)$. Recently, several new lower bounds of $i(3,infty)$ were obtained. In particular, Hoppen and Wormald showed in 2015 that $i(3,infty)ge0.4375$, and Cs'oka improved it to $i(3,infty)ge0.44533$ in 2016. Bollob'as proved the upper bound $i(3,infty)<frac613$ in 1981, and McKay improved it to $i(3,infty)<0.45537$ in 1987. There were no improvements since then. In this paper, we improve the upper bound to $i(3,infty)le\mathrm{0.454.}$

Review text

Summary: Let \(i(r,g)\) denote the infimum of the ratio \(\frac{\alpha(G)}{|V(G)|}\) over the \(r\)-regular graphs of girth at least \(g\), where \(\alpha(G)\) is the independence number of \(G\), and let \(i(r,\infty) := \lim\limits_{g \rightarrow \infty} i(r,g)\). Recently, several new lower bounds of \(i(3,\infty)\) were obtained. In particular, \textit{C. Hoppen} and \textit{N. Wormald} showed in [J. Comb. Theory, Ser. B 121, 367--397 (2016; Zbl 1348.05191)] that \(i(3, \infty) \geq 0.4375,\) and \textit{E. Csóka} et al. improved it to \(i(3,\infty) \geq 0.44533\) in [Random Struct. Algorithms 47, No. 2, 284--303 (2015; Zbl 1322.05106)]. \textit{B. Bollobas} proved the upper bound \(i(3,\infty) < \frac{6}{13}\) in [Proc. Am. Math. Soc. 83, 433--436 (1981; Zbl 0474.05057)], and \textit{B. D. McKay} improved it to \(i(3,\infty) < 0.45537\)in [Ars Comb. 23A, 179--185 (1987; Zbl 0644.05028)]. There were no improvements since then. In this paper, we improve the upper bound to \(i(3,\infty) \leq 0.454.\)

Recommendations

• Cubic graphs with large ratio of independent domination number to domination number
• Cubic Cayley graphs with small diameter
• Cubic graphs with equal independence number and matching number
• Independent domination in cubic graphs
• On the cubicity of certain graphs
• scientific article; zbMATH DE number 30759
• A new proof of the independence ratio of triangle-free cubic graphs
• On the independence number of random cubic graphs
• Symmetric cubic graphs of small girth

Cites work

• A note on the independence number of triangle-free graphs. II
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Fractional colorings of cubic graphs with large girth
• Girth and Independence Ratio
• scientific article; zbMATH DE number 4049676 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Induced Forests in Regular Graphs with Large Girth
• Invariant Gaussian processes and independent sets on regular graphs of large girth
• Large independent sets in regular graphs of large girth
• Properties of regular graphs with large girth via local algorithms
• The asymptotic number of labeled graphs with given degree sequences
• The Independence Ratio of Regular Graphs

Cited in

(5)

• Cubic graphs whose average number of regions is small
• Counting independent sets in cubic graphs of given girth
• Entropy and expansion
• Cubic graphs with large ratio of independent domination number to domination number
• Smallest cubic graphs with prescribed properties

This page was built for publication: Cubic graphs with small independence ratio

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