Which cospectral graphs have same degree sequences

Two graphs are said to be $L$-cospectral (respectively, $Q$-cospectral) if they have the same (respectively, signless) Laplacian spectra, and a graph $G$ is said to be $L?DS$ (respectively, $Q?DS$) if there does not exist other non-isomorphic graph $H$ such that $H$ and $G$ are $L$-cospectral (respectively, $Q$-cospectral). Let $d_1\left(G\right)\ge d_2\left(G\right)\ge ?\ge d_n\left(G\right)$ be the degree sequence of a graph $G$ with $n$ vertices. In this paper, we prove that except for two exceptions (respectively, the graphs with $d_1\left(G\right)\in \{4,5\}$), if $H$ is $L$-cospectral (respectively, $Q$-cospectral) with a connected graph $G$ and $d_2\left(G\right)=2$, then $H$ has the same degree sequence as $G$. A spider graph is a unicyclic graph obtained by attaching some paths to a common vertex of the cycle. As an application of our result, we show that every spider graph and its complement graph are both $L?DS$, which extends the corresponding results of Haemers et al. (2008), Liu et al. (2011), Zhang et al. (2009) and Yu et al. (2014).     

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

Maximum average degree and relaxed coloring

We say a graph is $(d,d,\dots ,d,0,\dots ,0)$-colorable with $a$ of $d$’s and $b$ of $0$’s if $V\left(G\right)$ may be partitioned into $b$ independent sets $O_1,O_2,\dots ,O_b$ and $a$ sets $D_1,D_2,\dots ,D_a$ whose induced graphs have maximum degree at most $d$. The maximum average degree, $mad\left(G\right)$, of a graph $G$ is the maximum average degree over all subgraphs of $G$. In this note, for nonnegative integers $a,b$, we show that if $mad\left(G\right)<\frac{4}{3}a+b$, then $G$ is $(1_1,1_2,\dots ,1_a,0_1,\dots ,0_b)$-colorable.     

A note on the shameful conjecture

Let $P_G\left(q\right)$ denote the chromatic polynomial of a graph $G$ on $n$ vertices. The ‘shameful conjecture’ due to Bartels and Welsh states that, $\frac{P_G\left(n\right)}{P_G(n-1)}\ge \frac{n^n}{{(n-1)}^n}\text{.}$ Let $\mu \left(G\right)$ denote the expected number of colors used in a uniformly random proper $n$-coloring of $G$. The above inequality can be interpreted as saying that $\mu \left(G\right)\ge \mu \left(O_n\right)$, where $O_n$ is the empty graph on $n$ nodes. This conjecture was proved by F.M. Dong, who in fact showed that, $\frac{P_G\left(q\right)}{P_G(q-1)}\ge \frac{q^n}{{(q-1)}^n}$ for all $q\ge n$. There are examples showing that this inequality is not true for all $q\ge 2$. In this paper, we show that the above inequality holds for all $q\ge 36D^{3/2}$, where $D$ is the largest degree of $G$. It is also shown that the above inequality holds true for all $q\ge 2$ when $G$ is a claw-free graph.     

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.     

Automorphism groups of Cayley graphs generated by block transpositions and regular Cayley maps

This paper deals with the Cayley graph $\mathrm{Cay}({\mathrm{Sym}}_n,T_n)$, where the generating set consists of all block transpositions. A motivation for the study of these particular Cayley graphs comes from current research in Bioinformatics. As the main result, we prove that $\text{Aut}\left(\mathrm{Cay}({\mathrm{Sym}}_n,T_n)\right)$ is the product of the left translation group and a dihedral group ${\mathsf{D}}_{n+1}$ of order $2(n+1)$. The proof uses several properties of the subgraph $\Gamma$ of $\mathrm{Cay}({\mathrm{Sym}}_n,T_n)$ induced by the set $T_n$. In particular, $\Gamma$ is a $2(n?2)$-regular graph whose automorphism group is ${\mathsf{D}}_{n+1},$ $\Gamma$ has as many as $n+1$ maximal cliques of size $2$, and its subgraph $\Gamma \left(V\right)$ whose vertices are those in these cliques is a 3-regular, Hamiltonian, and vertex-transitive graph. A relation of the unique cyclic subgroup of ${\mathsf{D}}_{n+1}$ of order $n+1$ with regular Cayley maps on ${\text{Sym}}_n$ is also discussed. It is shown that the product of the left translation group and the latter group can be obtained as the automorphism group of a non-$t$-balanced regular Cayley map on ${\text{Sym}}_n$.     

On mutually independent hamiltonian paths

Let $P_1=〈v_1,v_2,v_3,\dots ,v_n〉$ and $P_2=〈u_1,u_2,u_3,\dots ,u_n〉$ be two hamiltonian paths of $G$. We say that $P_1$ and $P_2$ are independent if $u_1=v_1,u_n=v_n$, and $u_i\ne v_i$ for $1<i<n$. We say a set of hamiltonian paths $P_1,P_2,\dots ,P_s$ of $G$ between two distinct vertices are mutually independent if any two distinct paths in the set are independent. We use $n$ to denote the number of vertices and use $e$ to denote the number of edges in graph $G$. Moreover, we use $\bar{e}$ to denote the number of edges in the complement of $G$. Suppose that $G$ is a graph with $\bar{e}\le n-4$ and $n\ge 4$. We prove that there are at least $n-2-\bar{e}$ mutually independent hamiltonian paths between any pair of distinct vertices of $G$ except $n=5$ and $\bar{e}=1$. Assume that $G$ is a graph with the degree sum of any two non-adjacent vertices being at least $n+2$. Let $u$ and $v$ be any two distinct vertices of $G$. We prove that there are ${deg}_G\left(u\right)+{deg}_G\left(v\right)-n$ mutually independent hamiltonian paths between $u$ and $v$ if $(u,v)\in E\left(G\right)$ and there are ${deg}_G\left(u\right)+{deg}_G\left(v\right)-n+2$ mutually independent hamiltonian paths between $u$ and $v$ if otherwise.