Spanning trees and spanning closed walks with small degrees

Let G be a graph and let f be a positive integer-valued function on $V(G)$. In this paper, we show that if for all $S?V(G)$, $\omega (G?S)<{\sum }_{v\in S}(f(v)?2)+2+\omega (G[S])$, then G has a spanning tree T containing an arbitrary given matching such that for each vertex v, $d_T(v)\le f(v)$, where $\omega (G?S)$ denotes the number of components of $G?S$ and $\omega (G[S])$ denotes the number of components of the induced subgraph $G[S]$ with the vertex set S. This is an improvement of several results. Next, we prove that if for all $S?V(G)$, $\omega (G?S)\le {\sum }_{v\in S}(f(v)?1)+1$, then G admits a spanning closed walk passing through the edges of an arbitrary given matching meeting each vertex v at most $f(v)$ times. This result solves a long-standing conjecture due to Jackson and Wormald (1990).     

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.     

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.     

Tensor products of n-complete algebras

If A and B are n- and m-representation finite k-algebras, then their tensor product $\mathrm{\Lambda }=A{?}_{k}B$ is not in general $(n+m)$-representation finite. However, we prove that if A and B are acyclic and satisfy the weaker assumption of n- and m-completeness, then Λ is $(n+m)$-complete. This mirrors the fact that taking higher Auslander algebra does not preserve d-representation finiteness in general, but it does preserve d-completeness. As a corollary, we get the necessary condition for Λ to be $(n+m)$-representation finite which was found by Herschend and Iyama by using a certain twisted fractionally Calabi–Yau property.     

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.     

Group gradings on the superalgebras M(m,n), A(m,n) and P(n)

We classify gradings by arbitrary abelian groups on the classical simple Lie superalgebras $P(n)$, $n\ge 2$, and on the simple associative superalgebras $M(m,n)$, $m,n\ge 1$, over an algebraically closed field: fine gradings up to equivalence and G-gradings, for a fixed group G, up to isomorphism. As a corollary, we also classify up to isomorphism the G-gradings on the classical Lie superalgebra $A(m,n)$ that are induced from G-gradings on $M(m+1,n+1)$. In the case of Lie superalgebras, the characteristic is assumed to be 0.     

On distance-regular Cayley graphs of generalized dicyclic groups

Let G be a generalized dicyclic group with identity 1. An inverse closed subset S of $G?\{1\}$ is called minimal if $〈S〉=G$ and there exists some $s\in S$ such that $〈S?\{s,s^{?1}\}〉\ne G$. In this paper, we characterize distance-regular Cayley graphs $\mathrm{Cay}(G,S)$ of G under the condition that S is minimal.     

On generalized perfect difference sets constructed from Sidon sets

Let $\mathbb{N}$ be the set of positive integers. For a nonempty set A of integers and every integer u, denote by $d_A(u)$ the number of $(a,a^{\prime })$ with $a,a^{\prime }\in A$ such that $u=a-a^{\prime }$. For a sequence S of positive integers, let $S(x)$ be the counting function of S. The set $A\subseteq \mathbb{N}$ is called a perfect difference set if $d_A(u)=1$ for every positive integer u. In 2008, Cilleruelo and Nathanson (2008) [4] constructed dense perfect difference sets from dense Sidon sets. In this paper, as a main result, we prove that: let $f:\mathbb{N}\to \mathbb{N}$ be an increasing function satisfying $f(n)\ge 2$ for any positive integer n, then for every Sidon set B and every function $\omega (x)\to \infty$, there exists a set $A\subseteq \mathbb{N}$ such that $d_A(u)=f(u)$ for every positive integer u and $B(x/3)-\omega (x)\le A(x)\le B(x/3)+\omega (x)$ for all $x\ge C_{f,B,\omega }$.