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]

The walk matrix of an n-vertex graph G with adjacency matrix A, denoted by $ W(G) $ W (G) , is $ [e,Ae,\ldots,A^{n-1}e] $ [ e , Ae , ... , A n − 1 e ] , where e is the all-ones vector. Let $ G\circ P_m $ G ∘ P m be the rooted product of G and a rooted path $ P_m $ P m (taking an endvertex as the root), i.e. $ G\circ P_m $ G ∘ P m is a graph obtained from G and n copies of $ P_m $ P m by identifying each vertex of G with an endvertex of a copy of $ P_m $ P m . Mao et al. [A new method for constructing graphs determined by their generalized spectrum. Linear Algebra Appl. 2015;477:112–127.] and Mao and Wang [Generalized spectral characterization of rooted product graphs. Linear Multilinear Algebra. 2022. DOI:10.1080/03081087.2022.2098226.] proved that, for m = 2 and $ m\in \{3,4\} $ m ∈ { 3 , 4 } , respectively \[ \det W(G\circ P_m)=\pm a_0^{\lfloor\frac{m}{2}\rfloor}(\det W(G))^m, \] det W (G ∘ P m) = ± a 0 ⌊ m 2 ⌋ (det W (G)) m , where $ a_0 $ a 0 is the constant term of the characteristic polynomial of G. Furthermore, in the same paper, Mao and Wang conjectured that the formula holds for any $ m\ge 2 $ m ≥ 2. In this paper, we verify this conjecture using the technique of Chebyshev polynomials. [ABSTRACT FROM AUTHOR]

In this paper, we introduce the subset-strong product of graphs and give a method for calculating the adjacency spectrum of this product. In addition, exact expressions for the first and second Zagreb indices of the subset-strong products of two graphs are reported. Examples are provided to illustrate the applications of this product in some growing graphs and complex networks. [ABSTRACT FROM AUTHOR]

Let 푅 be a commutative ring with identity 1 ≠ 0 and let Z ⁢ (R) ′ be the set of all non-zero and non-unit elements of ring 푅. Further, Γ ′ ⁢ (R) denotes the cozero-divisor graph of 푅, is an undirected graph with vertex set Z ⁢ (R) ′ , and w ∉ z ⁢ R and z ∉ w ⁢ R if and only if two distinct vertices 푤 and 푧 are adjacent, where q ⁢ R is the ideal generated by the element 푞 in 푅. In this paper, we find the signless Laplacian eigenvalues of the graphs Γ ′ ⁢ (Z n) for n = p 1 N ⁢ p 2 ⁢ p 3 and p 1 N ⁢ p 2 M ⁢ p 3 , where p 1 , p 2 , p 3 are distinct primes and N , M are positive integers. We also show that the cozero-divisor graph Γ ′ ⁢ (Z p 1 ⁢ p 2 ) is a signless Laplacian integral. [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]

Let $ \mathcal {G}_R $ G R denote a unitary one-matching bi-Cayley graph over a finite commutative ring R. In this paper, we give a necessary and sufficient condition for $ \mathcal {G}_R $ G R (respectively, the complement of $ \mathcal {G}_R $ G R and the line graph of $ \mathcal {G}_R $ G R ) to be Ramanujan. [ABSTRACT FROM AUTHOR]

A 2-edge-connected graph G is minimally 2-edge-connected if deleting arbitrary edge of G always leaves a graph which is not 2-edge-connected. In this paper, we completely characterize the (minimally) 2-edge-connected graphs with given size having the maximal signless Laplacian (Laplacian) index. [ABSTRACT FROM AUTHOR]

Complementarity spectrum of a connected graph G, denoted by $ \Pi (G) $ Π (G) , is the set of spectral radii of all connected induced subgraphs of G. Further, G is said to be spectrally non-redundant if $ c(G) $ c (G) , the cardinality of $ \Pi (G) $ Π (G) , is equal to $ b(G) $ b (G) , the number of all non-isomorphic induced subgraphs of G. In this paper, we give a sufficient condition for a family of graphs to be spectrally non-redundant. Using this criterion, we show that several infinite families of graphs are spectrally non-redundant. Moreover, we apply the same condition to distinguish graphs by their spectral radius, which illustrates the main reason for associating a graph with its complementarity spectrum. [ABSTRACT FROM AUTHOR]

