Search

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]

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 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]

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]

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]

The eccentricity matrix of a simple connected graph G is obtained from the distance matrix of G by retaining the largest nonzero distance in each row and column, and the remaining entries are defined to be zero. A bi-block graph is a simple connected graph whose blocks are all complete bipartite graphs with possibly different orders. In this paper, we study the eccentricity matrices of a subclass B (which includes trees) of bi-block graphs. We first find the inertia of the eccentricity matrices of graphs in B , and thereby, we characterize graphs in B with odd diameters. Precisely, if the diameter of G ∈ B is more than three, then we show that the eigenvalues of the eccentricity matrix of G are symmetric with respect to the origin if and only if the diameter of G is odd. Further, we prove that the eccentricity matrices of graphs in B are irreducible. [ABSTRACT FROM AUTHOR]

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]

In this paper we study the problem of prescribing Dirichlet eigenvalues on an arbitrary compact manifold M of dimension n ≥ 3 with a non-empty smooth boundary ∂ M . We show that for any finite increasing sequence of real numbers 0 < a 1 < a 2 ≤ a 3 ≤ ⋯ ≤ a N and any positive number V, there exists a Riemannian metric g on M such that Vol (M , g) = V and λ k D (M , g) = a k for any integer 1 ≤ k ≤ N . [ABSTRACT FROM AUTHOR]

In this paper, we deal with the construction of symmetric matrix whose corresponding graph is connected and unicyclic using some pre-assigned spectral data. Spectral data for the problem consist of the smallest and the largest eigenvalues of each leading principal submatrices. Inverse eigenvalue problem (IEP) with this set of spectral data is generally known as the extremal IEP. We use a standard scheme of labeling the vertices of the graph, which helps in getting a simple relation between the characteristic polynomials of each leading principal submatrix. Sufficient condition for the existence of the solution is obtained. The proof is constructive, hence provides an algorithmic procedure for finding the required matrix. Furthermore, we provide the condition under which the same problem is solvable when two particular entries of the required matrix satisfy a linear relation. [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]

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 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]

A graph G has a P ⩾ k -factor if G has a spanning subgraph H such that every component of H is a path of order at least k. A graph G is P ⩾ k -factor deleted if G - e has a P ⩾ k -factor for each edge e of G. In this paper, we give two necessary and sufficient conditions defining a P ⩾ 2 -factor deleted graph and a P ⩾ 3 -factor deleted graph, respectively. Based on the result of P ⩾ 2 -factor deleted graphs, we establish respectively a lower bound on the size and a lower bound on the spectral radius to ensure whether or not a graph is P ⩾ 2 -factor deleted. Furthermore, by constructing extremal graphs, we show that all the above bounds are best possible. [ABSTRACT FROM AUTHOR]

In this paper we show the existence of the minimal solution to the multidimensional Lambert–Euler inversion, a multidimensional generalization of [ - e - 1 , 0) branch of Lambert W function W 0 (x) . Specifically, for a given nonnegative irreducible symmetric matrix V ∈ R k × k and a vector u ∈ (0 , ∞) k , we show that, if the system of equations y j exp { - e j T V y } = u j ∀ j = 1 , ... , k , has at least one solution, it must have a minimal solution y ∗ , where the minimum is achieved in all coordinates y j simultaneously. Moreover, such y ∗ is the unique solution satisfying ρ V D [ y j ∗ ] ≤ 1 , where D [ y j ∗ ] = diag (y j ∗) is the diagonal matrix with entries y j ∗ and ρ denotes the spectral radius. Our main application is in the analysis of the vector-multiplicative coalescent process. It is a coalescent process with k types of particles and k-dimensional vector-valued cluster weights representing the composition of a cluster by particle types. The clusters merge according to the vector-multiplicative kernel K (x , y) = x T V y . First, we derive some new combinatorial results, and use them to solve the corresponding modified Smoluchowski equations obtained as a hydrodynamic limit of vector-multiplicative coalescent. Then, we use multidimensional Lambert–Euler inversion to establish gelation and find a closed form expression for the gelation time. We also find the asymptotic length of the minimal spanning tree for a broad range of graphs equipped with random edge lengths. [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]

