Search

The class of non-bipartite unicyclic graphs with a unique perfect matching, denoted by U , is considered in this article. This article describes the entries of the inverse of the adjacency matrix of a graph in U . It is proved that the inverse graph of a graph in U is always non-bipartite. In this article, we characterize the graphs in U whose inverses are mixed graphs. Among all such graphs in U we identify those graphs whose inverses are quasi-bipartite. Furthermore, characterizations of unicyclic graphs in U possessing unicyclic and bicyclic inverses are also provided in this article. [ABSTRACT FROM AUTHOR]

Letbe a graph with minimum degree. The spectral radius of, denoted by, is the largest eigenvalue of the adjacency matrix of. In this note, we mainly prove the following two results.(1) Let be a graph on vertices with . If , then contains a Hamilton path unless .(2) Let be a graph on vertices with . If , then contains a Hamilton cycle unless .As corollaries of our first result, two previous theorems due to Fiedler and Nikiforov and Lu et al. are obtained, respectively. Our second result refines another previous theorem of Fiedler and Nikiforov. [ABSTRACT FROM AUTHOR]

A graph G is k-edge-Hamiltonian if any collection of vertex-disjoint paths with at most k edges altogether belong to a Hamiltonian cycle in G. A graph G is k-Hamiltonian if for all S ⊆ V (G) with | S | ≤ k , the subgraph induced by V (G) ∖ S has a Hamiltonian cycle. These two concepts are classical extensions of the usual Hamiltonian graphs. In this paper, we present some spectral sufficient conditions for a graph to be k-edge-Hamiltonian and k-Hamiltonian in terms of the adjacency spectral radius as well as the signless Laplacian spectral radius. Our results could be viewed as slight extensions of the recent theorems proved by Li and Ning [Linear Multilinear Algebra. 2016;64:2252–2269], Nikiforov [Czechoslovak Math J. 2016;66:925–940] and Li et al. [Linear Multilinear Algebra. 2018;66:2011–2023]. Moreover, we shall prove a stability result for graphs being k-Hamiltonian, which could be regarded as a complement of two recent results of Füredi et al. [Discrete Math. 2017;340:2688–2690] and [Discrete Math. 2019;342:1919–1923]. [ABSTRACT FROM AUTHOR]

The class of unicyclic non-bipartite graphs with unique perfect matching, denoted by U , is considered in this article. This article provides a complete characterization of unicyclic graphs in U which possess tricyclic inverses. [ABSTRACT FROM AUTHOR]

This paper mainly focuses on spectral conditions for the Hamiltonicity of balanced bipartite graphs and nearly balanced bipartite graphs. Let ρ (G) and q (G) be the spectral radius and signless Laplacian spectral radius of a graph G, respectively. One of our main results is the following theorem: Let G be a balanced bipartite graph of order 2 n and of minimum degree δ (G) ≥ k ≥ s ≥ 0. If n ≥ (k + 1) (k − s + 1) and ρ (G) ≥ ρ (B n , n n − k , k − s) , then G is 2 s -hamiltonian unless G = B n , n n − k , k − s . If n ≥ (k + 1) (k − s + 1) and q (G) ≥ q (B n , n n − k , k − s) , then G is 2 s -hamiltonian unless G = B n , n n − k , k − s . This theorem generalizes the results in [B. L. Li, B. Ning, Spectral analogues of Erdos' and Moon–Moser's theorems on Hamilton cycles, Linear and Multilinear Algebra, 64 (2016) 2252–2269]. [ABSTRACT FROM AUTHOR]

The notion of the scrambling index is a fundamental invariant in graph theory and in the theory of non-negative matrices and their applications. Namely, a scrambling index of a primitive directed graph G is the smallest positive integer k = k (G) such that for any pair of vertices u,v of G there exists a vertex w of G such that there are directed walks of length k from u to w and from v to w. In this paper, we generalize the definition to arbitrary directed graphs. We describe constructively the class of graphs with non-zero scrambling index and generalize the Akelbek–Kirkland bounds for the scrambling index to arbitrary directed graphs. Also, the directed graphs with extremal scrambling index are characterized. [ABSTRACT FROM AUTHOR]

In this paper, we first present spectral conditions for the existence of C n − 1 in graphs (2-connected graphs) of order n, which are motivated by a conjecture of Erd ő s. We also prove spectral conditions for the existence of Hamilton cycles in balanced bipartite graphs. This result presents a spectral analog of Moon-Moser's theorem on Hamilton cycles in balanced bipartite graphs, and extends a previous theorem due to Li and the second author for n sufficiently large. We conclude this paper with two problems on tight spectral conditions for the existence of long cycles of given lengths. [ABSTRACT FROM AUTHOR]

In this paper, we establish some sufficient conditions for a graph to be Hamilton-connected in terms of the edge number, the spectral radius and the signless Laplacian spectral radius of the graph. Furthermore, we also give some sufficient conditions for a graph to be traceable from every vertex in terms of the edge number, the spectral radius and the signless Laplacian spectral radius. [ABSTRACT FROM PUBLISHER]

In 1962, Erdős gave a sufficient condition for Hamilton cycles in terms of the vertex number, edge number and minimum degree of graphs which generalized Ore’s theorem. One year later, Moon and Moser gave an analogous result for Hamilton cycles in balanced bipartite graphs. In this paper, we present the spectral analogues of Erdős’ theorem and Moon–Moser’s theorem, respectively. Letbe the class of non-Hamiltonian graphs of ordernand minimum degree at leastk. We determine the maximum (signless Laplacian) spectral radius of graphs in(for large enoughn), and the minimum (signless Laplacian) spectral radius of the complements of graphs in. All extremal graphs with the maximum (signless Laplacian) spectral radius and with the minimum (signless Laplacian) spectral radius of the complements are determined, respectively. We also solve similar problems for balanced bipartite graphs and the quasi-complements. [ABSTRACT FROM PUBLISHER]