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