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.     

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$.     

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})$.     

Maximize the Q-index of graphs with fixed order and size

In this paper, we consider two kinds of spectral extremal questions. The first asks which graph attains the maximum Q-index over all graphs of order n and size $m=n+k$? The second asks which graph attains the maximum Q-index over all $(p,q)$-bipartite graphs with $m=p+q+k$ edges? We solve the first question for $4\le k\le n?3$, and the second question for $?p?q\le k\le p?q$. The maximum Q-index on connected $(p,q)$-bipartite graphs is also determined for $?1\le k\le p?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.     

Hamilton-connected,vertex-pancyclic and bipartite holes

In 2016, McDiarmid and Yolov gave a tight threshold for the existence of Hamilton cycle in graphs with large minimum degree and without large “bipartite hole”(two disjoint sets of vertices with no edge between them) which extends Dirac's classical Theorem. In detail, an $(s,t)$-bipartite-hole in a graph G consists of two disjoint vertex sets S and T with $|S|=s$ and $|T|=t$ such that $E(G[S,T])=?$. Let $\stackrel{?}{\alpha }(G)$ be the maximum integer such that G contains an $(s,t)$-bipartite-hole for every pair of nonnegative integers s and t with $s+t=r$. Motivated by Bondy's metaconjecture, in this paper, we study the existence of vertex-pancyclicity (every vertex is in a cycle of length i for each $i\in [3,n]$ and Hamilton-connectivity(any two vertices can be connected through a Hamilton path). Our central theorem is that for any given $\mu >0$ and sufficiently large n, if G is an n-vertex graph with $\stackrel{?}{\alpha }(G)=\mu n$ and $\delta (G)\ge \frac{10}{3}\mu n$, then G is Hamilton-connected and vertex-pancyclic.     

On the size of special class 1 graphs and (P3;k)-co-critical graphs

A well-known theorem of Vizing states that if G is a simple graph with maximum degree Δ, then the chromatic index ${\chi }^{\prime }(G)$ of G is Δ or $\mathrm{\Delta }+1$. A graph G is class 1 if ${\chi }^{\prime }(G)=\mathrm{\Delta }$, and class 2 if ${\chi }^{\prime }(G)=\mathrm{\Delta }+1$; G is Δ-critical if it is connected, class 2 and ${\chi }^{\prime }(G-e)<{\chi }^{\prime }(G)$ for every $e\in E(G)$. A long-standing conjecture of Vizing from 1968 states that every Δ-critical graph on n vertices has at least $(n(\mathrm{\Delta }-1)+3)/2$ edges. We initiate the study of determining the minimum number of edges of class 1 graphs G, in addition, ${\chi }^{\prime }(G+e)={\chi }^{\prime }(G)+1$ for every $e\in E(\bar{G})$. Such graphs have intimate relation to $(P_3;k)$-co-critical graphs, where a non-complete graph G is $(P_3;k)$-co-critical if there exists a k-coloring of $E(G)$ such that G does not contain a monochromatic copy of $P_3$ but every k-coloring of $E(G+e)$ contains a monochromatic copy of $P_3$ for every $e\in E(\bar{G})$. We use the bound on the size of the aforementioned class 1 graphs to study the minimum number of edges over all $(P_3;k)$-co-critical graphs. We prove that if G is a $(P_3;k)$-co-critical graph on $n\ge k+2$ vertices, then$e(G)\ge \frac{k}{2}(n-\lceil \frac{k}{2}\rceil -\epsilon )+\left(\begin{array}{c}\lceil k/2\rceil +\epsilon \\ 2\end{array}\right),$ where ε is the remainder of $n-\lceil k/2\rceil$ when divided by 2. This bound is best possible for all $k\ge 1$ and $n\ge \lceil 3k/2\rceil +2$.     

Spectral strengthening of a theorem on transversal critical graphs

A transversal set of a graph G is a set of vertices incident to all edges of G. The transversal number of G, denoted by $\tau (G)$, is the minimum cardinality of a transversal set of G. A simple graph G with no isolated vertex is called τ-critical if $\tau (G?e)<\tau (G)$ for every edge $e\in E(G)$. For any τ-critical graph G with $\tau (G)=t$, it has been shown that $|V(G)|\le 2t$ by Erd?s and Gallai and that $|E(G)|\le \left(\begin{array}{c}t+1\\ 2\end{array}\right)$ by Erd?s, Hajnal and Moon. Most recently, it was extended by Gyárfás and Lehel to $|V(G)|+|E(G)|\le \left(\begin{array}{c}t+2\\ 2\end{array}\right)$. In this paper, we prove stronger results via spectrum. Let G be a τ-critical graph with $\tau (G)=t$ and $|V(G)|=n$, and let ${\lambda }_1$ denote the largest eigenvalue of the adjacency matrix of G. We show that $n+{\lambda }_1\le 2t+1$ with equality if and only if G is $t{K}_2$, $K_{s+1}\cup (t?s)K_2$, or $C_{2s?1}\cup (t?s)K_2$, where $2\le s\le t$; and in particular, ${\lambda }_1(G)\le t$ with equality if and only if G is $K_{t+1}$. We then apply it to show that for any nonnegative integer r, we have $n(r+\frac{{\lambda }_1}{2})\le \left(\begin{array}{c}t+r+1\\ 2\end{array}\right)$ and characterize all extremal graphs. This implies a pure combinatorial result that $r|V(G)|+|E(G)|\le \left(\begin{array}{c}t+r+1\\ 2\end{array}\right)$, which is stronger than Erd?s-Hajnal-Moon Theorem and Gyárfás-Lehel Theorem. We also have some other generalizations.     

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$.