A large family of cospectral Cayley graphs over dicyclic groups

For a finite group G and an inverse closed subset $S\subseteq G\setminus \{e\}$, the Cayley graph $X(G,S)$ has vertex set G and two vertices $x,y\in G$ are adjacent if and only if $x{y}^{-1}\in S$. Two graphs are called cospectral if their adjacency matrices have the same spectrum. Let $p\ge 3$ be a prime number and $T_{4p}$ be the dicyclic group of order 4p. In this paper, with the help of the characters from representation theory, we construct a large family of pairwise non-isomorphic and cospectral Cayley graphs over the dicyclic group $T_{4p}$ with $p\ge 23$, and find several pairs of non-isomorphic and cospectral Cayley graphs for $5\le p\le 19$.     

On s-hamiltonian line graphs of claw-free graphs

For an integer $s\ge 0$, a graph $G$ is $s$-hamiltonian if for any vertex subset $S?V\left(G\right)$ with $\left|S\right|\le s$, $G?S$ is hamiltonian, and $G$ is $s$-hamiltonian connected if for any vertex subset $S?V\left(G\right)$ with $\left|S\right|\le s$, $G?S$ is hamiltonian connected. Thomassen in 1984 conjectured that every 4-connected line graph is hamiltonian (see Thomassen, 1986), and Ku?zel and Xiong in 2004 conjectured that every 4-connected line graph is hamiltonian connected (see Ryjá?ek and Vrána, 2011). In Broersma and Veldman (1987), Broersma and Veldman raised the characterization problem of $s$-hamiltonian line graphs. In Lai and Shao (2013), it is conjectured that for $s\ge 2$, a line graph $L\left(G\right)$ is $s$-hamiltonian if and only if $L\left(G\right)$ is $(s+2)$-connected. In this paper we prove the following.(i) For an integer $s\ge 2$, the line graph $L\left(G\right)$ of a claw-free graph $G$ is $s$-hamiltonian if and only if $L\left(G\right)$ is $(s+2)$-connected.(ii) The line graph $L\left(G\right)$ of a claw-free graph $G$ is 1-hamiltonian connected if and only if $L\left(G\right)$ is 4-connected.     

Hyperstability of a logarithmic-type functional equation on restricted domains

Let $X$ be a real normed vector space and $f:(0,\infty )\to X$. In this paper, we prove the hyperstability of the logarithmic functional equation

$f\left(x^y\right)?yf\left(x\right)=0$

on $\Gamma$ of Lebesgue measure zero. More precisely, we prove that if $f:(0,\infty )\to X$ satisfies

$6f\left(x^y\right)?yf\left(x\right)6\le ?(x,y)$

for all $(x,y)\in {\Gamma }^{+}?\{(x,y):y>\alpha \left(x\right)\}[\mathrm{resp.}{\Gamma }^{?}?\{(x,y):0<y<\alpha \left(x\right)\}]$ of Lebesgue measure zero, where $\alpha :(0,\infty )\to (0,\infty )$ is an arbitrary given function and $?:(0,\infty )\times (0,\infty )\to [0,\infty )$ satisfies the condition $?(x,y)∕y\to 0$ as $y\to \infty$ [resp. $y\to 0$], then $f$ satisfies the functional equation $f\left(x^y\right)=yf\left(x\right)$ for all $x>0$ and$y>0$.     

Dependence of eigenvalues on the diffusion operators with random jumps from the boundary

This paper deals with a non-self-adjoint eigenvalue problem