In this paper, we study the signless Laplacian spectral Turán type problem in terms of the size, obtain sharp upper bounds on the signless spectral radius of C 3 ( C 4 )-free graphs with given size and minimum degree δ ≥ 2 , and characterize the corresponding extremal graphs completely. [ABSTRACT FROM AUTHOR]

In general, the properties of binary matroids like graphicness and cographicness are not preserved by the splitting operation. In this paper, for the set of graphic matroids, we obtain a collection of minimal minors to get non-cographic splitting matroids using a splitting operation by a set containing three elements. [ABSTRACT FROM AUTHOR]

Let ℋ be a uniform hypergraph. In this paper, we obtain several bounds for the spectral radius of ℋ in terms of the parameters such as q-average-degrees, diameter, and characterize the corresponding extremal hypergraphs. Moreover, we discuss the change for the spectral radius of a uniform hypergraph after deleting a vertex, and give a comparison of our results with some known ones. [ABSTRACT FROM AUTHOR]

A signed graph Γ is the graph whose edges get signs ± 1 . The index of Γ is the largest eigenvalue of its adjacency matrix. For a family F of signed graphs, a signed graph Γ is said to be F -free if Γ contains no member in F as its subgraph. The family consisting of all F -free graphs on n vertices is denoted by G (n , F) . If F = { F } , we simply write F as F. Let K n + and C n + be the complete graph of order n and cycle of order n whose edges get signs + 1 , respectively. In this paper, we, respectively, characterize the extremal graphs possessing the maximum index among G (n , K s +) with s ≥ 2 , G (n , C) with C = { C l + : 3 ≤ l ≤ n } and G (n , C 2 k) with C 2 k = { C 2 k + : 2 ≤ k ≤ ⌊ n 2 ⌋ } . [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]

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]

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]

For an n-vertex graph G, a fractional matching of G is a function f giving each edge a real number in [0, 1] such that ∑ e ∈ Γ (v) f (e) ≤ 1 for each vertex v ∈ V (G) , where Γ (v) is the set of edges incident to v. A fractional perfect matching is a fractional matching f with ∑ e ∈ E (G) f (e) = n 2 . In this paper, we establish tight lower bounds on the size and the spectral radius of G to guarantee that G has a fractional perfect matching, respectively. In addition, we investigate the relationship between fractional perfect matching and P ⩾ 2 -factor, and give some sufficient conditions for a graph to have a P ⩾ 2 -factor. [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]

The study of the relationships between the eigenvalues of a graph and its structural parameters is a central topic in spectral graph theory. In this paper, we give some new spectral conditions for the connectivity, toughness and perfect k-matchings of regular graphs. Our results extend or improve the previous related ones. [ABSTRACT FROM AUTHOR]

Let G S be a graph with loops obtained from a graph G of order n and loops at S ⊆ V (G). In this paper, we establish a neccesary and sufficient condition on the bipartititeness of a connected graph G and the spectrum Spec (G S) and Spec (G V (G) \ S) . We also prove that for every S ⊆ V (G) , E (G S) ≥ E (G) when G is bipartite. Moreover, we provide an identification of the spectrum of complete graphs K n and complete bipartite graphs K m , n with loops. We characterize any graphs with loops of order n whose eigenvalues are all positive or non-negative, and also any graphs with a few distinct eigenvalues. Finally, we provide some bounds related to G S . [ABSTRACT FROM AUTHOR]

For an n-vertex graph G, a fractional matching of G is a function f giving each edge a real number in [0, 1] such that ∑ e ∈ Γ (v) f (e) ≤ 1 for each vertex v ∈ V (G) , where Γ (v) is the set of edges incident to v. A fractional perfect matching is a fractional matching f with ∑ e ∈ E (G) f (e) = n 2 . In this paper, we establish tight lower bounds on the size and the spectral radius of G to guarantee that G has a fractional perfect matching, respectively. In addition, we investigate the relationship between fractional perfect matching and P ⩾ 2 -factor, and give some sufficient conditions for a graph to have a P ⩾ 2 -factor. [ABSTRACT FROM AUTHOR]

