Proper connection and size of graphs

An edge-coloured graph $G$ is called properly connected if any two vertices are connected by a path whose edges are properly coloured. The proper connection number of a connected graph $G,$ denoted by $\mathrm{pc}\left(G\right)$, is the smallest number of colours that are needed in order to make $G$ properly connected. Our main result is the following: Let $G$ be a connected graph of order $n$ and $k\ge 2$. If $\left|E\left(G\right)\right|\ge \left(\genfrac{}{}{0ex}{}{n?k?1}{2}\right)+k+2$, then $\mathrm{pc}\left(G\right)\le k$ except when $k=2$ and $G\in \{G_1,G_2\},$ where $G_1=K_1\vee (2K_1+K_2)$ and $G_2=K_1\vee (K_1+2K_2).$     

On vertex-disjoint cycles and degree sum conditions

This paper considers a degree sum condition sufficient to imply the existence of $k$ vertex-disjoint cycles in a graph $G$. For an integer $t\ge 1$, let ${\sigma }_t\left(G\right)$ be the smallest sum of degrees of $t$ independent vertices of $G$. We prove that if $G$ has order at least $7k+1$ and ${\sigma }_4\left(G\right)\ge 8k?3$, with $k\ge 2$, then $G$ contains $k$ vertex-disjoint cycles. We also show that the degree sum condition on ${\sigma }_4\left(G\right)$ is sharp and conjecture a degree sum condition on ${\sigma }_t\left(G\right)$ sufficient to imply $G$ contains $k$ vertex-disjoint cycles for $k\ge 2$.     

Extremal product-one free sequences in Dihedral and Dicyclic Groups

Let $G$ be a finite group, written multiplicatively. The Davenport constant of $G$ is the smallest positive integer $D\left(G\right)$ such that every sequence of $G$ with $D\left(G\right)$ elements has a non-empty subsequence with product $1$. Let $D_{2n}$ be the Dihedral Group of order $2n$ and $Q_{4n}$ be the Dicyclic Group of order $4n$. Zhuang and Gao (2005) showed that $D\left(D_{2n}\right)=n+1$ and Bass (2007) showed that $D\left(Q_{4n}\right)=2n+1$. In this paper, we give explicit characterizations of all sequences $S$ of $G$ such that $\left|S\right|=D\left(G\right)?1$ and $S$ is free of subsequences whose product is 1, where $G$ is equal to $D_{2n}$ or $Q_{4n}$ for some $n$.     

Star-critical Ramsey numbers for large generalized fans and books

In this paper, we show that for any fixed integers $m\ge 2$ and $t\ge 2$, the star-critical Ramsey number $r_1(K_1+n{K}_t,K_{m+1})=(m?1)tn+t$ for all sufficiently large $n$. Furthermore, for any fixed integers $p\ge 2$ and $m\ge 2$, $r_1(K_p+n{K}_1,K_{m+1})=(m?1+o\left(1\right))n$ as $n\to \infty$.     

A note on degree sum conditions for 2-factors with a prescribed number of cycles in bipartite graphs

Let $G$ be a balanced bipartite graph of order $2n\ge 4$, and let ${\sigma }_{1,1}\left(G\right)$ be the minimum degree sum of two non-adjacent vertices in different partite sets of $G$. In 1963, Moon and Moser proved that if ${\sigma }_{1,1}\left(G\right)\ge n+1$, then $G$ is hamiltonian. In this note, we show that if $k$ is a positive integer, then the Moon–Moser condition also implies the existence of a 2-factor with exactly $k$ cycles for sufficiently large graphs. In order to prove this, we also give a ${\sigma }_{1,1}$ condition for the existence of $k$ vertex-disjoint alternating cycles with respect to a chosen perfect matching in $G$.     

Hamiltonian cycles with all small even chords

Let $G$ be a graph of order $n\ge 3$. An even squared Hamiltonian cycle (ESHC) of $G$ is a Hamiltonian cycle $C=v_1{v}_2\dots v_n{v}_1$ of $G$ with chords $v_i{v}_{i+3}$ for all $1\le i\le n$ (where $v_{n+j}=v_j$ for $j\ge 1$). When $n$ is even, an ESHC contains all bipartite $2$-regular graphs of order $n$. We prove that there is a positive integer $N$ such that for every graph $G$ of even order $n\ge N$, if the minimum degree is $\delta \left(G\right)\ge \frac{n}{2}+92$, then $G$ contains an ESHC. We show that the condition of $n$ being even cannot be dropped and the constant $92$ cannot be replaced by $1$. Our results can be easily extended to even $k$th powered Hamiltonian cycles for all $k\ge 2$.     

A degree sum condition for graphs to be covered by two cycles

