In the model of randomly perturbed graphs we consider union a deterministic graph $\mathcal{G}_\alpha$ with minimum degree $\alpha n$ and binomial random $\mathbb{G}(n,p)$. This was introduced by Bohman, Frieze, Martin for Hamilton cycles their result bridges gap between Dirac's theorem results Pósa Korshunov on threshold in this note extend $\mathcal{G}_\alpha\cup\mathbb{G}(n,p)$ to sparser $\alpha=o(1)$. More precisely, any $\varepsilon>0$ \colon \mathbb{N} \mapsto (0,1)$ show that...

Abstract We prove a conjecture by Garbe et al. [arXiv:2010.07854] showing that Latin square is quasirandom if and only the density of every pattern . This result best possible in sense cannot be replaced with or for any n

In the early 1980s, Erdős and Sós initiated study of classical Turán problem with a uniformity condition: uniform density hypergraph <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper H"> <mml:semantics> <mml:mi>H</mml:mi> <mml:annotation encoding="application/x-tex">H</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is infimum over all alttext="d"> <mml:mi>d</mml:mi>...

Abstract A graph is 1‐ planar if it has a drawing in the plane such that each edge crossed at most once by another edge. Moreover, this additional property for crossing of two edges end vertices these induce complete subgraph, then locally maximal . For 3‐connected 1‐planar G , we show existence spanning subgraph and prove Hamiltonian three 3‐vertex‐cuts, traceable four 3‐vertex‐cuts. infinitely many nontraceable 5‐connected graphs are presented.

For a graph $G$ with vertex set $V(G)$ and independence number $\alpha(G)$, S. M. Selkow (Discrete Mathematics, 132(1994)363--365) established the famous lower bound $\sum\limits_{v\in V(G)}\frac{1}{d(v)+1}(1+\max\{\frac{d(v)}{d(v)+1}-\sum\limits_{u\in N(v)}\frac{1}{d(u)+1},0 \})$ on where $N(v)$ $d(v)=|N(v)|$ denote neighborhood degree of $v\in V(G)$, respectively. However, Selkow's original proof this result is incorrect. We give new probabilistic here.

A planar 3-connected graph G is called essentially 4-connected if, for every 3-separator S, at least one of the two components -S an isolated vertex.Jackson and Wormald proved that length circ(G) a longest cycle any on n vertices 2n+4 5 Fabrici, Harant Jendrol' improved this result to ≥ 1 2 (n + 4).In present paper, we prove contains 3 2) such can be found in time O(n ).

A planar graph is essentially $4$-connected if it 3-connected and every of its 3-separators the neighborhood a single vertex. Jackson Wormald proved that 4-connected $G$ on $n$ vertices contains cycle length at least $\frac{2n+4}{5}$, this result has recently been improved multiple times. In paper, we prove $\frac{5}{8}(n+2)$. This improves previously best-known lower bound $\frac{3}{5}(n+2)$.

A $3$-connected graph $G$ is essentially $4$-connected if, for any $3$-cut $S\subseteq V(G)$ of $G$, at most one component $G-S$ contains least two vertices. We prove that every maximal planar on $n$ vertices a cycle length $\frac{2}{3}(n+4)$; moreover, this bound sharp.

Abstract Results on the existence of various types spanning subgraphs graphs are milestones in structural graph theory and have been diversified several directions. In present paper, we consider “local” versions such statements. 1966, for instance, D. W. Barnette proved that a 3‐connected planar contains tree maximum degree at most 3. A local translation this statement is if graph, subset specified vertices cannot be separated by removing two or fewer , then has 3 containing all . Our...

A planar graph is essentially $4$-connected if it 3-connected and every of its 3-separators the neighborhood a single vertex. Jackson Wormald proved that 4-connected $G$ on $n$ vertices contains cycle length at least $\frac{2n+4}{5}$, this result has recently been improved multiple times. In paper, we prove $\frac{5}{8}(n+2)$. This improves previously best-known lower bound $\frac{3}{5}(n+2)$.

A (minimal) transversal of a partition is set which contains exactly one element from each member the and nothing else. coloring graph its vertex into anticliques, that is, sets pairwise nonadjacent vertices. We study following problem: Given $T$ proper $\mathfrak{C}$ some $G$, there $\mathfrak{H}$ subset $V(G)$ connected such two are adjacent if their corresponding vertices by path in $G$ using only colors? It has been suggested first author to question: for any order $k$ pair color classes...

We propose new bounds on the domination number and independence of a graph show that our compare favorably to recent ones. Our are obtained by using Bhatia-Davis inequality linking variance, expected value, minimum, maximum random variable with bounded distribution.

We prove a conjecture by Garbe et al. [arXiv:2010.07854] showing that Latin square is quasirandom if and only the density of every 2x3 pattern 1/720+o(1). This result best possible in sense cannot be replaced with 2x2 or 1xN for any N.

In the model of randomly perturbed graphs we consider union a deterministic graph $\mathcal{G}_\alpha$ with minimum degree $\alpha n$ and binomial random $\mathbb{G}(n,p)$. This was introduced by Bohman, Frieze, Martin for Hamilton cycles their result bridges gap between Dirac's theorem results Pos\'{a} Kor\v{s}unov on threshold in this note extend $\mathcal{G}_\alpha \cup \mathbb{G}(n,p)$ to sparser $\alpha=o(1)$. More precisely, any $\varepsilon>0$ \colon \mathbb{N} \mapsto (0,1)$ show...