More Like this

1. Independent dominating sets in graphs of girth five

   https://doi.org/10.1017/s0963548320000279  

   Harutyunyan, Ararat; Horn, Paul; Verstraete, Jacques (May 2021, Combinatorics, Probability and Computing)

   Abstract Let $$\gamma(G)$$ and $${\gamma _ \circ }(G)$$ denote the sizes of a smallest dominating set and smallest independent dominating set in a graph G, respectively. One of the first results in probabilistic combinatorics is that if G is an n -vertex graph of minimum degree at least d , then $$\begin{equation}\gamma(G) \leq \frac{n}{d}(\log d + 1).\end{equation}$$ In this paper the main result is that if G is any n -vertex d -regular graph of girth at least five, then $$\begin{equation}\gamma_(G) \leq \frac{n}{d}(\log d + c)\end{equation}$$ for some constant c independent of d . This result is sharp in the sense that as $$d \rightarrow \infty$$ , almost all d -regular n -vertex graphs G of girth at least five have $$\begin{equation}\gamma_(G) \sim \frac{n}{d}\log d.\end{equation}$$ Furthermore, if G is a disjoint union of $${n}/{(2d)}$$ complete bipartite graphs $$K_{d,d}$$ , then $${\gamma_\circ}(G) = \frac{n}{2}$$ . We also prove that there are n -vertex graphs G of minimum degree d and whose maximum degree grows not much faster than d log d such that $${\gamma_\circ}(G) \sim {n}/{2}$$ as $$d \rightarrow \infty$$ . Therefore both the girth and regularity conditions are required for the main result. 

   more » « less
2. An Ore-Type Condition for Hamiltonicity in Tough Graphs and the Extremal Examples

   https://doi.org/10.37236/12483  

   Sanka, Masahiro; Shan, Songling (January 2024, The Electronic Journal of Combinatorics)

   Let $$G$$ be a $$t$$-tough graph on $$n\ge 3$$ vertices for some $t>0$. It was shown by Bauer et al. in 1995 that if the minimum degree of $$G$$ is greater than $$\frac{n}{t+1}-1$$, then $$G$$ is hamiltonian. In terms of Ore-type hamiltonicity conditions, the problem was only studied when $$t$$ is between 1 and 2, and recently the second author proved a general result. The result states that if the degree sum of any two nonadjacent vertices of $$G$$ is greater than $$\frac{2n}{t+1}+t-2$$, then $$G$$ is hamiltonian. It was conjectured in the same paper that the $+t$ in the bound $$\frac{2n}{t+1}+t-2$$ can be removed. Here we confirm the conjecture. The result generalizes the result by Bauer, Broersma, van den Heuvel, and Veldman. Furthermore, we characterize all $$t$$-tough graphs $$G$$ on $$n\ge 3$$ vertices for which $$\sigma_2(G) = \frac{2n}{t+1}-2$$ but $$G$$ is non-hamiltonian. 

   more » « less
3. Interpolation for Curves in Projective Space with Bounded Error

   https://doi.org/10.1093/imrn/rnz136  

   Larson, Eric (July 2019, International Mathematics Research Notices)

   Abstract Given $$n$$ general points $$p_1, p_2, \ldots , p_n \in{\mathbb{P}}^r$$ it is natural to ask whether there is a curve of given degree $$d$$ and genus $$g$$ passing through them; by counting dimensions a natural conjecture is that such a curve exists if and only if $$\begin{equation*}n \leq \left\lfloor \frac{(r + 1)d - (r - 3)(g - 1)}{r - 1}\right\rfloor.\end{equation*}$$The case of curves with nonspecial hyperplane section was recently studied in [2], where the above conjecture was shown to hold with exactly three exceptions. In this paper, we prove a “bounded-error analog” for special linear series on general curves; more precisely we show that existence of such a curve subject to the stronger inequality $$\begin{equation*}n \leq \left\lfloor \frac{(r + 1)d - (r - 3)(g - 1)}{r - 1}\right\rfloor - 3.\end{equation*}$$Note that the $-3$ cannot be replaced with $-2$ without introducing exceptions (as a canonical curve in $${\mathbb{P}}^3$$ can only pass through nine general points, while a naive dimension count predicts twelve). We also use the same technique to prove that the twist of the normal bundle $$N_C(-1)$$ satisfies interpolation for curves whose degree is sufficiently large relative to their genus, and deduce from this that the number of general points contained in the hyperplane section of a general curve is at least $$\begin{equation*}\min\left(d, \frac{(r - 1)^2 d - (r - 2)^2 g - (2r^2 - 5r + 12)}{(r - 2)^2}\right).\end{equation*}$$ As explained in [7], these results play a key role in the author’s proof of the maximal rank conjecture [9]. 

   more » « less
4. Irregular subgraphs

   https://doi.org/10.1017/S0963548322000220  

   Alon, Noga; Wei, Fan (March 2023, Combinatorics, Probability and Computing)

   Abstract We suggest two related conjectures dealing with the existence of spanning irregular subgraphs of graphs. The first asserts that any $$d$$ -regular graph on $$n$$ vertices contains a spanning subgraph in which the number of vertices of each degree between $$0$$ and $$d$$ deviates from $$\frac{n}{d+1}$$ by at most $$2$$ . The second is that every graph on $$n$$ vertices with minimum degree $$\delta$$ contains a spanning subgraph in which the number of vertices of each degree does not exceed $$\frac{n}{\delta +1}+2$$ . Both conjectures remain open, but we prove several asymptotic relaxations for graphs with a large number of vertices $$n$$ . In particular we show that if $$d^3 \log n \leq o(n)$$ then every $$d$$ -regular graph with $$n$$ vertices contains a spanning subgraph in which the number of vertices of each degree between $$0$$ and $$d$$ is $$(1+o(1))\frac{n}{d+1}$$ . We also prove that any graph with $$n$$ vertices and minimum degree $$\delta$$ contains a spanning subgraph in which no degree is repeated more than $$(1+o(1))\frac{n}{\delta +1}+2$$ times. 

   more » « less
5. Vertex degree sums for perfect matchings in 3-uniform hypergraphs

   Zhang, Yi and (September 2018, The Electronic journal of combinatorics)

   We determine the minimum degree sum of two adjacent vertices that ensures a perfect matching in a 3-uniform hypergraph without isolated vertex. Suppose that $$H$$ is a 3-uniform hypergraph whose order $$n$$ is sufficiently large and divisible by $$3$$. If $$H$$ contains no isolated vertex and $$\deg(u)+\deg(v) > \frac{2}{3}n^2-\frac{8}{3}n+2$$ for any two vertices $$u$$ and $$v$$ that are contained in some edge of $$H$$, then $$H$$ contains a perfect matching. This bound is tight and the (unique) extremal hyergraph is a different \emph{space barrier} from the one for the corresponding Dirac problem. 

   more » « less