In 2001, Davies, Gladwell, Leydold, and Stadler proved discrete nodal domain theorems for eigenfunctions of generalized Laplacians, i.e., symmetric matrices with non-positive off-diagonal entries. In this paper, we establish nodal domain theorems for arbitrary symmetric matrices by exploring the induced signed graph structure. Our concepts of nodal domains for any function on a signed graph are switching invariant. When the induced signed graph is balanced, our definitions and upper bound estimates reduce to existing results for generalized Laplacians. Our approach provides a more conceptual understanding of Fiedler's results on eigenfunctions of acyclic matrices. This new viewpoint leads to lower bound estimates for the number of strong nodal domains which improves previous results of Berkolaiko and Xu–Yau. We also prove a new type of lower bound estimates by a duality argument. [ABSTRACT FROM AUTHOR]

For a finite group G, the power graph P (G) is a simple connected graph whose vertex set is the set of elements of G and two distinct vertices x and y are adjacent if and only if xi = y or yj = x, for 2 ≤ i, j ≤ n. In this paper, we obtain the distance Laplacian spectrum of power graphs of finite groups such as cyclic groups, dihedral groups, dicyclic groups, abelian groups and elementary abelian p groups. Moreover, we find the largest and second smallest distance Laplacian eigenvalue of power graphs of such groups. [ABSTRACT FROM AUTHOR]

Let G be a finite abelian group viewed a Z -module and let G = (V , E) be a simple graph. In this paper, we consider a graph Γ (G) called as a group-annihilator graph. The vertices of Γ (G) are all elements of G and two distinct vertices x and y are adjacent in Γ (G) if and only if [ x : G ] [ y : G ] G = { 0 } , where x , y ∈ G and [ x : G ] = { r ∈ Z : r G ⊆ Z x } is an ideal of a ring Z . We discuss in detail the graph structure realised by a group G. Moreover, we study the creation sequence, hyperenergeticity and hypoenergeticity of group-annihilator graphs. Finally, we conclude the paper with a discussion on Laplacian eigen values of the group-annihilator graph. We show that the Laplacian eigen values are representatives of orbits of the group action: A u t (Γ (G)) × G → G . [ABSTRACT FROM AUTHOR]

Given a family F of graphs, a graph G is called F -free if G contains none of F as its subgraph. The following problem is one of the most concerned problems in spectral extremal graph theory: what is the maximum spectral radius of an n-vertex F -free graph? If each connected component of a graph is either a path (star) or an isolated vertex, then we call it a linear (star) forest. Denote by L n , k and S n , k the family of all n-vertex linear forests and star forests with k edges, respectively. In this paper, we obtain the maximum spectral radius of an n-vertex L n , k -free graph and characterize the extremal graphs based on Kelmans transformation. Also, we obtain the maximum spectral radius of an n-vertex S n , k -free graph and characterize the unique extremal graph. [ABSTRACT FROM AUTHOR]

Modeling complex systems that consist of different types of objects leads to multilayer networks, where nodes in the different layers represent different kinds of objects. Nodes are connected by edges, which have positive weights. A multilayer network is associated with a supra-adjacency matrix. This paper investigates the sensitivity of the communicability in a multilayer network to perturbations of the network by studying the sensitivity of the Perron root of the supra-adjacency matrix. Our analysis sheds light on which edge weights to make larger to increase the communicability of the network, and which edge weights can be made smaller or set to zero without affecting the communicability significantly. [ABSTRACT FROM AUTHOR]

