Search

In light of the successful investigation of the adjacency matrix, a significant amount of its modification is observed employing numerous topological indices. The matrix corresponding to the well-known first Zagreb index is one of them. The entries of the first Zagreb matrix are d u i + d u j , if u i is connected to u j ; 0, otherwise, where d u i is degree of i-th vertex. The current work is concerned with the mathematical properties and chemical significance of the spectral radius ( ρ 1 ) associated with this matrix. The lower and upper bounds of ρ 1 are computed with characterizing extremal graphs for the class of unicyclic graphs and trees. The chemical connection of the first Zagreb spectral radius is established by exploring its role as a structural descriptor of molecules. The isomer discrimination ability of ρ 1 is also explained. [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]

For a set of graphs F , a graph is said to be F -free if it does not contain any graph in F as a subgraph. Let Ex s p (n , F) denote the graphs with the maximum spectral radius among all F -free graphs of order n. A linear forest is a graph whose connected components are paths. Denote by L s the family of all linear forests with s edges. In this paper the graphs in Ex s p (n , { K k + 1 , L s }) will be completely characterized when n is appropriately large. [ABSTRACT FROM AUTHOR]

The spectral radius ρ (A) is the maximum absolute value of the eigenvalues of a matrix A. In this paper, we establish some relationship between the spectral radius of a symmetric matrix and its principal submatrices, i.e., if A is partitioned as a 2 × 2 block matrix A = ( 0 A 12 A 21 A 22 ) , then ρ (A) 2 ≤ ρ 2 2 + θ ⁎ , where θ ⁎ is the largest real root of the equation μ 2 = (x − ν) 2 (ρ 2 2 + x) and ρ 2 = ρ (A 22) , μ = ρ (A 12 A 22 A 21) , ν = ρ (A 12 A 21). Furthermore, the results are used to obtain several upper bounds of the spectral radius of graphs, which strengthen or improve some known results. [ABSTRACT FROM AUTHOR]

In this note we show that for each positive integer a⩾2 there exist infinitely many trees whose spectral radius is equal to 2a. Such trees are obtained by replacing the central edge of the double star S(a,2a−2) with suitable bidegreed caterpillars.

Copyright of Operations Research Transactions / Yunchouxue Xuebao is the property of Editorial office of Operations Research Transactions and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

For a set of graphs F , let ex (n , F) and spex (n , F) denote the maximum number of edges and the maximum spectral radius of an n -vertex F -free graph, respectively. Nikiforov (LAA , 2007) gave the spectral version of the Turán Theorem by showing that spex (n , K k + 1) = λ (T k (n)) , where T k (n) is the k -partite Turán graph on n vertices. In the same year, Feng, Yu and Zhang (LAA) determined the exact value of spex (n , M s + 1) , where M s + 1 is a matching with s + 1 edges. Recently, Alon and Frankl (arXiv:2210.15076) gave the exact value of ex (n , { K k + 1 , M s + 1 }). In this article, we give the spectral version of the result of Alon and Frankl by determining the exact value of spex (n , { K k + 1 , M s + 1 }) when n is large. [ABSTRACT FROM AUTHOR]

In this article, we consider the relationships between walks in a signed graph G˙\dot{G} and its eigenvalues, with a particular focus on the largest absolute value of its eigenvalues ρ(G˙)\rho \left(\dot{G}), known as the spectral radius. Among other results, we derive a sequence of lower bounds for ρ(G˙)\rho \left(\dot{G}) expressed in terms of walks or closed walks. We also prove that ρ(G˙)\rho \left(\dot{G}) attains the spectral radius of the underlying graph GG if and only if G˙\dot{G} is switching equivalent to GG or its negation. It is proved that the length kk of the shortest negative cycle in G˙\dot{G} and the number of such cycles are determined by the spectrum of G˙\dot{G} and the spectrum of GG. Finally, a relation between kk and characteristic polynomials of G˙\dot{G} and GG is established.

Let G = (V , E) be a finite undirected graph of order n and of size m. Let Δ and δ be the largest and the smallest degree of G , respectively. The spectral radius of G is the largest eigenvalue of the adjacency matrix of the graph G. In this note we give new bounds on the spectral radius of { C 3 , C 4 } -free graphs in terms of m , n , Δ and δ. Computer search shows that in most of the cases the bounds derived in this note are better than the existing bounds. [ABSTRACT FROM AUTHOR]