$\{\begin{array}{c}a(x)y^{″}(x)+b(x)y^{\prime }(x)=\lambda y(x),\hfill \\ y(0)={\int }_0^{1}y(x)\mathrm{d}{\nu }_0(x),y(1)={\int }_0^{1}y(x)\mathrm{d}{\nu }_1(x),\hfill \end{array}$

which is associated with the generator of one dimensional diffusions with random jumps from the boundary. We focus on the dependence of spectral gap, eigenvalues and eigenfunctions on the coefficients a, b and the probability distributions ${\nu }_0$, ${\nu }_1$. To prove this, we show that all the eigenvalues are confined to a parabolic neighborhood of the real axis. Moreover, we also prove that zero is an algebraically simple eigenvalue of the problem.     

Vertex partitions of (C3,C4,C6)-free planar graphs

A graph is $(k_1,k_2)$-colorable if it admits a vertex partition into a graph with maximum degree at most $k_1$ and a graph with maximum degree at most $k_2$. We show that every $(C_3,C_4,C_6)$-free planar graph is $(0,6)$-colorable. We also show that deciding whether a $(C_3,C_4,C_6)$-free planar graph is $(0,3)$-colorable is NP-complete.     

Average degrees of edge-chromatic critical graphs

Let $G$ be a simple graph, and let $\Delta \left(G\right)$, $\overline{d}\left(G\right)$ and ${\chi }^{\prime }\left(G\right)$ denote the maximum degree, the average degree and the chromatic index of $G$, respectively. We called $G$ edge-$\Delta$-critical if ${\chi }^{\prime }\left(G\right)=\Delta \left(G\right)+1$ and ${\chi }^{\prime }\left(H\right)\le \Delta \left(G\right)$ for every proper subgraph $H$ of $G$. Vizing in 1968 conjectured that if $G$ is an edge-$\Delta$-critical graph of order $n$, then $\overline{d}\left(G\right)\ge \Delta \left(G\right)?1+\frac{3}{n}$. We prove that for any edge-$\Delta$-critical graph $G$, $\stackrel{?}{d}\left(G\right)\ge min\left\{\frac{2\sqrt{2}\Delta \left(G\right)?3?\sqrt{2}}{2\sqrt{2}+1},\frac{3\Delta \left(G\right)}{4}?2\right\},$ that is, $\overline{d}\left(G\right)\ge \left\{\begin{array}{cc}\frac{3}{4}\Delta \left(G\right)?2\hfill & \text{if}\Delta \left(G\right)\le 75;\hfill \\ \frac{2\sqrt{2}\Delta \left(G\right)?3?\sqrt{2}}{2\sqrt{2}+1}\approx 0.7388\Delta \left(G\right)?1.153\hfill & \text{if}\Delta \left(G\right)\ge 76.\hfill \end{array}\right.$This result improves the best known bound $\frac{2}{3}(\Delta \left(G\right)+2)$ obtained by Woodall in 2007 for $\Delta \left(G\right)\ge 41$.     

On the smallest non-trivial tight sets in Hermitian polar spaces H(d,q2), d even

We show that every $x$-tight set of a Hermitian polar spaces $\mathrm{H}(2n,q^2)$, $n\ge 2$, is the union of $x$ disjoint generators of the polar space provided that $x\le \frac{1}{2}(q+1)$. This was known before only when $n\in \{2,3\}$. This result is a contribution to the conjecture that the smallest $x$-tight set of $H(2n,q^2)$ that is not a union of disjoint generators occurs for $x=q+1$ and is for sufficiently large $q$ an embedded subgeometry.     

On the range of simple symmetric random walks on the line

This paper is aimed at a detailed study of the behaviors of random walks which is defined by the dyadic expansions of points. More precisely, let $x=({ϵ}_1\left(x\right),{ϵ}_2\left(x\right),\dots )$ be the dyadic expansion for a point $x\in [0,1)$ and $S_n\left(x\right)={\sum }_{k=1}^n(2{ϵ}_k\left(x\right)-1)$, which can be regarded as a simple symmetric random walk on $\mathbb{Z}.$ Denote by $R_n\left(x\right)$ the cardinality of the set $\{S_1\left(x\right),\dots ,S_n\left(x\right)\},$ which is just the distinct position of $x$ passed after $n$ times. The set of points whose behavior satisfies $R_n\left(x\right)\sim c{n}^{\gamma }$ is studied ($c>0$ and $0<\gamma \le 1$ being fixed) and its Hausdorff dimension is calculated.     

Analytic aspects of Delannoy numbers

The Delannoy numbers $d(n,k)$ count the number of lattice paths from $(0,0)$ to $(n?k,k)$ using steps $(1,0),(0,1)$ and $(1,1)$. We show that the zeros of all Delannoy polynomials $d_n\left(x\right)={\sum }_{k=0}^{n}d(n,k)x^k$ are in the open interval $(?3?2\sqrt{2},?3+2\sqrt{2})$ and are dense in the corresponding closed interval. We also show that the Delannoy numbers $d(n,k)$ are asymptotically normal (by central and local limit theorems).     

Homomorphisms of planar (m,n)-colored-mixed graphs to planar targets

An $(m,n)$-colored-mixed graph $G=(V,A_1,A_2,\cdots ,A_m,E_1,E_2,\cdots ,E_n)$ is a graph having m colors of arcs and n colors of edges. We do not allow two arcs or edges to have the same endpoints. A homomorphism from an $(m,n)$-colored-mixed graph G to another $(m,n)$-colored-mixed graph H is a morphism $\phi :V(G)\to V(H)$ such that each edge (resp. arc) of G is mapped to an edge (resp. arc) of H of the same color (and orientation). An $(m,n)$-colored-mixed graph T is said to be $P_g^{(m,n)}$-universal if every graph in $P_g^{(m,n)}$ (the planar $(m,n)$-colored-mixed graphs with girth at least g) admits a homomorphism to T.We show that planar $P_g^{(m,n)}$-universal graphs do not exist for $2m+n\ge 3$ (and any value of g) and find a minimal (in the number vertices) planar $P_g^{(m,n)}$-universal graphs in the other cases.