For a simple graph G on n vertices the Seidel Estrada index of G, denoted by $ SEE(G) $ SEE (G) , is defined as $ SEE(G)=\sum _{i=1}^ne^{\theta _i} $ SEE (G) = ∑ i = 1 n e θ i , where $ \theta _1,\ldots,\theta _n $ θ 1 , ... , θ n are the Seidel eigenvalues (the eigenvalues of the Seidel matrix) of G. In this paper, we find the maximum and minimum values of the Seidel Estrada index among all graphs with the fixed number of vertices. Our results confirm some conjectures on Seidel Estrada index of graphs that have been posed in [M. Hakimi-Nezhaad, M. Ghorbani, On the Estrada Index of Seidel Matrix, Mathematics Interdisciplinary Research5 (2020) 43–54]. [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]

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 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 G n , β be the set of simple graphs of order n with a given matching number β. In this paper, the graphs maximizing the largest signless p-Laplacian eigenvalue among G n , β are obtained. [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 consider the friendship paradox in the context of random walks and paths. Among our results, we give an equality connecting long-range degree correlation, degree variability, and the degree-wise effect of additional steps for a random walk on a graph. Random paths are also considered, as well as applications to acquaintance sampling in the context of core-periphery structure. [ABSTRACT FROM AUTHOR]

The weight of a partition is the sum of its nonzero coordinates. Let R and S be partitions of the same weight and $ {\mathcal {A}}(R,S) $ A (R , S) be the class of all $ (0,1) $ (0 , 1) -matrices with row sums R and column sums S. For a positive integer t, the t-term rank of a matrix $ A\in {\mathcal {A}}(R,S) $ A ∈ A (R , S) , denoted $ \rho _t(A) $ ρ t (A) , is defined as the largest number of 1's in A with at most one 1 in each column and at most t 1's in each row. The term rank partition of A is the partition $$\begin{align*} term\ \rho(A) & :=(\rho_1(A)-\rho_0(A),\rho_2(A) \\ & \quad - \rho_1(A),\ldots ,\rho_t(A)-\rho_{t-1}(A),\ldots), \end{align*} $$ term ρ (A) := (ρ 1 (A) − ρ 0 (A) , ρ 2 (A) − ρ 1 (A) , ... , ρ t (A) − ρ t − 1 (A) , ...) , where $ \rho _0(A)=0 $ ρ 0 (A) = 0. Let θ be a partition of weight equal to the number of nonzero coordinates of S. In this paper, we study conditions for the existence of a matrix $ C\in {\mathcal {A}}(R,S) $ C ∈ A (R , S) with $ term\ \rho (C)=\theta. $ term ρ (C) = θ. [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]

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 Γ be a finite simple graph with adjacency matrix A. Γ is said to be singular if and only if A has an eigenvalue 0. The nullity of Γ, denoted by null $ (\Gamma) $ (Γ) , is the multiplicity of the eigenvalue 0 in the spectrum of Γ. In this paper, we completely determine the singularity of graphs Γ for which the dicylic or semi-dihedral group acts transitively and faithfully on V as a group of automorphisms. Moreover, we give formulas to calculate the nullities for such graphs. [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, 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]

Discrete versions of the Laplace and Dirac operators have been studied in the context of combinatorial models of statistical mechanics and quantum field theory. In this paper, we introduce several variations of the Laplace and Dirac operators on graphs, and we investigate graph-theoretic versions of the Schrödinger and Dirac equations. We provide a combinatorial interpretation for solutions of the equations and we prove gluing identities for the Dirac operator on lattice graphs, as well as for graph Clifford algebras. [ABSTRACT FROM AUTHOR]

Given an arbitrary connected graph G, the n-polygon graph $ \tau _n(G) $ τ n (G) is obtained by adding a path with length n $ (n\geq ~2) $ (n ≥ 2) to each edge of graph G, and the iterated n-polygon graphs $ \tau _n^g(G) $ τ n g (G) ( $ g\geq ~0 $ g ≥ 0) are obtained from the iteration $ \tau _n^g(G)=\tau _n(\tau _n^{g-1}(G)) $ τ n g (G) = τ n (τ n g − 1 (G)) , with the initial condition $ \tau _n^0(G)=G $ τ n 0 (G) = G. In this paper, a method for calculating the eigenvalues of the normalized Laplacian matrix for graph $ \tau _n(G) $ τ n (G) is presented if the eigenvalues of a normalized Laplacian matrix for graph G is first given. The normalized Laplacian spectra for the graph $ \tau _n(G) $ τ n (G) and graphs $ \tau _n^g(G) $ τ n g (G) ( $ g\geq ~0 $ g ≥ 0) can also then be derived. Finally, as applications, we calculate the multiplicative degree-Kirchhoff index, Kemeny's constant, and the number of spanning trees for the graph $ \tau _n(G) $ τ n (G) and graphs $ \tau _n^g(G) $ τ n g (G) by exploring their connections with the normalized Laplacian spectrum, and obtain exact results for these quantities. [ABSTRACT FROM AUTHOR]

The principal ratio of a graph is the ratio of the greatest and least entry of its principal eigenvector. Since the principal ratio compares the extreme values of the principal eigenvector it is sensitive to outliers. This can be problematic for graphs (networks) drawn from empirical data. To account for this we consider the dispersion of the principal eigenvector (and degree vector). More precisely, we consider the coefficient of variation of the aforementioned vectors, that is, the ratio of the vector's standard deviation and mean. We show how both of these statistics are bounded above by the same function of the principal ratio. Further, this bound is sharp for regular graphs. The goal of this paper is to show that the coefficient of variation of the principal eigenvector (and degree vector) can converge or diverge to the principal ratio in the limit. In doing so, we find an example of a graph family (the complete split graph) whose principal ratio converges to the golden ratio. We conclude with conjectures concerning extremal graphs of the aforementioned statistics. [ABSTRACT FROM AUTHOR]

Let G be a graph, and let $ A(G) $ A (G) be the adjacency matrix of G. The computation of permanent of $ A(G) $ A (G) is #p-complete. Computing permanent of $ A(G) $ A (G) is of great interest in quantum chemistry, statistical physics, among other disciplines. In this paper, we characterize the ordering of permanents of adjacency matrices of all graphs obtained from regular complete bipartite graph $ K_{p, p} $ K p , p by deleting six edges. As an application, we show that all graphs with a perfect matching obtained from $ K_{p, p} $ K p , p with six edges deleted are determined by their permanental polynomials. [ABSTRACT FROM AUTHOR]