Search

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]

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]

The complex adjacency matrix A C (G) for a multidigraph G is introduced in Barik and Sahoo (AKCE Int J Graphs Comb 17(1):466–479, 2020). We study the rank of multidigraphs corresponding to the complex adjacency matrix and call it A C -rank. It is known that a connected graph G has rank 2 if and only if G is a complete bipartite graph, and has rank 3 if and only if it is a complete tripartite graph (Cheng in Electron J Linear Algebra 16:60–67, 2007). We observe that these results hold as special cases for multidigraphs but are not sufficient. In this article, we characterize all multidigraphs with A C -rank 2 and 3, respectively. [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]

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]

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]

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]

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]