Let G be a graph of size m and ρ (G) be the spectral radius of its adjacency matrix. A graph is said to be F -free if it does not contain a subgraph isomorphic to F. Let θ 1 , 2 , 3 denote the graph obtained from three internally disjoint paths with the same pair of endpoints, where the three paths are of lengths 1, 2, 3, respectively. Recently, Li, Sun and Wei showed that for any θ 1 , 2 , 3 -free graph G of size m ≥ 8 , ρ (G) ≤ 1 + 4 m − 3 2 , with equality if and only if G ≅ S m + 3 2 , 2 , where S m + 3 2 , 2 = K 2 ▿ K m − 1 2 ‾. However, this bound is not attainable when m is even. In this paper, we characterize the graphs with the maximum spectral radius over K 2 , r + 1 -free non-star graphs with m ≥ (4 r + 2) 2 + 1 , the graphs with the maximum spectral radius over θ 1 , 2 , 3 -free graphs with m ≥ 22 when m is even, and the graphs with the second largest spectral radius over θ 1 , 2 , 3 -free graphs with m ≥ 22 when m is odd. [ABSTRACT FROM AUTHOR]

In a graph G, if di is the degree of a vertex vi, the geometric-arithmetic matrix GA(G) is a square matrix whose [Formula: see text]-th entry is [Formula: see text] whenever vertices i and j are adjacent and 0 otherwise. The set of all eigenvalues of GA(G) including multiplicities is known as the geometric-arithmetic spectrum of G. The difference between the largest and the smallest geometric-arithmetic eigenvalue is called the geometric-arithmetic spread [Formula: see text] of G. In this article, we investigate some properties of [Formula: see text] We obtain lower and upper bounds of [Formula: see text] and show the existence of graphs for which equality holds. Further, [Formula: see text] is computed for various graph operations.

In this article, we consider the generalization of the Laplacian matrix for hypergraphs to obtain several results related to spectral properties of hypergraphs. This generalization of Laplacian matrix was defined in 2021 by Anirban Banerjee. We first supply a necessary and sufficient condition on the Laplacian spectral radius of hypergraphs such that the complement of that hypergraph is connected. We give bounds for the Laplacian spectral radius of k -uniform hypergraphs in terms of some invariants of hypergraph, such as the maximum degree, minimum degree, first Zagreb index, and the chromatic number. As an application of these results, some upper bounds of the Nordhaus-Gaddum type are obtained for the sum of Laplacian spectral radius of a k -uniform hypegraphs and its complement, and product of Laplacian spectral radius of a k -uniform hypegraphs and its complement. It is known that the second largest Laplacian eigenvalue for graphs is greater or equal to the second highest degree of graphs. We show by an example that this result is not true for 3-uniform hypergraphs in general. Finally, we supply a class of 3-uniform hypergraphs for which the second largest Laplacian eigenvalue is greater or equal to the second highest degree. [ABSTRACT FROM AUTHOR]

Let G ˙ be an unbalanced signed graph. In this paper, we establish that e (G ˙) ⩽ 1 2 (n 2 − n) − (n − 3) and ρ (G ˙) ⩽ n − 2 if G ˙ does not contain unbalanced K 4 as a signed subgraph. Moreover, comprehensive characterizations of the extremal signed graphs have been obtained. • The situation that the index of signed graph equals to the spectral radius of underlying graph has been characterized. • We determine the Turán number of K 4 − in unbalanced signed graph, and we characterize all the extremal signed graphs. • We solve the spectral Turán problem among all K 4 − -free unbalanced signed graphs. [ABSTRACT FROM AUTHOR]

G is a simple connected graph with adjacency matrix A(G) and degree diagonal matrix D(G). The signless Laplacian matrix of G is defined as Q(G) = D(G) + A(G). In 2017, Nikiforov [1] defined the matrix Aα(G) = α D(G) + (1 − α)A(G) for α ∈ [0,1]. The Aα-spectral radius of G is the maximum eigenvalue of Aα (G). In 2019, Liu et al. [2] defined the matrix Θk(G) as Θk (G) = kD(G) + A(G), for k ∈ ℝ. In this paper, we present a new type of lower bound for the Aα-spectral radius of a graph after vertex deletion. Furthermore, we deduce some corollaries on Θk (G), A(G), Q(G) matrices. [ABSTRACT FROM AUTHOR]

