No Arabic abstract
In this paper, we present a spectral sufficient condition for a graph to be Hamilton-connected in terms of signless Laplacian spectral radius with large minimum degree.
For a connected graph $G$ on $n$ vertices, recall that the distance signless Laplacian matrix of $G$ is defined to be $mathcal{Q}(G)=Tr(G)+mathcal{D}(G)$, where $mathcal{D}(G)$ is the distance matrix, $Tr(G)=diag(D_1, D_2, ldots, D_n)$ and $D_{i}$ is the row sum of $mathcal{D}(G)$ corresponding to vertex $v_{i}$. Denote by $rho^{mathcal{D}}(G),$ $rho_{min}^{mathcal{D}}(G)$ the largest eigenvalue and the least eigenvalue of $mathcal{D}(G)$, respectively. And denote by $q^{mathcal{D}}(G)$, $q_{min}^{mathcal{D}}(G)$ the largest eigenvalue and the least eigenvalue of $mathcal{Q}(G)$, respectively. The distance spread of a graph $G$ is defined as $S_{mathcal{D}}(G)=rho^{mathcal{D}}(G)- rho_{min}^{mathcal{D}}(G)$, and the distance signless Laplacian spread of a graph $G$ is defined as $S_{mathcal{Q}}(G)=q^{mathcal{D}}(G)-q_{min}^{mathcal{D}}(G)$. In this paper, we point out an error in the result of Theorem 2.4 in Distance spectral spread of a graph [G.L. Yu, et al, Discrete Applied Mathematics. 160 (2012) 2474--2478] and rectify it. As well, we obtain some lower bounds on ddistance signless Laplacian spread of a graph.
This paper presents sufficient conditions for Hamiltonian paths and cycles in graphs. Letting $lambdaleft( Gright) $ denote the spectral radius of the adjacency matrix of a graph $G,$ the main results of the paper are: (1) Let $kgeq1,$ $ngeq k^{3}/2+k+4,$ and let $G$ be a graph of order $n$, with minimum degree $deltaleft( Gright) geq k.$ If [ lambdaleft( Gright) geq n-k-1, ] then $G$ has a Hamiltonian cycle, unless $G=K_{1}vee(K_{n-k-1}+K_{k})$ or $G=K_{k}vee(K_{n-2k}+overline{K}_{k})$. (2) Let $kgeq1,$ $ngeq k^{3}/2+k^{2}/2+k+5,$ and let $G$ be a graph of order $n$, with minimum degree $deltaleft( Gright) geq k.$ If [ lambdaleft( Gright) geq n-k-2, ] then $G$ has a Hamiltonian path, unless $G=K_{k}vee(K_{n-2k-1}+overline {K}_{k+1})$ or $G=K_{n-k-1}+K_{k+1}$ In addition, it is shown that in the above statements, the bounds on $n$ are tight within an additive term not exceeding $2$.
Tur{a}n type extremal problem is how to maximize the number of edges over all graphs which do not contain fixed forbidden subgraphs. Similarly, spectral Tur{a}n type extremal problem is how to maximize (signless Laplacian) spectral radius over all graphs which do not contain fixed subgraphs. In this paper, we first present a stability result for $kcdot P_3$ in terms of the number of edges and then determine all extremal graphs maximizing the signless Laplacian spectral radius over all graphs which do not contain a fixed linear forest with at most two odd paths or $kcdot P_3$ as a subgraph, respectively.
Let $G$ be a simple graph with maximum degree $Delta(G)$. A subgraph $H$ of $G$ is overfull if $|E(H)|>Delta(G)lfloor |V(H)|/2 rfloor$. Chetwynd and Hilton in 1985 conjectured that a graph $G$ with $Delta(G)>|V(G)|/3$ has chromatic index $Delta(G)$ if and only if $G$ contains no overfull subgraph. The 1-factorization conjecture is a special case of this overfull conjecture, which states that for even $n$, every regular $n$-vertex graph with degree at least about $n/2$ has a 1-factorization and was confirmed for large graphs in 2014. Supporting the overfull conjecture as well as generalizing the 1-factorization conjecture in an asymptotic way, in this paper, we show that for any given $0<varepsilon <1$, there exists a positive integer $n_0$ such that the following statement holds: if $G$ is a graph on $2nge n_0$ vertices with minimum degree at least $(1+varepsilon)n$, then $G$ has chromatic index $Delta(G)$ if and only if $G$ contains no overfull subgraph.
Let $F_{a_1,dots,a_k}$ be a graph consisting of $k$ cycles of odd length $2a_1+1,dots, 2a_k+1$, respectively which intersect in exactly a common vertex, where $kgeq1$ and $a_1ge a_2ge cdotsge a_kge 1$. In this paper, we present a sharp upper bound for the signless Laplacian spectral radius of all $F_{a_1,dots,a_k}$-free graphs and characterize all extremal graphs which attain the bound. The stability methods and structure of graphs associated with the eigenvalue are adapted for the proof.