Search

Four Color Theorem implies that the independence number of every planar graph is at least n / 4. A cactus graph is a connected planar graph whose block is either an edge or a cycle. In this paper, the lower bound for independence number of cactus graphs is improved to ⌈ n / 3 ⌉. Moreover, the maximum spectral radius of cactus graphs with fixed independence number is determined. [ABSTRACT FROM AUTHOR]

The (k , r) -fan, denoted by F k , r , is the graph consisting of k copies of the complete graph K r which intersect in a single vertex. Desai et al. [7] proved that E X s p (n , F k , r) ⊆ E X (n , F k , r) for sufficiently large n , where E X s p (n , F k , r) and E X (n , F k , r) are the sets of n -vertex F k , r -free graphs with maximum spectral radius and maximum size, respectively. In this paper, the set E X s p (n , F k , r) is uniquely determined for n large enough. Let H s , t 1 , ... , t k be the graph consisting of s triangles and k odd cycles of lengths t 1 , ... , t k ≥ 5 intersecting in exactly one common vertex, denoted by H s , k for short. Li and Peng [12] showed that E X s p (n , H s , k) ⊆ E X (n , H s , k) for n large enough. In this paper, the set E X s p (n , H s , k) is uniquely characterized for sufficiently large n. [ABSTRACT FROM AUTHOR]

A fractional matching of a graph G is a function f : E (G) → [ 0 , 1 ] such that for any v ∈ V (G) , ∑ e ∈ E G (v) f (e) ≤ 1 , where E G (v) = { e ∈ E (G) : e is incident with v in G }. The fractional matching number of G is μ f (G) = max { ∑ e ∈ E (G) f (e) : f is a fractional matching of G }. Let k ∈ (0 , n) is an integer. In this paper, we prove a tight lower bound of the spectral radius to guarantee μ f (G) > n − k 2 in a graph with minimum degree δ , which implies the result on the fractional perfect matching due to Fan et al. (2022) [6]. For a set { A , B , C , ... } of graphs, an { A , B , C , ... } -factor of a graph G is defined to be a spanning subgraph of G each component of which is isomorphic to one of { A , B , C , ... }. We present a tight sufficient condition in terms of the spectral radius for the existence of a { K 2 , { C k } } -factor in a graph with minimum degree δ , where k ≥ 3 is an integer. Moreover, we also provide a tight spectral radius condition for the existence of a { K 1 , 1 , K 1 , 2 , ... , K 1 , k } -factor with k ≥ 2 in a graph with minimum degree δ , which generalizes the result of Miao et al. (2023) [10]. [ABSTRACT FROM AUTHOR]

A fractional matching of a graph G is a function f:E(G) → [0, 1] such that for any v ∈ V(G), ∑ e ∈ E G (v) f (e) ≤ 1 where EG(v) = {e ∈ E(G): e is incident with v in G}. The fractional matching number of G is μ f (G) = max { ∑ e ∈ E (G) f (e) : f is a fractional matching of G}. For any real numbers a ≥ 0 and k ∈ (0, n), it is observed that if n = |V(G)| and δ (G) > n − k 2 , then μ f (G) > n − k 2 . We determine a function φ(a, n, δ, k) and show that for a connected graph G with n = |V(G)|, δ (G) ≤ n − k 2 , spectral radius λ1(G) and complement G ¯ , each of the following holds. If λ1 (aD(G) + A(G)) < φ(a, n, δ, k), then μ f (G) > n − k 2. If λ 1 (a D (G ¯) + A (G ¯)) < (a + 1) (δ + k − 1) , then μ f (G) > n − k 2. As applications, we prove a relationship between μf(G) and λ1(aD(G) + A(G)) for a graph G. Furthermore, sufficient spectral conditions for a graph to have a fractional perfect matching are also obtained. [ABSTRACT FROM AUTHOR]

Let G be a graph and h : E (G) → [ 0 , 1 ] be a function. For any two positive integers a and b with a ≤ b , a fractional [ a , b ] -factor of G with the indicator function h is a spanning subgraph with vertex set V (G) and edge set E h such that a ≤ ∑ e ∈ E G (v) h (e) ≤ b for any vertex v ∈ V (G) , where E h = { e ∈ E (G) | h (e) > 0 } and E G (v) = { e ∈ E (G) | e is incident with v in G }. A graph G is ID-factor-critical if for every independent set I of G whose size has the same parity as | V (G) | , G − I has a perfect matching. In this paper, we present a tight sufficient condition based on the spectral radius for a graph to contain a fractional [ a , b ] -factor, which extends the result of Wei and Zhang (2023) [16]. Furthermore, we also prove a tight sufficient condition in terms of the spectral radius for a graph with minimum degree δ to be ID-factor-critical. [ABSTRACT FROM AUTHOR]