Let S n , 2 be the graph obtained by joining each vertex of K 2 to n − 2 isolated vertices, and let S n , 2 − be the graph obtained from S n , 2 by deleting an edge incident to a vertex of degree two. Recently, Zhai, Lin and Shu [20] showed that ρ (G) ≤ 1 + 4 m − 3 2 for any C 5 -free graph of size m ≥ 8 or C 6 -free graph of size m ≥ 22 , with equality if and only if G ≅ S m + 3 2 , 2 (possibly, with some isolated vertices). However, this bound is sharp only for odd m. Motivated by this, we want to obtain a sharp upper bound of ρ (G) for C 5 -free or C 6 -free graphs with m edges. In this paper, we prove that if G is a C 5 -free graph of even size m ≥ 14 or C 6 -free graph of even size m ≥ 74 , and G contains no isolated vertices, then ρ (G) ≤ ρ ˜ (m) , with equality if and only if G ≅ S m + 4 2 , 2 − , where ρ ˜ (m) is the largest root of x 4 − m x 2 − (m − 2) x + (m 2 − 1) = 0. [ABSTRACT FROM AUTHOR]

If A(G) and D(G) are respectively the adjacency matrix and the diagonal matrix of vertex degrees of a connected graph G, the generalized adjacency matrix Aα(G) is defined as Aα(G) = α D(G) + (1 - α) A(G), where 0 ≤ α ≤ 1. The Aα (or generalized) spectral radius λ(Aα(G)) (or simply λα) is the largest eigenvalue of Aα(G). In this paper, we show that λα ≤ α Δ + (1 - α)√ 2m ( 1 - 1/ω), where m, Δ and ω = ω(G) are respectively the size, the largest degree and the clique number of G. Further, if G has order n, then we show that ... where di and mi are respectively the degree and the average 2-degree of the vertex Vi. [ABSTRACT FROM AUTHOR]

A graph G is F -free, if it contains no F as a subgraph. A Brualdi-Solheid-Turán type problem asks what is the maximum spectral radius of an F -free graph of order n ? Let K a , b • K 3 denote the graph obtained by identifying a vertex of K a , b belonging to the part of size b and a vertex of K 3. In this paper, we consider about a Brualdi-Solheid-Turán type problem on non-bipartite graphs. We prove that if G is a non-bipartite graph with order n ≥ 21 and ρ (G) ≥ ρ (K ⌈ n − 2 2 ⌉ , ⌊ n − 2 2 ⌋ • K 3) , then G contains a pentagon unless G ≅ K ⌈ n − 2 2 ⌉ , ⌊ n − 2 2 ⌋ • K 3. [ABSTRACT FROM AUTHOR]

A blow-up of a graph G , is obtained from G by replacing each vertex v i of G with an independent set V i of n i vertices and joining each vertex in V i with each vertex in V j provided v i v j ∈ E (G). Let M n (G) be the set of all the blow-ups of G such that each n i ≥ 1 and ∑ i = 1 | G | n i = n. Monsalve and Rada (2021) [9] proposed three conjectures on the extremal spectral radii of M n (P k) and M n (C k). In this paper, we confirm the first two conjectures and construct an infinite class of graphs to illustrate the third conjecture is not true. [ABSTRACT FROM AUTHOR]

For a given complex square matrix A with constant row sum, we establish two new eigenvalue inclusion sets. Using these bounds, first, we derive bounds for the second largest and the smallest eigenvalues of adjacency matrices of fc-regular graphs. Then we establish some bounds for the second largest and the smallest eigenvalues of the normalized adjacency matrices of graphs and the second smallest and the largest eigenvalues of the Laplacian matrices of graphs. The sharpness of these bounds is verified by examples. [ABSTRACT FROM AUTHOR]

Abstract The spectral radius of a graph is the largest eigenvalue of the adjacency matrix corresponding to this graph. Let G be a graph with long pendant paths. In this note, we estimate the spectral radius of G , by obtaining appropriate upper and lower bounds. As an application, the spectral radius of some k-ary trees are estimated. [ABSTRACT FROM AUTHOR]

We obtain bounds for the largest and least eigenvalues of the adjacency matrix of a simple undirected graph. We find upper bound for the second largest eigenvalue of the adjacency matrix. We prove that the bounds obtained here improve on the existing bounds and also illustrate them with examples. [ABSTRACT FROM AUTHOR]

