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

γ-variable first-order logic of uniform attachment random graphs

We study logical limit laws for uniform attachment random graphs. In this random graph model, vertices and edges are introduced recursively: at time $n+1$, the vertex $n+1$ is introduced together with m edges joining the new vertex with m different vertices chosen uniformly at random from $1,\dots ,n$. We prove that this random graph obeys convergence law for first-order sentences with at most $m?2$ variables.     

Vertex-disjoint rainbow triangles in edge-colored graphs

Let $G$ be an edge-colored graph of order $n$. The minimum color degree of $G$, denoted by ${\delta }^c\left(G\right)$, is the largest integer $k$ such that for every vertex $v$, there are at least $k$ distinct colors on edges incident to $v$. We say that an edge-colored graph is rainbow if all its edges have different colors. In this paper, we consider vertex-disjoint rainbow triangles in edge-colored graphs. Li (2013) showed that if ${\delta }^c\left(G\right)\ge (n+1)∕2$, then $G$ contains a rainbow triangle and the lower bound is tight. Motivated by this result, we prove that if $n\ge 20$ and ${\delta }^c\left(G\right)\ge (n+2)∕2$, then $G$ contains two vertex-disjoint rainbow triangles. In particular, we conjecture that if ${\delta }^c\left(G\right)\ge (n+k)∕2$, then $G$ contains $k$ vertex-disjoint rainbow triangles. For any integer $k\ge 2$, we show that if $n\ge 16k-12$ and ${\delta }^c\left(G\right)\ge n∕2+k-1$, then $G$ contains $k$ vertex-disjoint rainbow triangles. Moreover, we provide sufficient conditions for the existence of $k$ edge-disjoint rainbow triangles.     

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

Moment subset sums over finite fields

The k-subset sum problem over finite fields is a classical NP-complete problem. Motivated by coding theory applications, a more complex problem is the higher m-th moment k-subset sum problem over finite fields. We show that there is a deterministic polynomial time algorithm for the m-th moment k-subset sum problem over finite fields for each fixed m when the evaluation set is the image set of a monomial or Dickson polynomial of any degree n. In the classical case $m=1$, this recovers previous results of Nguyen-Wang (the case $m=1,p>2$) [22] and the results of Choe-Choe (the case $m=1,p=2$) [3].     

Monochromatic k-edge-connection colorings of graphs

A path in an edge-colored graph $G$ is called monochromatic if any two edges on the path have the same color. For $k\ge 2$, an edge-colored graph $G$ is said to be monochromatic $k$-edge-connected if every two distinct vertices of $G$ are connected by at least $k$ edge-disjoint monochromatic paths, and $G$ is said to be uniformly monochromatic $k$-edge-connected if every two distinct vertices are connected by at least $k$ edge-disjoint monochromatic paths such that all edges of these $k$ paths are colored with a same color. We use $m{c}_k\left(G\right)$ and $um{c}_k\left(G\right)$ to denote the maximum number of colors that ensures $G$ to be monochromatic $k$-edge-connected and, respectively, $G$ to be uniformly monochromatic $k$-edge-connected. In this paper, we first conjecture that for any $k$-edge-connected graph $G$, $m{c}_k\left(G\right)=e\left(G\right)-e\left(H\right)+\lfloor \frac{k}{2}\rfloor$, where $H$ is a minimum $k$-edge-connected spanning subgraph of $G$. We verify the conjecture for $k=2$. We also prove the conjecture for $G=K_{k+1}$ and $G=K_{k,n}$ with $n\ge k\ge 3$. When $G$ is a minimal $k$-edge-connected graph, we give an upper bound of $m{c}_k\left(G\right)$, i.e., $m{c}_k\left(G\right)\le k-1$. For the uniformly monochromatic $k$-edge-connectivity, we prove that for all $k$, $um{c}_k\left(G\right)=e\left(G\right)-e\left(H\right)+1$, where $H$ is a minimum $k$-edge-connected spanning subgraph of $G$.     

A characterization of graphs with given maximum degree and smallest possible matching number: II

Let ${\alpha }^{\prime }(G)$ be the matching number of a graph G. A characterization of the graphs with given maximum odd degree and smallest possible matching number is given by Henning and Shozi (2021) [13]. In this paper we complete our study by giving a characterization of the graphs with given maximum even degree and smallest possible matching number. In 2018 Henning and Yeo [10] proved that if G is a connected graph of order n, size m and maximum degree k where $k\ge 4$ is even, then ${\alpha }^{\prime }(G)\ge \frac{n}{k(k+1)}+\frac{m}{k+1}?\frac{1}{k(k+1)}$, unless G is k-regular and $n\in \{k+1,k+3\}$. In this paper, we give a complete characterization of the graphs that achieve equality in this bound when the maximum degree k is even, thereby completing our study of graphs with given maximum degree and smallest possible matching number.     

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

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.     

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.