Search

Modeling complex systems that consist of different types of objects leads to multilayer networks, in which vertices are connected by both inter-layer and intra-layer edges. In this paper, we investigate multiplex networks, in which vertices in different layers are identified with each other, and the only inter-layer edges are those that connect a vertex with its copy in other layers. Let the third-order adjacency tensor A ∈ R N × N × L and the parameter γ ≥ 0 , which is associated with the ease of communication between layers, represent a multiplex network with N vertices and L layers. To measure the ease of communication in a multiplex network, we focus on the average inverse geodesic length, which we refer to as the multiplex global efficiency e A (γ) by means of the multiplex path length matrix P ∈ R N × N . This paper generalizes the approach proposed in [15] for single-layer networks. We describe an algorithm based on min-plus matrix multiplication to construct P, as well as variants P K that only take into account multiplex paths made up of at most K intra-layer edges. These matrices are applied to detect redundant edges and to determine non-decreasing lower bounds e A K (γ) for e A (γ) , for K = 1 , 2 , ⋯ , N - 2 . Finally, the sensitivity of e A K (γ) to changes of the entries of the adjacency tensor A is investigated to determine edges that should be strengthened to enhance the multiplex global efficiency the most. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of computing the entire sequence of the maximum degree of minors of a block-structured symbolic matrix (a generic partitioned polynomial matrix) A = (A α β x α β t d α β ) , where A α β is a 2 × 2 matrix over a field F , x α β is an indeterminate, and d α β is an integer for α = 1 , 2 , ⋯ , μ and β = 1 , 2 , ⋯ , ν , and t is an additional indeterminate. This problem can be viewed as an algebraic generalization of the maximum weight bipartite matching problem. The main result of this paper is a combinatorial -time algorithm for computing the entire sequence of the maximum degree of minors of a (2 × 2) -type generic partitioned polynomial matrix of size 2 μ × 2 ν . We also present a minimax theorem, which can be used as a good characterization (NP ∩ co-NP characterization) for the computation of the maximum degree of minors of order k. Our results generalize the classical primal-dual algorithm (the Hungarian method) and minimax formula (Egerváry's theorem) for the maximum weight bipartite matching problem. [ABSTRACT FROM AUTHOR]

The k-token graph F k (G) of a graph G is the graph whose vertices are the k-subsets of vertices from G, two of which are adjacent whenever their symmetric difference is a pair of adjacent vertices in G. It was proved that the algebraic connectivity of F k (G) equals the algebraic connectivity of G with a proof using random walks and interchange of processes on a weighted graph. However, no algebraic or combinatorial proof is known, and it would be a hit in the area. In this paper, we algebraically prove that the algebraic connectivity of F k (G) equals the one of G for new infinite families of graphs, such as trees, some graphs with hanging trees, and graphs with minimum degree large enough. Some examples of these families are the following: the cocktail party graph, the complement graph of a cycle, and the complete multipartite graph. [ABSTRACT FROM AUTHOR]

In this paper, we study a distance-regular graph Γ having a nonintegral eigenvalue θ and give some restriction for the intersection numbers. As an application, we show that (the collinearity graph of) a thick regular near hexagon has a nonintegral eigenvalue if and only if it is a generalized hexagon of order (s, 1) such that s is not a square. [ABSTRACT FROM AUTHOR]

The permanent of a square matrix M = (m ij) k × k is p e r (M) = ∑ σ ∏ i = 1 k m i σ (i) , where the sum is taken over all permutations σ of the set { 1 , 2 , ... , k } . For a simple connected graph G, its signless Laplacian matrix Q(G) is D (G) + A (G) , where D(G) is the degree diagonal matrix and A(G) is the adjacency matrix of G. The signless Laplacian permanental polynomial of G is ψ (Q (G) ; x) = p e r (x I - Q (G)) . In this paper, we give the representation of a graph with two types of degrees, d (> 1) and 1, in terms of its signless Laplacian permanental polynomial. The unicyclic graphs discussed here are UC(r, d), where the unique cycle is C r with all whose vertices have degree d (> 2) , and the remaining are degree 1 vertices. We show that UC(r, d) is determined uniquely by its signless Laplacian permanental polynomial for r = 3 , 4 , 5 , 6 and for any d. We also prove that the unicyclic graph obtained from UC(r, d) by making d - 1 new vertices adjacent to a pendant vertex, is also determined uniquely by its signless Laplacian permanental polynomial, for r = 4 , 5 . Finally, we show that among all connected graphs, UC(r, 3), for every r ≥ 3 , is determined uniquely by its signless Laplacian permanental polynomial. [ABSTRACT FROM AUTHOR]

Laplacian matrix and its spectrum are commonly used for giving a measure in networks in order to analyse its topological properties. In this paper, Laplacian matrix of graphs and their spectrum are studied. Laplacian energy of a graph G of order n is defined as LE (G) = ∑ i = 1 n | λ i (L) - d ¯ | , where λ i (L) is the i-th eigenvalue of Laplacian matrix of G, and d ¯ is their average. If LE (G) = LE (K n) for the complete graph K n of order n, then G is known as L-borderenergetic graph. In the first part of this paper, we construct three infinite families of non-complete disconnected L-borderenergetic graphs: Λ 1 = { G b , j , k = [ (((j - 2) k - 2 j + 2) b + 1) K (j - 1) k - (j - 2) ] ∪ b (K j × K k) | b , j , k ∈ Z + } , Λ 2 = { G 2 , b = [ K 6 ∇ b (K 2 × K 3) ] ∪ (4 b - 2) K 9 | b ∈ Z + } , Λ 3 = { G 3 , b = [ b K 8 ∇ b (K 2 × K 4) ] ∪ (14 b - 4) K 8 b + 6 | b ∈ Z + } , where ∇ is join operator and × is direct product operator on graphs. Then, in the second part of this work, we construct new infinite families of non-complete connected L-borderenergetic graphs Ω 1 = { K 2 ∇ a K 2 r ¯ | a ∈ Z + } , Ω 2 = { a K 3 ∪ 2 (K 2 × K 3) ¯ | a ∈ Z + } and Ω 3 = { a K 5 ∪ (K 3 × K 3) ¯ | a ∈ Z + } , where G ¯ is the complement operator on G. [ABSTRACT FROM AUTHOR]

Let R be a finite commutative ring with unity, and let G = (V , E) be a simple graph. The zero-divisor graph, denoted by Γ (R) is a simple graph with vertex set as R, and two vertices x , y ∈ R are adjacent in Γ (R) if and only if x y = 0 . In [5], the authors have studied the Laplacian eigenvalues of the graph Γ (Z n) and for distinct proper divisors d 1 , d 2 , ⋯ , d k of n, they defined the sets as, A d i = { x ∈ Z n : (x , n) = d i } , where (x, n) denotes the greatest common divisor of x and n. In this paper, we show that the sets A d i , 1 ≤ i ≤ k are actually orbits of the group action: A u t (Γ (R)) × R ⟶ R , where A u t (Γ (R)) denotes the automorphism group of Γ (R) . Our main objective is to determine new classes of threshold graphs, since these graphs play an important role in several applied areas. For a reduced ring R, we prove that Γ (R) is a connected threshold graph if and only if R ≅ F q or R ≅ F 2 × F q . We provide classes of threshold graphs realized by some classes of local rings. Finally, we characterize all finite commutative rings with unity of which zero-divisor graphs are not threshold. [ABSTRACT FROM AUTHOR]

The distance spectral radius of a connected hypergraph is the largest eigenvalue of its distance matrix. In this paper, we determine the k-uniform hypertree with the minimal spectral radius among all k-uniform hypertrees with m edges and diameter d, where 3 ≤ d ≤ m - 1 . [ABSTRACT FROM AUTHOR]

In 2022, the second author found a prolific construction of strongly regular graphs, which is based on joining a coclique and a divisible design graph with certain parameters. The construction produces strongly regular graphs with the same parameters as the complement of the symplectic graph Sp (2 d , q) . In this paper, we determine the parameters of strongly regular graphs which admit a decomposition into a divisible design graph and a coclique attaining the Hoffman bound. In particular, it is shown that when the least eigenvalue of such a strongly regular graph is a prime power, its parameters coincide with those of the complement of Sp (2 d , q) . Furthermore, a generalization of the construction is discussed. [ABSTRACT FROM AUTHOR]

In this paper we prove that every totally real algebraic integer λ of degree d ≥ 2 occurs as an eigenvalue of some tree of height at most d (d + 1) / 2 + 3 . In order to prove this, for a given algebraic number α ≠ 0 , we investigate an additive semigroup that contains zero and is closed under the map x ↦ α / (1 - x) for x ≠ 1 . The problem of finding the smallest such semigroup seems to be of independent interest. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the normalized distance Laplacian spectrum of the zero-divisor graph of a commutative ring R , denoted by Γ (R) , where R is taken as the ring of integers modulo n. The graph has vertex set Z (R) ∗ , which is the set of nonzero zero-divisors of R , and two vertices x and y are connected by an edge if and only if x y = 0 . Specifically, we analyze the normalized distance Laplacian spectrum of Γ (Z n) , where n = p S q T , p and q are primes with p < q , and S and T are positive integers. [ABSTRACT FROM AUTHOR]

Let G be a connected graph with vertex set V (G) = { v 1 , v 2 , ... , v n } . Recall that the reciprocal distance signless Laplacian matrix of G is defined to be R Q (G) = R T (G) + R D (G) , where RD(G) is the reciprocal distance matrix, and R T i is the reciprocal distance degree of vertex v i for i = 1 , 2 , ... , n , R T (G) = diag (R T 1 , R T 2 , ... , R T n) . Denote by μ 1 (R Q (G)) and μ n (R Q (G)) the largest eigenvalue and the least eigenvalue of RQ(G), respectively. The reciprocal distance signless Laplacian spread of G is defined as S RQ (G) = μ 1 (R Q (G)) - μ n (R Q (G)) . In this paper, we obtain some bounds on reciprocal distance signless Laplacian spread of a graph. [ABSTRACT FROM AUTHOR]

Let A (G) and D (G) be the adjacency and distance matrices of a graph G respectively. The adjacency energy or A -energy E A (G) of a graph G is defined as the sum of the absolute values of the eigenvalues of A (G) . Analogously, the D -energy E D (G) is defined to be the sum of the absolute values of the eigenvalues of D (G) . One of the interesting problems on graph energy is to characterize those graphs which are equienergetic with respect to both the adjacency and distance matrices. A weaker problem is to construct the families of graphs which are equienergetic with respect to both the adjacency and distance matrices. In this paper, we find the explicit relations between A -energy and D -energy of certain families of graphs. As a consequence, we provide an answer to the above open problem (Indulal in https://icgc2020.wordpress.com/invitedlectures, 2020; http://www.facweb.iitkgp.ac.in/rkannan/gma.html, 2020) [ABSTRACT FROM AUTHOR]

This paper investigates the interplay between the algebraic properties of the rings, the combinatorial properties of their corresponding zero-divisor graphs, and the associated Hermitian matrix of such graphs. For a finite ring R, its zero-divisor graph may contain both directed edges and undirected edges; such graphs are called mixed graphs. The Hermitian matrices of mixed graphs are natural generalizations of the adjacency matrices of undirected graphs. In this paper, we completely determine the structure and the Hermitian eigenvalues of the zero-divisor graph Γ (D × R) by using the structure and the Hermitian eigenvalues of the zero-divisor graph Γ (R) . As applications, we investigate Γ (D × R) for some special R and extend some known results on this topic. [ABSTRACT FROM AUTHOR]

Let λ 2 be the second largest eigenvalue of the adjacency matrix of a connected graph. In 2021, Liu, Chen and Stanić determined all the connected { K 1 , 3 , K 5 - e } -free graphs whose second largest eigenvalue λ 2 ⩽ 1 . In this paper, we completely identify all the connected { K 2 , 3 , K 4 } -minor free graphs whose second largest eigenvalue does not exceed 1. That is, we characterize all the connected outerplanar graphs satisfying λ 2 ⩽ 1 . Furthermore, all the maximal outerplanar graphs having the same property can be deduced by our result obtained in this paper. Our main tools include analyzing the local structure of the outerplanar graph with respect to its girth. [ABSTRACT FROM AUTHOR]

In this paper, first we consider some partitioned matrices having some special kind of blocks, and we obtain their eigenvalues and eigenvectors. From these, we deduce several results on the eigenvalues of partitioned matrices in the literature. Next we consider an extension of a generalized join of graphs introduced by Hedetniemi (On classes of graphs defined by special cutsets of lines. In: Many facets of graph theory. Proceedings of the conference held at Western MiGammagan University, Kalamazoo/Mi, 1968. Lecture notes in mathematics, vol 110, pp 171–189, 1969), we call it the M -join of H k . The spectra of partitioned matrices allow to detect the adjacency, the Laplacian and the signless Laplacian spectrum of old and new type of join of graphs. Further, we have constructed several pairs of simultaneously A-cospectral, L-cospectral and Q-cospectral graphs. [ABSTRACT FROM AUTHOR]

The fact that the adjacency matrix of every finite graph is diagonalizable plays a fundamental role in spectral graph theory. Since this fact does not hold in general for digraphs, it is natural to ask whether it holds for digraphs with certain level of symmetry. Interest in this question dates back to the early 1980 s, when P. J. Cameron asked for the existence of arc-transitive digraphs with non-diagonalizable adjacency matrix. This was answered in the affirmative by Babai (J Graph Theory 9:363–370, 1985). Then Babai posed the open problems of constructing a 2-arc-transitive digraph and a vertex-primitive digraph whose adjacency matrices are not diagonalizable. In this paper, we solve Babai's problems by constructing an infinite family of s-arc-transitive digraphs for each integer s ≥ 2 , and an infinite family of vertex-primitive digraphs, both of whose adjacency matrices are non-diagonalizable. [ABSTRACT FROM AUTHOR]

Let G be a connected graph. Denote by d i the degree of a vertex v i in G. Let f (x , y) > 0 be a real symmetric function. Consider an edge-weighted graph in such a way that for each edge v i v j of G, the weight of v i v j is equal to the value f (d i , d j) . Therefore, we have a degree-based weighted adjacency matrix A f (G) of G, in which the (i, j)-entry is equal to f (d i , d j) if v i v j is an edge of G and is equal to zero otherwise. Let x be a positive eigenvector corresponding to the largest eigenvalue λ 1 (A f (G)) of the weighted adjacency matrix A f (G) . In this paper, we first consider the unimodality of the eigenvector x on an induced path of G. Second, if f(x, y) is increasing in the variable x, then we investigate how the largest weighted adjacency eigenvalue λ 1 (A f (G)) changes when G is perturbed by vertex contraction or edge subdivision. The aim of this paper is to unify the study of spectral properties for the degree-based weighted adjacency matrices of graphs. [ABSTRACT FROM AUTHOR]

Let a network be represented by a simple graph G with n vertices. A common approach to investigate properties of a network is to use the adjacency matrix A = [ a ij ] i , j = 1 n ∈ R n × n associated with the graph G , where a ij > 0 if there is an edge pointing from vertex v i to vertex v j , and a ij = 0 otherwise. Both A and its positive integer powers reveal important properties of the graph. This paper proposes to study properties of a graph G by also using the path length matrix for the graph. The (i j) th entry of the path length matrix is the length of the shortest path from vertex v i to vertex v j ; if there is no path between these vertices, then the value of the entry is ∞ . Powers of the path length matrix are formed by using min-plus matrix multiplication and are important for exhibiting properties of G . We show how several known measures of communication such as closeness centrality, harmonic centrality, and eccentricity are related to the path length matrix, and we introduce new measures of communication, such as the harmonic K-centrality and global K-efficiency, where only (short) paths made up of at most K edges are taken into account. The sensitivity of the global K-efficiency to changes of the entries of the adjacency matrix also is considered. [ABSTRACT FROM AUTHOR]

Suppose G is a connected simple graph with the vertex set V (G) = { v 1 , v 2 , ⋯ , v n } . Let d G (v i , v j) be the distance between v i and v j . Then the distance matrix of G is D (G) = (d ij) n × n , where d ij = d G (v i , v j) . Since D(G) is a non-negative real symmetric matrix, its eigenvalues can be arranged λ 1 (G) ≥ λ 2 (G) ≥ ⋯ ≥ λ n (G) , where eigenvalues λ 1 (G) and λ n (G) are called the distance spectral radius and the least distance eigenvalue of G, respectively. In this paper, we characterize the unique graph whose distance spectral radius attains maximum and minimum among all complements of graphs with two pendent vertices, respectively. Furthermore, we determine the unique graph whose least distance eigenvalue attains minimum among all complements of graphs with two pendent vertices. [ABSTRACT FROM AUTHOR]

Suppose G is a connected simple graph with the vertex set V (G) = { v 1 , v 2 , ⋯ , v n } . Let d G (v i , v j) be the least distance between v i and v j in G. Then the distance matrix of G is D (G) = (d ij) n × n , where d ij = d G (v i , v j) . Since D(G) is a non-negative real symmetric matrix, its eigenvalues can be arranged λ 1 (G) ≥ λ 2 (G) ≥ ⋯ ≥ λ n (G) , where eigenvalues λ 1 (G) and λ n (G) are called the distance spectral radius and the least distance eigenvalue of G, respectively. In this paper, we characterize the unique graph whose distance spectral radius attains maximum and minimum among all complements of graphs of diameter greater than three, respectively. Furthermore, we determine the unique graph whose least distance eigenvalue attains minimum among all complements of graphs of diameter greater than three. [ABSTRACT FROM AUTHOR]

For a connected simple graph G, the generalized distance matrix is defined by D α : = α T r (G) + (1 - α) D (G) , 0 ≤ α ≤ 1 , where Tr(G) is the diagonal matrix of vertex transmissions and D(G) is the distance matrix. For particular values of α , we obtain the distance matrix, the distance Laplacian matrix and the distance signless Laplacian matrix and other uncountable distance based matrices. Let ∂ 1 ≥ ∂ 2 ≥ ⋯ ≥ ∂ n be the D α eigenvalues of G and p ≥ 2 a real number, the Schatten p-norm is the p-th root of the sum of p-th powers of eigenvalues of D α , α ∈ [ 1 2 , 1 ] , that is, ‖ D α ‖ p p = ∂ 1 p + ∂ 2 p + ⋯ + ∂ n p . In this paper, we obtain various bounds for ‖ D α ‖ p p in terms of different graph parameters and characterize the corresponding extremal graphs. [ABSTRACT FROM AUTHOR]

Given q-uniform hypergraphs (q-graphs) F, G and H, where G is a spanning subgraph of F, G is called weaklyH-saturated in F if the edges in E (F) \ E (G) admit an ordering e 1 , ... , e k so that for all i ∈ [ k ] the hypergraph G ∪ { e 1 , ... , e i } contains an isomorphic copy of H which in turn contains the edge e i . The weak saturation number of H in F is the smallest size of an H-weakly saturated subgraph of F. Weak saturation was introduced by Bollobás in 1968, but despite decades of study our understanding of it is still limited. The main difficulty lies in proving lower bounds on weak saturation numbers, which typically withstands combinatorial methods and requires arguments of algebraic or geometrical nature. In our main contribution in this paper we determine exactly the weak saturation number of complete multipartite q-graphs in the directed setting, for any choice of parameters. This generalizes a theorem of Alon from 1985. Our proof combines the exterior algebra approach from the works of Kalai with the use of the colorful exterior algebra motivated by the recent work of Bulavka, Goodarzi and Tancer on the colorful fractional Helly theorem. In our second contribution answering a question of Kronenberg, Martins and Morrison, we establish a link between weak saturation numbers of bipartite graphs in the clique versus in a complete bipartite host graph. In a similar fashion we asymptotically determine the weak saturation number of any complete q-partite q-graph in the clique, generalizing another result of Kronenberg et al. [ABSTRACT FROM AUTHOR]

In this paper, we consider the spectral radius of signless p-Laplacian of a graph, which is a generalization of the quadratic form of the signless Laplacian matrix for p = 2 . Let π = (d 0 , d 1 , … , d n - 1) be a non-increasing sequence of positive integers and G π the set of graphs with degree sequence π . In this paper, we obtain some transformations for graphs in G π that do not decrease the largest signless p-Laplacian eigenvalue of a graph. Furthermore, if ∑ i = 0 n - 1 d i = 2 n and d 2 ≥ 2 , then we identify the graph maximizing the signless p-Laplacian spectral radius among G π . As an application, we get the extremal graph maximizing the signless p-Laplacian spectral radius among all unicyclic graphs. [ABSTRACT FROM AUTHOR]

Let Γ = (X , R) denote a finite, simple, connected, and undirected non-bipartite graph with vertex set X and edge set R . Fix a vertex x ∈ X , and define R f = R \ { y z ∣ ∂ (x , y) = ∂ (x , z) } , where ∂ denotes the path-length distance in Γ . Observe that the graph Γ f = (X , R f) is bipartite. We say that Γ supports a uniform structure with respect to x whenever Γ f has a uniform structure with respect to x. Assume that Γ is a distance-regular graph with classical parameters (D , q , α , β) with q ≤ 1 . Recall that q is an integer, which is not equal to 0 or - 1 . The purpose of this paper is to study when Γ supports a uniform structure with respect to x. The main result of the paper is a complete classification of graphs with classical parameters with q ≤ 1 and D ≥ 4 that support a uniform structure with respect to x. [ABSTRACT FROM AUTHOR]

The splitting field S F (Γ) of a mixed graph Γ is the smallest field extension of Q which contains all eigenvalues of the Hermitian adjacency matrix of Γ . The extension degree [ S F (Γ) : Q ] is called the algebraic degree of Γ . In this paper, we determine the splitting fields and algebraic degrees of mixed Cayley graphs over abelian groups. This generalizes the main results of Mönius (J Algebra 594(15):154–169, 2022). Additionally, we provide a characterization of integral mixed Cayley graphs over abelian groups, which implies the main result of Kadyan and Bhattacharjya (Electron J Combin 28(4):P4.46, 2021). [ABSTRACT FROM AUTHOR]

Twin vertices in simple unweighted graphs are vertices that have the same neighbours, and, in the case of weighted graphs with possible loops, the corresponding incident edges have equal weights. In this paper, we explore the role of twin vertices in quantum state transfer. In particular, we provide characterizations of periodicity, perfect state transfer, and pretty good state transfer between twin vertices in a weighted graph with respect to its adjacency, Laplacian and signless Laplacian matrices. As an application, we provide characterizations of all simple unweighted double cones on regular graphs that exhibit periodicity, perfect state transfer, and pretty good state transfer. [ABSTRACT FROM AUTHOR]

For integers n ≥ 1 and m ≥ 0 , let D = D (n , m) denote the Doob scheme which is the direct product of n copies of Shrikhande graph and m copies of complete graph on four vertices. Let V denote the standard module of D with an inner product ⟨ u , v ⟩ = u t v ¯ where t and - denote transpose and complex conjugate, respectively. Fix a vertex x of D, and let T = T (x) denote the Terwilliger algebra of D with respect to x. We view T as a Lie algebra with respect to the usual commutator. Using Tanabe's results (JAC 6: 173–195, 1997) on characterization of irreducible T-modules, it was shown in (JAC 54: 979–998, 2021) that there exists a homomorphism π from the special orthogonal algebra so 4 to T and that each irreducible T-module is an irreducible π (so 4) -module. Let W denote an irreducible T-module. In this paper, we consider two Cartan subalgebras h and h ∗ of so 4 and obtain weight space decompositions W = ∑ r = 0 d ∑ s = 0 p W rs = ∑ k = 0 d ∑ l = 0 p W kl ∗ where d, p are uniquely determined by the parameters of W. We show that each W rs (resp. W kl ∗ ) is one-dimensional. Moreover, we describe how ⟨ W rs ∗ , W kl ⟩ is connected to Krawtchouk polynomials and we prove the relations π (h) W rs ∗ ⊆ W r - 1 , s ∗ + W r , s - 1 ∗ + W rs ∗ + W r + 1 , s ∗ + W r , s + 1 ∗ π (h ∗) W kl ⊆ W k - 1 , l + W k , l - 1 + W kl + W k + 1 , l + W k , l + 1 where W ij : = 0 and W ij ∗ : = 0 if i < 0 , j < 0 , i > d , or j > p . Additionally, we establish some connections between T and the tetrahedron algebra ⊠ . [ABSTRACT FROM AUTHOR]

One important topic in chemical graph theory is the extremal value problem of topological indices over chemical trees. The augmented Zagreb index is an important topological index, and it has attracted more and more attention because of having the best predicting ability for diverse of physical and chemical properties. In Cruz et al. (Appl Math Comput 380:125281, 2020) and Gao (MATCH Commun Math Comput Chem 89:699–722, 2023), the authors captured some conditions, respectively; they obtained extremal chemical trees for some topological indices which satisfied the conditions. Unfortunately, the augmented Zagreb index does not satisfy these conditions. Motivated by the results in Cruz et al. (Appl Math Comput 380:125281, 2020) and Gao (MATCH Commun Math Comput Chem 89:699–722, 2023), in this paper, we study the related issues about the augmented Zagreb index. The maximal augmented Zagreb index for chemical trees is determined; the corresponding extremal trees are characterized. [ABSTRACT FROM AUTHOR]

In this paper, we give various lower and upper bounds for the energy of graphs in terms of several topological indices of graphs: the first general multiplicative Zagreb index, the general Randić index, the general zeroth-order Randić index, the redefined Zagreb indices, and the atom-bond connectivity index. Moreover, we obtain new bounds for the energy in terms of certain graph invariants as diameter, girth, algebraic connectivity and radius. [ABSTRACT FROM AUTHOR]

Mantel’s theorem is a classical result in extremal graph theory which implies that the maximum number of edges of a triangle-free graph of order n. In 1970, Nosal obtained a spectral version of Mantel’s theorem which gave the maximum spectral radius of a triangle-free graph of order n. In this paper, the clique tensor of a graph G is proposed and the spectral Mantel’s theorem is extended via the clique tensor. Furthermore, a sharp upper bound of the number of cliques in G via the spectral radius of the clique tensor is obtained. These results imply that a result of Erdős (Magyar Tud Akad Mat Kutató Int Közl 7:459–464, 1962) under certain conditions. [ABSTRACT FROM AUTHOR]

Let G be a simple graph and A(G) be its adjacency matrix. We say that the graph G satisfies reciprocal eigenvalue property (or simply, property (R)) if 1 λ is an eigenvalue of A(G), whenever λ is an eigenvalue of A(G). The graph G satisfies strong anti-reciprocal property (or simply, property (-SR)) if - 1 λ is an eigenvalue of A(G) with multiplicity k, whenever λ is an eigenvalue of A(G) with multiplicity k. Recently, Barik, Mondal and Pati proved that there exists no singular (non-trivial) tree whose nonzero eigenvalues satisfy reciprocal eigenvalue property. As a concluding remark, the authors mentioned that "It is interesting to see that our result (for trees) is true for any connected graph". In this paper, we prove that there exists no singular unicyclic graph whose nonzero eigenvalues satisfy reciprocal eigenvalue property. Ahmad, Hameed and Jabeen in their recent paper raised the question about existence of noncorona graphs with property (-SR) and constructed seven classes of graphs satisfying this property. Here, we give several families of noncorona graphs with property (-SR). [ABSTRACT FROM AUTHOR]

The eccentricity matrix of a graph is obtained from the distance matrix by keeping the entries that are largest in their row or column, and replacing the remaining entries by zero. This matrix can be interpreted as an opposite to the adjacency matrix, which is on the contrary obtained from the distance matrix by keeping only the entries equal to 1. In the paper, we determine graphs having the second largest eigenvalue of eccentricity matrix less than 1. [ABSTRACT FROM AUTHOR]

The graph a K m , m ∇ C n is named the generalized double-wheel graph. A graph G is said to be M-integral (resp. A-integral, D-integral, D L -integral or D Q -integral) if all eigenvalues of its matrix M (resp. adjacency matrix A(G) , distance matrix D(G) , distance Laplacian matrix D L (G) or distance signless Laplacian matrix D Q (G) ) are integers. In this paper, we completely determine all D-integral, D L -integral and D Q -integral generalized double-wheel graphs respectively. [ABSTRACT FROM AUTHOR]

Let G S be the graph obtained by attaching a self-loop at every vertex in S ⊆ V (G) of a simple graph G of order n. In this paper, we explore several new results related to the line graph L (G S) of G S. Particularly, we show that every eigenvalue of L (G S) must be at least - 2 , and relate the characteristic polynomial of the line graph L(G) of G with the characteristic polynomial of the line graph L (G ^) of a self-loop graph G ^ , which is obtained by attaching a self-loop at each vertex of G. Then, we provide some new bounds for the eigenvalues and energy of G S. As one of the consequences, we obtain that the energy of a connected regular complete multipartite graph is not greater than the energy of the corresponding self-loop graph. Lastly, we establish a lower bound of the spectral radius in terms of the first Zagreb index M 1 (G) and the minimum degree δ (G) , as well as proving two Nordhaus–Gaddum-type bounds for the spectral radius and the energy of G S , respectively. [ABSTRACT FROM AUTHOR]

Denote by G n , ν ∗ (G n , ν ∗ ∗) the collection of all (connected) graphs of order n having a fractional matching number ν ∗ . This paper characterizes the graphs in G n , ν ∗ and G n , ν ∗ ∗ with the maximum spectral radius, and establishes a lower bound for the spectral radius of graphs of order n to guarantee that their fractional matching numbers are at least τ + 1 2 . In addition, we explore the relationship between the spectral radius, perfect matching and fractional perfect matching of G. Moreover, we present a spectral condition guaranteeing that the matching number of a graph is at least k + 1 , which generalizes some previous known results. [ABSTRACT FROM AUTHOR]

In this paper, the unique graph with the minimal second smallest normalized Laplacian eigenvalue of unicyclic graphs with fixed girth is determined. [ABSTRACT FROM AUTHOR]

Let G be a connected graph of order n, where n is a positive integer. A spanning subgraph F of G is called a path-factor if every component of F is a path of order at least 2. A P ≥ k -factor means a path-factor in which every component admits order at least k ( k ≥ 2 ). The distance matrix D (G) of G is an n × n real symmetric matrix whose (i, j)-entry is the distance between the vertices v i and v j . The distance signless Laplacian matrix Q (G) of G is defined by Q (G) = T r (G) + D (G) , where Tr(G) is the diagonal matrix of the vertex transmissions in G. The largest eigenvalue η 1 (G) of Q (G) is called the distance signless Laplacian spectral radius of G. In this paper, we aim to present a distance signless Laplacian spectral radius condition to guarantee the existence of a P ≥ 2 -factor in a graph and claim that the following statements are true: (i) G admits a P ≥ 2 -factor for n ≥ 4 and n ≠ 7 if η 1 (G) < θ (n) , where θ (n) is the largest root of the equation x 3 - (5 n - 3) x 2 + (8 n 2 - 23 n + 48) x - 4 n 3 + 22 n 2 - 74 n + 80 = 0 ; (ii) G admits a P ≥ 2 -factor for n = 7 if η 1 (G) < 25 + 161 2 . [ABSTRACT FROM AUTHOR]

In this paper, we investigate the spectrum of a class of weighted Laplacians on Cayley graphs and determine under what conditions the corresponding eigenspaces are generically irreducible. Specifically, we analyze the spectrum on left-invariant Cayley graphs endowed with an invariant metric, and we give some criteria for generically irreducible eigenspaces. Additionally, we introduce an operator that is comparable to the Laplacian and show that the same criterion holds. [ABSTRACT FROM AUTHOR]

Some of the quantum searching models have been given by perturbed quantum walks. Driving some perturbed quantum walks, we may quickly find one of the targets with high probability. In this paper, we address a discrete-time quantum walk. We construct a quantum searching model finding one of the edges of a given subgraph in a complete graph. How to construct our model is that we label the arcs by + 1 or - 1 , and define a perturbed quantum walk by the sign function on the set of arcs. After that, we detect one of the edges labeled - 1 by the induced sign function as fast as possible. This idea was firstly proposed by Segawa (Quantum Inf Process 20:182, 2021). They only addressed the case where the subgraph forms a matching, and obtained by a combinatorial argument that the time of finding one of the edges of the subgraph is quadratically faster than a classical searching model. In this paper, we show that the model is valid for any subgraph, i.e., we obtain by spectral analysis a quadratic speed-up for finding one of the edges of the subgraph in a complete graph. [ABSTRACT FROM AUTHOR]

Topological indices are widely used in mathematical chemistry to study graphs of molecules of a chemical compound. The comaximal graph of a ring R, denoted by Γ (R) , has elements of R as vertices, and any two distinct vertices x, y of Γ (R) are adjacent if and only if R x + R y = R . In this paper, we find the eigenvalues of the adjacency matrix, and the topological indices of the comaximal graph Γ (Z n) of the ring Z n . We determine the Wiener index, the first and the second Zagreb index, as well as the adjacency and the Laplacian energy of Γ (Z n) . A SAGE code for evaluating the above indices has also been provided at the end of this paper. [ABSTRACT FROM AUTHOR]

In this paper, we obtain some sharp upper and lower bounds for the spectral radii of nonnegative k-uniform tensors (resp., nonnegative tensors) by using the i-th q-times-average slice sum which was introduced by C. Lü, L. H. You and Y. F. Huang [AIMS Math., 2020, 5(3): 1799–1819]. When k = 2, q =1, our results can deduce the main results of D. P. Huang and L. H. You [J. Appl. Math., 2016, 3: 1–7]. We also find that the upper bounds of nonnegative k-uniform tensors we obtained can not be compared with the upper bounds presented by [AIMS Math., 2020, 5(3): 1799–1819] by numerical examples. As applications, we obtain some sharp upper bounds for the α-spectral radii of k-uniform hypergraphs (resp., k-uniform directed hypergraphs). [ABSTRACT FROM AUTHOR]

In this paper, we characterize all connected signed graphs whose the adjacency matrix has at most two eigenvalues (multiplicities included) not equal to ± 1 , among these signed graphs, there are 17 infinite families of signed graphs and 28 individual signed graphs. Furthermore, we study the spectral determination problem for the friendship graphs F k within the scope of signed graphs, which consist of a number of edge-disjoint triangles meeting in one vertex. [ABSTRACT FROM AUTHOR]

In a TAR (token addition/removal) reconfiguration graph, each vertex is a set of vertices, with an edge between two vertices if one can be obtained from the other by adding or removing one element. This paper considers the X-TAR graph of a base graph G where the vertices of the X-TAR graph of G are the X-sets of G, which are subsets of V(G) that satisfy certain conditions. Dominating sets, power dominating sets, zero forcing sets, and positive semidefinite zero forcing sets are all examples of X-sets. For graphs G and G ′ with no isolated vertices, it is shown that G and G ′ have isomorphic X-TAR graphs if and only if there is a relabeling of the vertices of G ′ such that G and the relabeled G ′ have exactly the same X-sets. These results are applied to show certain zero forcing TAR graphs are unique up to isomorphism of the base graph. Furthermore, results related to the connectedness of the zero forcing TAR graph are presented. [ABSTRACT FROM AUTHOR]

Let G be a graph with order n and adjacency matrix A (G) . The adjacency polynomial of G is defined as ϕ (G ; λ) = det (λ I - A (G)) = ∑ i = 0 n a i (G) λ n - i . Here, a i (G) is referred as the i-th adjacency coefficient of G. We use G n , m to denote the set of all connected graphs having n vertices and m edges. A graph G ∈ G n , m is said to be 4-Sachs optimal in G n , m if a 4 (G) = min { a 4 (H) | H ∈ G n , m }. The minimum 4-Sachs number in G n , m is denoted by a 4 ¯ (G n , m) , which is the value of min { a 4 (H) | H ∈ G n , m } . In this paper, we study the relationship between the value of a 4 (G) and the structural properties of G. Specially, we provide a structural characterization of 4-Sachs optimal graphs by showing that each 4-Sachs optimal graph in G n , m contains a connected difference graph as its spanning subgraph. Additionally, for n ≥ 4 and n - 1 ≤ m ≤ 2 n - 4 , we determine all 4-Sachs optimal graphs, along with their corresponding minimum 4-Sachs number a 4 ¯ (G n , m) . [ABSTRACT FROM AUTHOR]

The Grover walk is one of the most well-studied quantum walks on graphs. In this paper, we investigate its periodicity to reveal the relationship between the quantum walk and the underlying graph, focusing particularly on the characterization of graphs exhibiting a periodic Grover walk. Graphs having a periodic Grover walk with periods of 2, 3, 4, and 5 have previously been characterized. It is expected that graphs exhibiting a periodic Grover walk with odd period correspond to cycles with odd length. We address that problem and are able to perfectly characterize the class of graphs exhibiting an odd-periodic Grover walk by using a combinatorial method. [ABSTRACT FROM AUTHOR]

The paper deals with two interrelated topics: (1) identifying transient amplifiers in an iterative process, and (2) analyzing the process by its spectral dynamics, which is the change in the graph spectra by edge manipulation. Transient amplifiers are networks representing population structures which shift the balance between natural selection and random drift. Thus, amplifiers are highly relevant for understanding the relationships between spatial structures and evolutionary dynamics. We study an iterative procedure to identify transient amplifiers for death–Birth updating. The algorithm starts with a regular input graph and iteratively removes edges until desired structures are achieved. Thus, a sequence of candidate graphs is obtained. The edge removals are guided by quantities derived from the sequence of candidate graphs. Moreover, we are interested in the Laplacian spectra of the candidate graphs and analyze the iterative process by its spectral dynamics. The results show that although transient amplifiers for death–Birth updating are generally rare, a substantial number of them can be obtained by the proposed procedure. The graphs identified share structural properties and have some similarity to dumbbell and barbell graphs. We analyze amplification properties of these graphs and also two more families of bell-like graphs and show that further transient amplifiers for death–Birth updating can be found. Finally, it is demonstrated that the spectral dynamics possesses characteristic features useful for deducing links between structural and spectral properties. These feature can also be taken for distinguishing transient amplifiers among evolutionary graphs in general. [ABSTRACT FROM AUTHOR]

A threshold graph G on n vertices is defined by a binary sequence of length n. In this paper, we present an explicit formula for computing the distance characteristic polynomial of a threshold graph from its binary sequence. As an application, we show how to construct infinite pairs of nonisomorphic threshold graphs having the same D -spectrum. This answers a question posed in Lu et al. (Linear Algebra Appl 553:223–237, 2018). [ABSTRACT FROM AUTHOR]

Let G be a graph of order n with adjacency matrix A(G) and diagonal matrix of degree D(G). For every α ∈ [ 0 , 1 ] , Nikiforov (Appl Anal Discrete Math 11(1):81–107, 2017) defined the matrix A α (G) = α D (G) + (1 - α) A (G) . In this paper, we present the A α (G) -characteristic polynomial when G is obtained by coalescing two graphs, and if G is a semi-regular bipartite graph we obtain the A α -characteristic polynomial of the line graph associated with G. Moreover, if G is a regular graph, we exhibit the A α -characteristic polynomial for the graphs obtained from some operations. [ABSTRACT FROM AUTHOR]

Let G be a graph of order n and μ be an adjacency eigenvalue of G with multiplicity k ≥ 1. A star complement H for μ in G is an induced subgraph of G of order n − k with no eigenvalue μ, and the subset X = V(G − H) is called a star set for μ in G. The star complement provides a strong link between graph structure and linear algebra. In this paper, the authors characterize the regular graphs with K2,2,s (s ≥ 2) as a star complement for all possible eigenvalues, the maximal graphs with K2,2,s as a star complement for the eigenvalue μ = 1, and propose some questions for further research. [ABSTRACT FROM AUTHOR]