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]

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]