Search

A combinatorial approach is given to compute bases for eigenspaces of zero-divisor graphs of finite Boolean rings. A commutative monoid $ \mathcal {S} $ S of graphs is shown to contain a cyclic submonoid $ \mathcal {U} $ U that determines values of the entries of basis elements, while the members of its complement $ \mathcal {S}\setminus \mathcal {U} $ S ∖ U encode the supports of these elements. Furthermore, every member of $ \mathcal {S}\setminus \mathcal {U} $ S ∖ U is associated with a Catalan-triangle number, which counts the number of basis elements whose supports are determined by the given member. This is established by using a combinatorial interpretation of Catalan-triangle numbers to produce linearly independent sets of eigenvectors. [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 simple finite graph with vertex set V (Γ) and edge set E (Γ) . Let R be an equivalence relation on V (Γ) . The R -super Γ graph Γ R is a simple graph with vertex set V (Γ) and two distinct vertices are adjacent if either they are in the same R -equivalence class or there are elements in their respective R -equivalence classes that are adjacent in the original graph Γ . We first show that Γ R is a generalized join of some complete graphs and using this we obtain the adjacency and Laplacian spectrum of conjugacy super commuting graphs and order super commuting graphs of dihedral group D 2 n (n ≥ 3) , generalized quaternion group Q 4 m (m ≥ 2) and the nonabelian group Z p ⋊ Z q of order pq, where p and q are distinct primes with q | (p - 1) . [ABSTRACT FROM AUTHOR]

In this article, we study a question of Hong from 1993 related to the minimum spectral radii of the adjacency matrices of connected graphs of given order and size. Hong asked if it is true that among all connected graphs of given number of vertices nn and number of edges ee, the graphs having minimum spectral radius (the minimizer graphs) must be almost regular, meaning that the difference between their maximum degree and their minimum degree is at most one. In this article, we answer Hong’s question positively for various values of nn and ee, and in several cases, we determined the graphs with minimum spectral radius.

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

Let G be a simple graph with the adjacency matrix $ A(G) $ A (G). Let $ \tau (G) $ τ (G) denote the smallest positive eigenvalue of $ A(G) $ A (G). In 1990, Pavlíková and Kr $ \breve{c} $ c ˘ -Jediný proved that among all nonsingular trees on n = 2m vertices, the comb graph (obtained by taking a path on m vertices and adding a new pendant vertex to every vertex of the path) has the maximum τ value. We consider the problem for unicyclic graphs. Let $ \mathscr {U} $ U denote the class of all connected bipartite unicyclic graphs with a unique perfect matching, and for each $ m\geq ~3 $ m ≥ 3 , let $ \mathscr {U}_n $ U n be the subclass of $ \mathscr {U} $ U with graphs on n = 2m vertices. We first obtain the classes of unicyclic graphs U in $ \mathscr {U} $ U such that $ \tau (U)\leq \sqrt {2}-1 $ τ (U) ≤ 2 − 1. We then find the unique graph $ U_o^n $ U o n (resp. $ U_e^n $ U e n ) having the maximum τ value among all graphs in $ \mathscr {U}_n $ U n when m is odd (resp. when m is even). Finally, we prove that $ U_o^6 $ U o 6 (the graph obtained from a cycle of order 4, by adding two pendants to two adjacent vertices) is the graph with maximum τ value among all graphs in $ \mathscr {U} $ U . As a consequence, we obtain a sharp upper bound for $ \tau (U) $ τ (U) when $ U\in \mathscr {U} $ U ∈ U . [ABSTRACT FROM AUTHOR]

Let (G, w) be a weighted graph with the adjacency matrix A. The group inverse of (G, w), denoted by (G # , w #) is the weighted graph with the weight w # (v i v j) of an edge v i v j in G # is defined as the ijth entry of A # , the group inverse of A. We study the group inverse of singular weighted trees. It is shown that if (T, w) is a singular weighted tree, then (T # , w #) is again a weighted tree if and only if (T, w) is a star tree, which in turn holds if and only if (T # , w #) is graph isomorphic to (T, w). A new class T w of weighted trees is introduced and studied here. It is shown that the group inverse of the adjacency matrix of a positively weighted tree in T w is signature similar to a non-negative matrix. [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]

We introduce a graph attached to mutually orthogonal Sudoku Latin squares. The spectra of the graphs obtained from finite fields are explicitly determined. As a corollary, we then use the eigenvalues to distinguish non-isomorphic Sudoku Latin squares. [ABSTRACT FROM AUTHOR]

In this paper, we study the prime order Cayley graph assigned to the group ℤn for different values of n. We specify some of the graph theoretical properties such as chromatic and perfect matching numbers. Furthermore, we determine the adjacency matrices and eigenvalues of the prime order Cayley graph associated with groups ℤn and 𝒟2n.

We consider particular weighted directed graphs with edges having colour red, blue or green such that each red edge has weight 1, each blue edge has weight $ -1 $ − 1 and each green edge has weight $ \mathrm {i} $ i (the imaginary unit). Such a directed graph is called a 3-coloured digraph (for short, a 3-CD). Every mixed graph and every signed graph can be interpreted as a 3-CD. We first study some structural properties of 3-CDs by means of the eigenvalues of the adjacency matrix. In particular, we give spectral criteria for singularity of such digraphs. Second, we consider weight-symmetric 3-CDs, i.e. those 3-CDs that are switching isomorphic to their negation. It follows that the class of weight-symmetric 3-CDs is included in the class of 3-CDs whose spectrum is symmetric (with respect to the origin). We give some basic properties and several constructions of weight-symmetric 3-CDs and establish constructions of 3-CDs which have symmetric spectrum but are not weight-symmetric. [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 a simple graph G, the ABC-index is a degree based topological index and is defined as where dv is the degree of the vertex υ in G. Recently, the Laplacian ABC-matrix was introduced in [22] is defined by where is the diagonal matrix of ABC-degrees and Ã(G) is the ABC-matrix of G: The eigenvalues of the matrix are called the Laplacian ABC-eigenvalues of G. In the article, we consider the problem of characterization of connected graphs having exactly three distinct Laplacian ABC-eigenvalues. We solve this problem for bipartite graphs, multipartite graphs, unicyclic graphs, regular graphs and prove the non-existence of such graphs with diameter greater than 2. We introduce the concept of trace norm of the matrix called the Laplacian ABC-energy of G. We obtain some upper and lower bounds for the Laplacian ABC-energy and characterize the extremal graphs which attain these bounds. [ABSTRACT FROM AUTHOR]

For a group G, the generating graph Γ (G) is defined as the graph with the vertex set G, and any two distinct vertices of Γ (G) are adjacent if they generate G. In this paper, we study the generating graph of D n , where D n is a Dihedral group of order 2n. We explore various graph theoretic properties, and determine complete spectrum of the adjacency and the Laplacian matrix of Γ (D n) . Moreover, we compute some distance and degree based topological indices of Γ (D n) . [ABSTRACT FROM AUTHOR]

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

We formalize the notion of a sedentary vertex and present a relaxation of the concept of a sedentary family of graphs introduced by Godsil (Linear Algebra Appl 614:356–375, 2021. https://doi.org/10.1016/j.laa.2020.08.027). We provide sufficient conditions for a given vertex in a graph to exhibit sedentariness. We also show that a vertex with at least two twins (vertices that share the same neighbours) is sedentary. We prove that there are infinitely many graphs containing strongly cospectral vertices that are sedentary, which reveals that, even though strong cospectrality is a necessary condition for pretty good state transfer, there are strongly cospectral vertices which resist high probability state transfer to other vertices. Moreover, we derive results about sedentariness in products of graphs which allow us to construct new sedentary families, such as Cartesian powers of complete graphs and stars. [ABSTRACT FROM AUTHOR]

Let G n , β be the set of graphs of order n with given matching number β. Let D (G) be the diagonal matrix of the degrees of the graph G and A (G) be the adjacency matrix of the graph G. The largest eigenvalue of the nonnegative matrix A α (G) = α D (G) + A (G) is called the α-spectral radius of G. The graphs with maximal α-spectral radius in G n , β are completely characterized in this paper. In this way, we provide a general framework to attack the problem of extremal spectral radius in G n , β . More precisely, we generalize the known results on the maximal adjacency spectral radius in G n , β and the signless Laplacian spectral radius. [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]

Let R be a commutative ring with all non-zero zero divisors Z ∗ (R) of R . Then Γ (R) is said to be a zero divisor graph if and only if a · b = 0 where a , b ∈ V (Γ (R)) = Z ∗ (R) and (a , b) ∈ E (Γ (R)) . Graph energy E (Γ (R)) is defined as the sum of the absolute eigenvalues of the adjacency matrix of Γ (R) , then E (Γ (R)) = ∑ i = 1 n | λ i | . A topological index is a numeric quantity associated with a chemical structure that attempts to link the chemical structure to various physicochemical properties, chemical reactivity, or biological activity. This paper discusses the graph energy and various topological indices of zero divisor graph associated with the commutative ring. [ABSTRACT FROM AUTHOR]

For a simple graph with vertex set {v1,v2,…,vn}\left\{{v}_{1},{v}_{2},\ldots ,{v}_{n}\right\} and degree sequence dvii=1,2,…,n{d}_{{v}_{i}}\hspace{0.33em}i=1,2,\ldots ,n, the inverse sum indeg matrix (ISI matrix) AISI(G)=(aij){A}_{{\rm{ISI}}}\left(G)=\left({a}_{ij}) of GG is a square matrix of order n,n, where aij=dvidvjdvi+dvj,{a}_{ij}=\frac{{d}_{{v}_{i}}{d}_{{v}_{j}}}{{d}_{{v}_{i}}+{d}_{{v}_{j}}}, if vi{v}_{i} is adjacent to vj{v}_{j} and 0, otherwise. The multiset of eigenvalues τ1≥τ2≥⋯≥τn{\tau }_{1}\ge {\tau }_{2}\hspace{0.33em}\ge \cdots \ge {\tau }_{n} of AISI(G){A}_{{\rm{ISI}}}\left(G) is known as the ISI spectrum of GG. The ISI energy of GG is the sum ∑i=1n∣τi∣\mathop{\sum }\limits_{i=1}^{n}| {\tau }_{i}| of the absolute ISI eigenvalues of G.G. In this article, we give some properties of the ISI eigenvalues of graphs. Also, we obtain the bounds of the ISI eigenvalues and characterize the extremal graphs. Furthermore, we construct pairs of ISI equienergetic graphs for each n≥9n\ge 9.

We consider signed graphs with just 2 or 3 distinct eigenvalues, in particular (i) those with at least one simple eigenvalue, and (ii) those with vertex-deleted subgraphs which themselves have at most 3 distinct eigenvalues. We also construct new examples using weighing matrices and symmetric 3-class association schemes.

The class of unicyclic non-bipartite graphs with unique perfect matching, denoted by U , is considered in this article. This article provides a complete characterization of unicyclic graphs in U which possess tricyclic inverses. [ABSTRACT FROM AUTHOR]

In this article, we undertake the problem of finding the first four trees on a fixed number of vertices with the maximum smallest positive eigenvalue. Let T n , d denote the class of trees on n vertices with diameter d. First, we obtain the bounds on the smallest positive eigenvalue of trees in T n , d for d = 2 , 3 , 4 and then upper bounds on the smallest positive eigenvalue of trees are obtained in general class of all trees on n vertices. Finally, the first four trees on n vertices with the maximum, second maximum, third maximum and fourth maximum smallest positive eigenvalue are characterized. [ABSTRACT FROM AUTHOR]

Let G be a connected d-regular graph and λ 2 (G) be the second largest eigenvalue of its adjacency matrix. Mohar and O (private communication) asked a challenging problem: what is the best upper bound for λ 2 (G) which guarantees that κ (G) ≥ t + 1 , where 1 ≤ t ≤ d - 1 and κ (G) is the vertex-connectivity of G, which was also mentioned by Cioabă. As a starting point, we determine a sharp bound for λ 2 (G) to guarantee κ (G) ≥ 2 (i.e., the case that t = 1 in this problem), and characterize all families of extremal graphs. [ABSTRACT FROM AUTHOR]

It was shown in 2006 that among the nonsingular trees T (whose adjacency matrix A(T) is nonsingular), the corona trees (trees that are obtained by taking any tree T and then adding a new pendant vertex at each vertex of T) are the only ones which satisfy the reciprocal eigenvalue property (λ is an eigenvalue of A(T) if and only if 1 λ is an eigenvalue of A(T), where their multiplicities are allowed to be different). A general question remained open. Can there be a tree which has at least one zero eigenvalue and whose nonzero eigenvalues satisfy the reciprocal eigenvalue property? In this note, we show that there are no such trees with at least two vertices. The proof is a beautiful application of the product of graphs. [ABSTRACT FROM AUTHOR]

The energy of a graph is defined as the sum of the absolute values of all eigenvalues with respect to its adjacency matrix. Denote by Gn,m the set of all connected graphs having n vertices and m edges. Caporossi et al. [Caporossi G, Cvetkovi D, Gutman I, et al. Variable neighbourhood search for extremal graphs. 2. Finding graphs with external energy. J Chem Inf Comput Sci. 1999;39:984–996] conjectured that among all graphs in Gn,m, n ≥ 6 and n − 1 ≤ m ≤ 2(n − 2), the graphs with minimum energy are the star Sn with m−n + 1 additional edges all connected to the same vertices for m ≤ n + ⌊ (n − 7) / 2 ⌋ , and the bipartite graph with two vertices on one side, one of which is connected to all vertices on the other side, otherwise. In this paper, we provide a new approach to investigate the conjecture above. Especially, we determine the unique tetracyclic graph having minimum energy. [ABSTRACT FROM AUTHOR]

This article provides a combinatorial description of the inverse of the adjacency matrix of a non-singular 3-coloured digraph. The class of unicyclic 3-coloured digraphs with the cycle weight ±i and with a unique perfect matching, denoted by U g , is considered in this article. We characterize the 3-coloured digraphs in U g whose inverses are again 3-coloured digraphs. Furthermore, the 3-coloured digraphs in U g whose inverses are bipartite are also characterized. It is proved that the inverses of the 3-coloured digraphs in U g are always Laplacian non-singular. Characterizations of unicyclic 3-coloured digraphs in U g possessing unicyclic inverses are also supplied in this article. As an application, we can obtain the class of unicyclic 3-coloured digraphs with the cycle weight ±i satisfying the strong reciprocal eigenvalue property. [ABSTRACT FROM AUTHOR]

An oriented graph is called singular or nonsingular according as its adjacency matrix is singular or nonsingular. In this note, by a new approach, we determine the singularity of oriented quasi-trees. The main results of Chen et al. ['Singularity of oriented graphs from several classes', Bull. Aust. Math. Soc. 102 (1) (2020), 7–14] follow as corollaries. Furthermore, we give a necessary condition for an oriented bipartite graph to be nonsingular. By applying this condition, we characterise nonsingular oriented bipartite graphs $B_{m,n}$ when $\min \{m,n\}\leq 3$. [ABSTRACT FROM AUTHOR]

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

Let G be an undirected graph with adjacency matrix A (G). For a vertex u ∈ V (G) , the subgraph centrality of u in G is C S (u) = (exp ⁡ (A (G))) u u = ∑ k = 0 ∞ 1 k ! (A (G) k) u u . In this paper, we give some formulas for C S (u) by using equitable partitions and star sets of G. [ABSTRACT FROM AUTHOR]

In [A note about cospectral graphs for the adjacency and normalized Laplacian matrices. Linear Multilinear Algebra. 2010;58(3-4):387–390], Butler constructed a family of bipartite graphs, which are cospectral for both the adjacency and the normalized Laplacian matrices. In this article, we extend this construction for generating larger classes of bipartite graphs, which are cospectral for both the adjacency and the normalized Laplacian matrices. Also, we provide a couple of constructions of non-bipartite graphs, which are cospectral for the adjacency matrices but not necessarily for the normalized Laplacian matrices. [ABSTRACT FROM AUTHOR]

The class of non-bipartite unicyclic graphs with a unique perfect matching, denoted by U , is considered in this article. This article describes the entries of the inverse of the adjacency matrix of a graph in U . It is proved that the inverse graph of a graph in U is always non-bipartite. In this article, we characterize the graphs in U whose inverses are mixed graphs. Among all such graphs in U we identify those graphs whose inverses are quasi-bipartite. Furthermore, characterizations of unicyclic graphs in U possessing unicyclic and bicyclic inverses are also provided in this article. [ABSTRACT FROM AUTHOR]

Let G be a digraph and A (G) be the adjacency matrix of G. Let D (G) be the diagonal matrix with outdegrees of vertices of G. For any real α ∈ [ 0 , 1 ] , define the matrix A α (G) as A α (G) = α D (G) + (1 − α) A (G). The largest modulus of the eigenvalues of A α (G) is called the A α spectral radius of G. In this paper, we determine the digraphs which attain the maximum (or minimum) A α spectral radius among all strongly connected digraphs with given parameters such as girth, clique number, vertex connectivity or arc connectivity. We also propose an open problem. [ABSTRACT FROM AUTHOR]

New proofs of formulae for the inverses of nonsingular adjacency matrices of cycles, and the group inverses of singular adjacency matrices of cycles, are presented. A new columnwise description for the inverse of the adjacency matrix of an even path, and block matrix representations for the group inverse of adjacency matrices of wheels and brooms are also obtained. [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]

Let G be a graph with vertex set { v 1 , v 2 , ... , v n } and let d i denote the degree of vertex v i . The geometric–arithmetic matrix GA (G) of G is indexed by the vertices of G, whose (i, j) -th entry is 2 d i d j d i + d j if the vertices i and j are adjacent and 0 otherwise. The multi-set of eigenvalues of GA (G) is known as the geometric–arithmetic spectrum of G. In this article, we obtain geometric–arithmetic spectra of various families of graphs and characterize the connected graphs with two and three distinct GA eigenvalues. We obtain several upper and lower bounds for the geometric arithmetic energy and characterize the graphs attaining such bounds. [ABSTRACT FROM AUTHOR]

We investigate signed graphs with just 2 or 3 distinct eigenvalues, mostly in the context of vertex-deleted subgraphs, the join of two signed graphs or association schemes. [ABSTRACT FROM AUTHOR]

In this paper, we present a new connection between representation theory of noncommutative hypersurfaces and combinatorics. Let S be a graded ( ± 1 )-skew polynomial algebra in n variables of degree 1 and f = x 1 2 + ⋯ + x n 2 ∈ S . We prove that the stable category CM ̲ Z (S / (f)) of graded maximal Cohen–Macaulay module over S/(f) can be completely computed using the four graphical operations. As a consequence, CM ̲ Z (S / (f)) is equivalent to the derived category D b (mod k 2 r) , and this r is obtained as the nullity of a certain matrix over F 2 . Using the properties of Stanley–Reisner ideals, we also show that the number of irreducible components of the point scheme of S that are isomorphic to P 1 is less than or equal to r + 1 2 . [ABSTRACT FROM AUTHOR]