The Wiener-type invariants of a connected graph G are defined as W f = ∑ u , v ∈ V (G) f (d G (u , v)) , where f(x) is a nonnegative function on the distance d G (u , v). 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 best possible Wiener-type invariants conditions to guarantee a graph to be k-leaf-connected, which extend the corresponding results on Hamilton-connected graphs. As applications, sufficient conditions for a graph to be k-leaf-connected in terms of the distance (distance signless Laplacian, Harary) spectral radius of G or its complement are also obtained. [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 S n be the symmetric group on [ n ] = { 1 , 2 , ⋯ , n } and C n (r) be the set of all r-cycles in S n that do not fix 1, i.e., C n (r) = { α ∈ S n ∣ α (1) ≠ 1 and α is an r - cycle } . In this paper, we give a reduction formula of the eigenvalues of the Cayley graph Γ (S n , C n (r)) . Then we apply it to determine all the eigenvalues of the Cayley graph Γ (S n , C n (r)) for r = 3 , n - 1 and n. [ABSTRACT FROM AUTHOR]

Using the eigenvalues of a graph to reflect its structural properties is a central topic in spectral graph theory. Especially, the relationships between the eigenvalues of a graph and its structural parameters have been studied extensively. In this paper, we explore the relationships between the (normalized) Laplacian eigenvalues of a graph and its ℓ -connectivity, integrity, tenacity and toughness. Some of our results extend or improve the related existing results. [ABSTRACT FROM AUTHOR]

The celebrated Motzkin–Straus formulation for the maximum clique problem provides a nontrivial characterization of the clique number of a graph in terms of the maximum value of a nonconvex quadratic function over a standard simplex. It was originally developed as a way of proving Turán's theorem in graph theory, but was later used to develop competitive algorithms for the maximum clique problem based on continuous optimization. Clique relaxations, such as s-defective clique and s-plex, emerged as attractive, more practical alternatives to cliques in network-based cluster detection models arising in numerous applications. This paper establishes continuous cubic formulations for the maximum s-defective clique problem and the maximum s-plex problem by generalizing the Motzkin–Straus formulation to the corresponding clique relaxations. The formulations are used to extend Turán's theorem and other known lower bounds on the clique number to the considered clique relaxations. Results of preliminary numerical experiments with the CONOPT solver demonstrate that the proposed formulations can be used to quickly compute high-quality solutions for the maximum s-defective clique problem and the maximum s-plex problem. The proposed formulations can also be used to generate interesting test instances for global optimization solvers. [ABSTRACT FROM AUTHOR]

Let (G , σ) be a signed graph, where G is the underlying simple graph and σ : E (G) ⟶ { - , + } is the sign function on the edges of G. Let (K n , H -) be a signed complete graph whose negative edges induce a subgraph H. In this paper, we show that if (K n , H -) has exactly m non-negative eigenvalues (including their multiplicities), then H has at most m - 1 connected components. In particular, if H is a non-spanning subgraph of K n with m - 1 connected components, then each connected component of H is a complete bipartite graph. Next, we characterize all signed graphs (K n , σ) with exactly one or two non-negative eigenvalues. Let H be a non-spanning subgraph of K n . Then, we characterize (K n , H -) with exactly three non-negative eigenvalues, where H is not connected or H is a tree. Also, it is shown that if H is a connected non-spanning subgraph of K n and H has exactly two negative eigenvalues, then (K n , H -) has exactly three non-negative eigenvalues. [ABSTRACT FROM AUTHOR]

Let q(G) denote the signless Laplacian spectral radius of a graph G. In this paper, we first give an upper bound on q(G) of a connected graph G with fixed size m ≥ 3 k (k ∈ Z +) and maximum degree Δ ≤ m - k . For two connected graphs G 1 and G 2 with size m ≥ 4 , employing this upper bound, we prove that q (G 1) > q (G 2) if Δ (G 1) > Δ (G 2) and Δ (G 1) ≥ 2 m 3 + 1 . As an application, we determine the first ⌊ d / 2 ⌋ graphs with the largest signless Laplacian spectral radius among all graphs with fixed size and diameter. [ABSTRACT FROM AUTHOR]

Let P k be the path of order k. The square P k 2 of P k is obtained by joining all pairs of vertices with distance no more than two in P k . A graph is called H-free if it does not contain H as a subgraph. In this paper, we consider a Brualdi-Solheid-Turán type problem for P 5 2 -free graphs, and determine the maximum spectral radius among P 5 2 -free graphs of order n. [ABSTRACT FROM AUTHOR]