Let G be a graph with adjacency matrix A ( G ) and let D ( G ) be the diagonal matrix of the degrees of G . For every real α ∈ [ 0 , 1 ] , write A α ( G ) for the matrix A α ( G ) = α D ( G ) + ( 1 − α ) A ( G ) . This paper presents some extremal results about the spectral radius ρ α ( G ) of A α ( G ) that generalize previous results about ρ 0 ( G ) and ρ 1 / 2 ( G ) . In particular, write B p , q , r be the graph obtained from a complete graph K p by deleting an edge and attaching paths P q and P r to its ends. It is shown that if α ∈ [ 0 , 1 ) and G is a graph of order n and diameter at least k , then ρ α ( G ) ≤ ρ α ( B n − k + 2 , ⌊ k / 2 ⌋ , ⌈ k / 2 ⌉ ) , with equality holding if and only if G = B n − k + 2 , ⌊ k / 2 ⌋ , ⌈ k / 2 ⌉ . This result generalizes results of Hansen and Stevanović [5] , and Liu and Lu [7] . [ABSTRACT FROM AUTHOR]

Let G be a graph with adjacency matrix A ( G ) and let D ( G ) be the diagonal matrix of the degrees of G . For any real α ∈ [ 0 , 1 ] , Nikiforov [3] defined the matrix A α ( G ) as A α ( G ) = α D ( G ) + ( 1 − α ) A ( G ) . The largest eigenvalue of A α ( G ) is called the A α -spectral radius of G . In this paper, we give three edge graft transformations on A α -spectral radius. As applications, we determine the unique graph with maximum A α -spectral radius among all connected graphs with diameter d , and determine the unique graph with minimum A α -spectral radius among all connected graphs with given clique number. In addition, some bounds on the A α -spectral radius are obtained. [ABSTRACT FROM AUTHOR]

A Hamiltonian graph G is hyper-Hamiltonian if G − v is Hamiltonian for any v ∈ V ( G ) . In this paper, we give some sufficient conditions for a graph to be hyper-Hamiltonian. We provide both, spectral and non-spectral conditions for hyper-Hamiltonicity. [ABSTRACT FROM AUTHOR]

A graph G is called H -free, if it does not contain H as a subgraph. In 2010, Nikiforov proposed a Brualdi-Solheid-Turán type problem: what is the maximum spectral radius of an H -free graph of order n ? In this paper, we consider the Brualdi-Solheid-Turán type problem for non-bipartite graphs. Let K a , b • K 3 denote the graph obtained by identifying a vertex of K a , b in the part of size b and a vertex of K 3. We prove that if G is a non-bipartite graph of order n satisfying ρ (G) ≥ ρ (K ⌈ n − 2 2 ⌉ , ⌊ n − 2 2 ⌋ • K 3) , then G contains all odd cycles C 2 l + 1 for each integer l ∈ [ 2 , k ] unless G ≅ K ⌈ n − 2 2 ⌉ , ⌊ n − 2 2 ⌋ • K 3 , provided that n is sufficiently large with respect to k. This resolves the problem posed by Guo, Lin and Zhao (2021). [ABSTRACT FROM AUTHOR]

We prove a result concerning the behavior of the spectral radius of a hypergraph under relocations of edges. We determine the unique hypergraphs with maximum spectral radius among connected k -uniform hypergraphs with fixed number of pendant edges, the unique k -uniform hypertrees with respectively maximum, second maximum and third maximum spectral radius, the unique k -uniform unicyclic hypergraphs ( k -uniform linear unicyclic hypergraphs, respectively) with respectively maximum and second maximum spectral radius. We also determine the unique hypergraphs with maximum spectral radius among k -uniform unicyclic hypergraphs with given girth. [ABSTRACT FROM AUTHOR]

We give sharp upper and lower bounds for the spectral radius of a nonnegative matrix with positive row sums using average 3-row sums, compare these bounds with the existing bounds using the average 2-row sums by examples, and apply them to the adjacency matrix and the signless Laplacian matrix of a digraph or a graph. [ABSTRACT FROM AUTHOR]

Let G be a graph with adjacency matrix A(G), and let D(G) be the diagonal matrix of the degrees of G: The signless Laplacian Q(G) of G is defined as Q(G) := A(G) +D(G). Cvetković called the study of the adjacency matrix the A-spectral theory, and the study of the signless Laplacian-the Q-spectral theory. To track the gradual change of A(G) into Q(G), in this paper it is suggested to study the convex linear combinations Aα(G) of A(G) and D(G) defined byAα (G) := αD(G) + (1 - α )A(G) , 0 ≤ α ≤ 1. This study sheds new light on A(G) and Q(G), and yields, in particular, a novel spectral Turán theorem. A number of open problems are discussed. [ABSTRACT FROM AUTHOR]