3-Vertices with fewest 2-neighbors in plane graphs with no long paths of 2-vertices

Let $g(k,t)$ be the minimum integer such that every plane graph with girth g at least $g(k,t)$, minimum degree $\delta =2$ and no $(k+1)$-paths consisting of vertices of degree 2, where $k\ge 1$, has a 3-vertex with at least t neighbors of degree 2, where $1\le t\le 3$.In 2015, Jendrol' and Maceková proved $g(1,1)\le 7$. Later on, Hudák et al. established $g(1,3)=10$, Jendrol', Maceková, Montassier, and Soták proved $g(1,1)\ge 7$, $g(1,2)=8$ and $g(2,2)\ge 11$, and we recently proved that $g(2,2)=11$ and $g(2,3)=14$.Thus $g(k,t)$ is already known for $k=1$ and all t. In this paper, we prove that $g(k,1)=3k+4$, $g(k,2)=3k+5$, and $g(k,3)=3k+8$ whenever $k\ge 2$.     

Hamiltonian and long paths in bipartite graphs with connectivity

Let G be a graph, $\nu (G)$ the order of G, $\kappa (G)$ the connectivity of G and k a positive integer such that $k\le (\nu (G)?2)/2$. Then G is said to be k-extendable if it has a matching of size k and every matching of size k extends to a perfect matching of G. A Hamiltonian path of a graph G is a spanning path of G. A bipartite graph G with vertex sets $V_1$ and $V_2$ is defined to be Hamiltonian-laceable if such that $|V_1|=|V_2|$ and for every pair of vertices $p\in V_1$ and $q\in V_2$, there exists a Hamiltonian path in G with endpoints p and q, or $|V_1|=|V_2|+1$ and for every pair of vertices $p,q\in V_1,p\ne q$, there exists a Hamiltonian path in G with endpoints p and q. Let G be a bipartite graph with bipartition $(X,Y)$. Define $bn(G)$ to be a maximum integer such that $0\le bn(G)<min\{|X|,|Y|\}$ and (1) for each non-empty subset S of X, if $|S|\le |X|?bn(G)$, then $|N(S)|\ge |S|+bn(G)$, and if $|X|?bn(G)<|S|\le |X|$, then $N(S)=Y$; and (2) for each non-empty subset S of Y, if $|S|\le |Y|?bn(G)$, then $|N(S)|\ge |S|+bn(G)$, and if $|Y|?bn(G)<|S|\le |Y|$, then $N(S)=X$; and (3) $bn(G)=0$ if there is no non-negative integer satisfying (1) and (2).Let G be a bipartite graph with bipartition $(X,Y)$ such that $|X|=|Y|$ and $bn(G)>0$. In this paper, we show that if $\nu (G)\le 2\kappa (G)+4bn(G)?4$, then G is Hamiltonian-laceable; or if $\nu (G)>6bn(G)?2$, then for every pair of vertices $x\in X$ and $y\in Y$, there is an $(x,y)$-path P in G with $|V(P)|\ge 6bn(G)?2$. We show some of its corollaries in k-extendable, bipartite graphs and a conjecture in k-extendable graphs.     

Hamiltonian s-properties and eigenvalues of k-connected graphs

Chvátal and Erdös (1972) [5] proved that, for a k-connected graph G, if the stability number $\alpha (G)\le k?s$, then G is Hamilton-connected ($s=1$) or Hamiltonian ($s=0$) or traceable ($s=?1$). Motivated by the result, we focus on tight sufficient spectral conditions for k-connected graphs to possess Hamiltonian s-properties. We say that a graph possesses Hamiltonian s-properties, which means that the graph is Hamilton-connected if $s=1$, Hamiltonian if $s=0$, and traceable if $s=?1$.For a real number $a\ge 0$, and for a k-connected graph G with order n, degree diagonal matrix $D(G)$ and adjacency matrix $A(G)$, we have identified best possible upper bounds for the spectral radius ${\lambda }_1(aD(\mathrm{\Gamma })+A(\mathrm{\Gamma }))$, where Γ is either G or the complement of G, to warrant that G possesses Hamiltonian s-properties. Sufficient conditions for a graph G to possess Hamiltonian s-properties in terms of upper bounds for the Laplacian spectral radius as well as lower bounds of the algebraic connectivity of G are also obtained. Other best possible spectral conditions for Hamiltonian s-properties are also discussed.     