Let $G$ be a $k$-connected graph of order $n$. In [1], Bondy (1980) considered a degree sum condition for a graph to have a Hamiltonian cycle, say, to be covered by one cycle. He proved that if ${\sigma }_{k+1}\left(G\right)>(k+1)(n?1)/2$, then $G$ has a Hamiltonian cycle. On the other hand, concerning a degree sum condition for a graph to be covered by two cycles, Enomoto et al. (1995) [4] proved that if $k=1$ and ${\sigma }_3\left(G\right)\ge n$, then $G$ can be covered by two cycles. By these results, we conjecture that if ${\sigma }_{2k+1}\left(G\right)>(2k+1)(n?1)/3$, then $G$ can be covered by two cycles. In this paper, we prove the case $k=2$ of this conjecture. In fact, we prove a stronger result; if $G$ is 2-connected with ${\sigma }_5\left(G\right)\ge 5(n?1)/3$, then $G$ can be covered by two cycles, or $G$ belongs to an exceptional class.     

Compact simple Lie groups admitting left-invariant Einstein metrics that are not geodesic orbit

In this article, we prove that the compact simple Lie groups $\mathrm{S}\mathrm{U}(n)$ for $n\ge 6$, $\mathrm{S}\mathrm{O}(n)$ for $n\ge 7$, $\mathrm{S}\mathrm{p}(n)$ for $n\ge 3$, ${\mathrm{E}}_6,{\mathrm{E}}_7,{\mathrm{E}}_8$, and ${\mathrm{F}}_4$ admit left-invariant Einstein metrics that are not geodesic orbit. This gives a positive answer to an open problem recently posed by Nikonorov.     

The Laplacian spectral radius of trees and maximum vertex degree

Let $\Delta \left(T\right)$ and $\mu \left(T\right)$ denote the maximum degree and the Laplacian spectral radius of a tree $T$, respectively. In this paper we prove that for two trees $T_1$ and $T_2$ on $n(n\ge 21)$ vertices, if $\Delta \left(T_1\right)>\Delta \left(T_2\right)$ and $\Delta \left(T_1\right)\ge ?\frac{11n}{30}?+1$, then $\mu \left(T_1\right)>\mu \left(T_2\right)$, and the bound “$\Delta \left(T_1\right)\ge ?\frac{11n}{30}?+1$” is the best possible. We also prove that for two trees $T_1$ and $T_2$ on $2k(k\ge 4)$ vertices with perfect matchings, if $\Delta \left(T_1\right)>\Delta \left(T_2\right)$ and $\Delta \left(T_1\right)\ge ?\frac{k}{2}?+2$, then $\mu \left(T_1\right)>\mu \left(T_2\right)$.     

On disjoint matchings in cubic graphs

For $i=2,3$ and a cubic graph $G$ let ${\nu }_i\left(G\right)$ denote the maximum number of edges that can be covered by $i$ matchings. We show that ${\nu }_2\left(G\right)\ge \frac{4}{5}\left|V\left(G\right)\right|$ and ${\nu }_3\left(G\right)\ge \frac{7}{6}\left|V\left(G\right)\right|$. Moreover, it turns out that ${\nu }_2\left(G\right)\le \frac{\left|V\left(G\right)\right|+2{\nu }_3\left(G\right)}{4}$.     

Steiner tree packing number and tree connectivity

Let $S$ be a set of at least two vertices in a graph $G$. A subtree $T$ of $G$ is a $S$-Steiner tree if $S?V\left(T\right)$. Two $S$-Steiner trees $T_1$ and $T_2$ are edge-disjoint (resp. internally vertex-disjoint) if $E\left(T_1\right)\cap E\left(T_2\right)=?$ (resp. $E\left(T_1\right)\cap E\left(T_2\right)=?$ and $V\left(T_1\right)\cap V\left(T_2\right)=S$). Let ${\lambda }_G\left(S\right)$ (resp. ${\kappa }_G\left(S\right)$) be the maximum number of edge-disjoint (resp. internally vertex-disjoint) $S$-Steiner trees in $G$, and let ${\lambda }_k\left(G\right)$ (resp. ${\kappa }_k\left(G\right)$) be the minimum ${\lambda }_G\left(S\right)$ (resp. ${\kappa }_G\left(S\right)$) for $S$ ranges over all $k$-subset of $V\left(G\right)$. Kriesell conjectured that if ${\lambda }_G\left(\{x,y\}\right)\ge 2k$ for any $x,y\in S$, then ${\lambda }_G\left(S\right)\ge k$. He proved that the conjecture holds for $\left|S\right|=3,4$. In this paper, we give a short proof of Kriesell’s Conjecture for $\left|S\right|=3,4$, and also show that ${\lambda }_k\left(G\right)\ge ?\frac{1}{k?1}?\frac{k?}{2}??$ (resp. ${\kappa }_k\left(G\right)\ge ?\frac{1}{k?1}?\frac{k?}{2}??$ ) if $\lambda \left(G\right)\ge ?$ (resp. $\kappa \left(G\right)\ge ?$) in $G$, where $k=3,4$. Moreover, we also study the relation between ${\kappa }_k\left(L\left(G\right)\right)$ and ${\lambda }_k\left(G\right)$, where $L\left(G\right)$ is the line graph of $G$.