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

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

Improvements on Hippchen's conjecture

Let G be a k-connected graph on n vertices. Hippchen's Conjecture (2008) states that two longest paths in G share at least k vertices. Gutiérrez (2020) recently proved the conjecture when $k\le 4$ or $k\ge \frac{n?2}{3}$. We improve upon both results; namely, we show that two longest paths in G share at least k vertices when $k=5$ or $k\ge \frac{n+2}{5}$. This completely resolves two conjectures by Gutiérrez in the affirmative.     

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

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.     

Remarks on the distribution of colors in Gallai colorings

A Gallai coloring of a complete graph $K_n$ is an edge coloring without triangles colored with three different colors. A sequence $e_1\ge \cdots \ge e_k$ of positive integers is an $(n,k)$-sequence if ${\sum }_{i=1}^k{e}_i=\left(\genfrac{}{}{0ex}{}{n}{2}\right)$. An $(n,k)$-sequence is a G-sequence if there is a Gallai coloring of $K_n$ with $k$ colors such that there are $e_i$ edges of color $i$ for all $i,1\le i\le k$. Gyárfás, Pálvölgyi, Patkós and Wales proved that for any integer $k\ge 3$ there exists an integer $g\left(k\right)$ such that every $(n,k)$-sequence is a G-sequence if and only if $n\ge g\left(k\right)$. They showed that $g\left(3\right)=5,g\left(4\right)=8$ and $2k-2\le g\left(k\right)\le 8k^2+1$.We show that $g\left(5\right)=10$ and give almost matching lower and upper bounds for $g\left(k\right)$ by showing that with suitable constants $\alpha ,\beta >0$, $\frac{\alpha k^{1.5}}{lnk}\le g\left(k\right)\le \beta k^{1.5}$ for all sufficiently large $k$.     

Bounds for moments of cubic and quartic Dirichlet L-functions

We study the $2k$-th moment of central values of the family of primitive cubic and quartic Dirichlet $L$-functions. We establish sharp lower bounds for all real $k\ge 1/2$ unconditionally for the cubic case and under the Lindelöf hypothesis for the quartic case. We also establish sharp lower bounds for all real $0\le k<1/2$ and sharp upper bounds for all real $k\ge 0$ for both the cubic and quartic cases under the generalized Riemann hypothesis (GRH). As an application of our results, we establish quantitative non-vanishing results for the corresponding $L$-values.     

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