Graphs with nullity 2c(G)+p(G)−1

Let G be a connected graph with $n(G)$ vertices and $e(G)$ edges. The nullity of G, denoted by $\eta (G)$, is the multiplicity of eigenvalue zero of the adjacency matrix of G. Ma, Wong and Tian (2016) proved that $\eta (G)\le 2c(G)+p(G)?1$ unless G is a cycle of order a multiple of 4, where $c(G)=e(G)?n(G)+1$ is the elementary cyclic number of G and $p(G)$ is the number of leaves of G. Recently, Chang, Chang and Zheng (2020) characterized the leaf-free graphs with nullity $2c(G)?1$, thus leaving the problem to characterize connected graphs G with nullity $2c(G)+p(G)?1$ when $p(G)\ne 0$. In this paper, we solve this problem completely.     

Erdős matching conjecture for almost perfect matchings

In 1965 Erd?s asked, what is the largest size of a family of k-element subsets of an n-element set that does not contain a matching of size $s+1$? In this note, we improve upon a recent result of Frankl and resolve this problem for $s>101k^3$ and $(s+1)k?n<(s+1)(k+\frac{1}{100k})$.     

On the full Brouwer's Laplacian spectrum conjecture

Let G be a simple connected graph and let $S_k(G)$ be the sum of the first k largest Laplacian eigenvalues of G. It was conjectured by Brouwer in 2006 that $S_k(G)\le e(G)+\left(\begin{array}{c}k+1\\ 2\end{array}\right)$ holds for $1\le k\le n?1$. The case $k=2$ was proved by Haemers, Mohammadian and Tayfeh-Rezaie [Linear Algebra Appl., 2010]. In this paper, we propose the full Brouwer's Laplacian spectrum conjecture and we prove the conjecture holds for $k=2$ which also confirm the conjecture of Guan et al. in 2014.     

On the sizes of large subgraphs of the binomial random graph

We consider the binomial random graph $G(n,p)$, where p is a constant, and answer the following two questions.First, given $e(k)=p\left(\begin{array}{c}k\\ 2\end{array}\right)+O(k)$, what is the maximum k such that a.a.s. the binomial random graph $G(n,p)$ has an induced subgraph with k vertices and $e(k)$ edges? We prove that this maximum is not concentrated in any finite set (in contrast to the case of a small $e(k)$). Moreover, for every constant $C>0$, with probability bounded away from 0, the size of the concentration set is bigger than $C\sqrt{n/\ln ?n}$, and, for every ${\omega }_n\to \infty$, a.a.s. it is smaller than ${\omega }_n\sqrt{n/\ln ?n}$.Second, given $k>\epsilon n$, what is the maximum μ such that a.a.s. the set of sizes of k-vertex subgraphs of $G(n,p)$ contains a full interval of length μ? The answer is $\mu =\mathrm{\Theta }\left(\sqrt{(n?k)n\ln ?\left(\begin{array}{c}n\\ k\end{array}\right)}\right)$.     

Large blocking sets in PG(2,q2)

Minimal blocking sets in $\mathrm{PG}(2,q^2)$ have size at most $q^3+1$. This result is due to Bruen and Thas and the bound is sharp, sets attaining this bound are called unitals. In this paper, we show that the second largest minimal blocking sets have size at most $q^3+1-(p-3)/2$, if $q=p$, $p\ge 67$, or $q=p^h$, $p>7$, $h>1$. Our proof also works for sets having at least one tangent at each of its points (that is, for tangency sets).     

On the Newton polygons of twisted L-functions of binomials

Let χ be an order c multiplicative character of a finite field and $f(x)=x^d+\lambda x^e$ a binomial with $(d,e)=1$. We study the twisted classical and T-adic Newton polygons of f. When $p>(d-e)(2d-1)$, we give a lower bound of Newton polygons and show that they coincide if p does not divide a certain integral constant depending on $p\mathrm{mod}cd$.We conjecture that this condition holds if p is large enough with respect to $c,d$ by combining all known results and the conjecture given by Zhang-Niu. As an example, we show that it holds for $e=d-1$.