Search

In this paper, we study the relationship between spectral radius and maximum average degree of graphs. By using this relationship and the previous technique of Li and Ning in (J Graph Theory 103:486–492, 2023), we prove that, for any given positive number ε < 1 3 , if n is a sufficiently large integer, then any graph G of order n with ρ (G) > n 2 4 contains a cycle of length t for all integers t ∈ [ 3 , (1 3 - ε) n ] , where ρ (G) is the spectral radius of G. This improves the result of Li and Ning (2023). [ABSTRACT FROM AUTHOR]

Let S be a subset of V(G). The vertices of S are colored black and the vertices of V (G) - S are colored white. The color-change-rule is defined as if there is a black vertex u having an unique white neighbor v, then change the color of v to black. The zero forcing number of a graph, denoted by Z(G), is the minimum cardinality of a set S such that all vertices of V(G) are black by repeating the color-change-rule, which was proposed at the AIM-minimum rank group in 2008 to bound the maximal nullity of G. Hence it has received much attention. Our interest is to study the zero forcing number of graphs with matching number α ′ (G) and cyclomatic number c(G). In the paper, utilizing the alternating path and an operation associated with a vertex partition, we verify the sharp bounds that n (G) - 2 α ′ (G) ≤ Z (G) ≤ n (G) - α ′ (G) + c (G) - 1 for n (G) ≥ 3 . The extremal graphs attain the upper bound are completely characterized. [ABSTRACT FROM AUTHOR]

For an integer ℓ ≥ 2 , a P ≥ ℓ -factor of a graph G is a spanning subgraph in which each component is a path of order at least ℓ . In this paper, we characterize the extremal graphs with maximum spectral radius among all connected graphs of given order with prescribed minimum degree and without a P ≥ 2 -factor or a P ≥ 3 -factor. This generalizes the result in Li and Miao (Discrete Math 344:112588, 2021). [ABSTRACT FROM AUTHOR]

Let G be an irregular graph on n vertices with maximum degree Δ ≥ 3 and diameter D ≥ 3 . The spectral radius of G, which is denoted by ρ (G) , is the largest eigenvalue of the adjacency matrix of G. In this paper, a new lower bound of Δ - ρ (G) is given, which improves the previous bounds intrinsically. [ABSTRACT FROM AUTHOR]

Let G be a connected irregular graph on n vertices with maximum degree Δ and diameter D. The spectral radius of G, which is denoted by ρ (G) , is the largest eigenvalue of the adjacency matrix of G. In this paper, we study the lower bound of Δ - ρ (G) . As a result, a new lower bound is obtained which improves the known lower bounds of Δ - ρ (G) . [ABSTRACT FROM AUTHOR]

E.R. van Dam and G.R. Omidi generalized the concept of strongly regular graphs as follows. If for any two vertices the number of ℓ -walks (walks of length ℓ ) from one vertex to the other is the same which depends only on whether the two vertices are the same, adjacent or non-adjacent, then G is called a strongly ℓ -walk-regular graph. The existence of strongly ℓ -walk-regular graphs which are not strongly 3-walk-regular graphs is unknown. In this paper, we prove that the edge-connectivity of a connected strongly 3-walk-regular graph G of degree k ≥ 3 is equal to k. Moreover, if G is not the graph formed by adding a perfect matching between two copies of K 4 , then each edge cut set of size k is precisely the set of edges incident with a vertex of G. For a regular graph G in general, we also give a sufficient and tight condition such that G is 1-extendable. [ABSTRACT FROM AUTHOR]

Let G be a graph on even number of vertices. A perfect matching of G is a set of independent edges which cover each vertex of G. For an integer t ≥ 1 , G is t-extendable if G has a perfect matching, and for any t independent edges, G has a perfect matching which contains these given t edges. The graph G is bi-critical if for any two vertices u and v, the graph G - u , v contains a perfect matching. Let G be a connected k-regular graph. In this paper, we obtain two sharp sufficient eigenvalue conditions for a connected k-regular graph to be 1-extendable and bi-critical, respectively. Our results are in term of the second largest eigenvalue of the adjacency matrix of G. We also give examples that show that there is no good spectral characterization (in term of the second largest eigenvalue of the adjacency matrix) for 2-extendability of regular graphs in general. Also, for any integer 1 ≤ ℓ < k + 2 2 , we obtain an eigenvalue condition for G to be (ℓ + 1) -connected. [ABSTRACT FROM AUTHOR]

Let G be a connected graph. An edge cut set M of G is a cyclic edge cut set if there are at least two components of G - M which contain a cycle. The cyclic edge-connectivity of G is the minimum cardinality of a cyclic edge cut set (if exists) of G. In this paper, we show that the cyclic edge-connectivity of a connected strongly regular graph G (not K 3 , 3 ) of degree k ≥ 3 with girth c is equal to (k - 2) c , where c = 3 , 4 or 5. Moreover, if G is not the triangular graph srg-(10, 6, 3, 4), the complete multi-partite graph K 2 , 2 , 2 , 2 or the lattice graph srg-(16, 6, 2, 2), then each cyclic edge cut set of size (k - 2) c is precisely the set of edges incident with a cycle of length c in G. [ABSTRACT FROM AUTHOR]