For integer k ≥ 2 , a graph G is called k -leaf-connected if | V (G) | ≥ k + 1 and given any subset S ⊆ V (G) with | S | = k , G always has a spanning tree T such that S is precisely the set of leaves of T. Thus a graph is 2-leaf-connected if and only if it is Hamilton-connected. Gurgel and Wakabayashi (1986) provided a sufficient condition based upon the size for a graph to be k -leaf-connected. In this paper, we present a new condition for k -leaf-connected graphs which improves the result of Gurgel and Wakabayashi. Meanwhile, we also extend the condition on Hamilton-connected graphs of Zhou and Wang (2017). As applications, sufficient conditions for a graph to be k -leaf-connected in terms of the (signless Laplacian) spectral radius of G or its complement are obtained. [ABSTRACT FROM AUTHOR]

A fan, denoted by H 2 k , is the graph obtained by joining a vertex to a path with 2 k vertices. A graph is H 2 k -free if it does not contain a subgraph H 2 k. Yuan (2021) [13] proved the Turán number and the extremal graphs of H 2 k -free graphs. In this paper, we characterize spectral extremal graphs of H 2 k -free graphs for sufficiently large n and k ≥ 3. • Spectral Turán-type problem is a frontier research field in spectral graph theory. In this paper, we characterize spectral extremal graphs of H 2 k -free graphs for sufficiently large n and k ≥ 3. • The problem investigated in this paper is very interesting and important in spectral graph theory. [ABSTRACT FROM AUTHOR]

For any integer k ≥ 2 , a spanning k -ended-tree is a spanning tree with at most k leaves. Motivated by the degree sum condition of Broersma and Tuinstra (1998) [4] , we provide tight spectral conditions to guarantee the existence of a spanning k -ended-tree in a connected graph of order n with extremal graphs being characterized. Let T be a spanning tree of a connected graph. The leaf degree of T is the maximum number of leaves adjacent to v in T for any v ∈ V (T). By adopting Kaneko's theorem (2001) [17] , we also present tight spectral conditions for the existence of a spanning tree with leaf degree at most k in a connected graph and determine extremal graphs, where k ≥ 1 is an integer. [ABSTRACT FROM AUTHOR]

A bipartite graph is subcubic if it is an irregular bipartite graph with maximum degree three. In this paper, we prove that the asymptotic value of maximum spectral radius over subcubic bipartite graphs of order n is 3 − Θ ( π 2 n 2 ). Our key approach is taking full advantage of the eigenvalues of a certain tridiagonal matrix, due to Willms [SIAM J. Matrix Anal. Appl. 30 (2008) 639–656]. Moreover, for large maximum degree, i.e., the maximum degree is at least ⌊ n / 2 ⌋ , we characterize irregular bipartite graphs with maximum spectral radius. For general maximum degree, we present an upper bound on the spectral radius of irregular bipartite graphs in terms of the order and maximum degree. [ABSTRACT FROM AUTHOR]

In this paper, we give sufficient conditions on the spectral radius for a bipartite graph being Hamiltonian and traceable, which expand the results of Lu, Liu and Tian (2012) [10] . Furthermore, we also provide tight sufficient conditions on the signless Laplacian spectral radius for a graph to be Hamiltonian and traceable, which improve the results of Yu and Fan (2012) [11] . [ABSTRACT FROM AUTHOR]

For integer k ≥ 2 , a graph G is called k -leaf-connected if | V (G) | ≥ k + 1 and given any subset S ⊆ V (G) with | S | = k , G always has a spanning tree T such that S is precisely the set of leaves of T. Thus a graph is 2-leaf-connected if and only if it is Hamilton-connected. In this paper, we present a best possible condition based upon the size to guarantee a graph to be k -leaf-connected, which not only improves the results of Gurgel and Wakabayashi (1986) and Ao et al. (2022), but also extends the result of Xu et al. (2021). Our key approach is showing that an (n + k − 1) -closed non- k -leaf-connected graph must contain a large clique if its size is large enough. As applications, sufficient conditions for a graph to be k -leaf-connected in terms of the (signless Laplacian) spectral radius of G or its complement are also presented. [ABSTRACT FROM AUTHOR]

Abstract: Let be the set of bipartite graphs with order n and diameter d. This paper characterizes the extremal graph with the maximal spectral radius in . Furthermore, the maximal spectral radius is a decreasing function on d. At last, bipartite graphs with the second largest spectral radius are determined. [Copyright &y& Elsevier]