Search

Let G be a complex unit gain graph which is obtained from an undirected graph Γ by assigning a complex unit φ ( v i v j ) to each oriented edge v i v j such that φ ( v i v j ) φ ( v j v i ) = 1 for all edges. The Laplacian matrix of G is defined as L ( G ) = D ( G ) − A ( G ) , where D ( G ) is the degree diagonal matrix of Γ and A ( G ) = ( a i j ) has a i j = φ ( v i v j ) if v i is adjacent to v j and a i j = 0 otherwise. In this paper, we provide a combinatorial description of det ( L ( G ) ) that generalizes that for the determinant of the Laplacian matrix of a signed graph. [ABSTRACT FROM AUTHOR]

Abstract: Let be the smallest number such that the adjacency matrix of any undirected graph with vertices or more has at least nonpositive eigenvalues. We show that is well-defined and prove that the values of for are 1, 3, 6, 10, 16 respectively. In addition, we prove that for all , , in which is the Ramsey number for and , and is the triangular number. This implies new lower bounds for eigenvalues of Laplacian matrices: the largest eigenvalue is bounded from below the largest degree, which generalizes some prior results. [Copyright &y& Elsevier]

Abstract: For many types of graphs, criteria have been discovered that give necessary and sufficient conditions for an integer sequence to be the degree sequence of such a graph. These criteria tend to take the form of a set of inequalities, and in the case of the Erdős–Gallai criterion (for simple undirected graphs) and the Gale–Ryser criterion (for bipartite graphs), it has been shown that the number of inequalities that must be checked can be reduced significantly. We show that similar reductions hold for the corresponding criteria for many other types of graphs, including bipartite -multigraphs, bipartite graphs with structural edges, directed graphs, -multigraphs, and tournaments. We also prove a reduction for imbalance sequences. [Copyright &y& Elsevier]

Abstract: Let be a simple graph of order with triangle(s). Also let be the eigenvalues of the adjacency matrix of graph . X. Yong [X. Yong, On the distribution of eigenvalues of a simple undirected graph, Linear Algebra Appl. 295 (1999) 73–80] conjectured that (i) is complete if and only if and also (ii) is complete if and only if . Here we disprove this conjecture by a counter example. Wang et al. [J.F. Wang, F. Belardo, Q.X. Huang, B. Borovićanin, On the two largest Q-eigenvalues of graphs, Discrete Math. 310 (2010) 2858–2866] conjectured that friendship graph is determined by its adjacency spectrum. Here we prove this conjecture. The eccentricity of a vertex is the maximum distance from it to another vertex and the average eccentricity of a graph is the mean value of eccentricities of all vertices of . Moreover, we mention three conjectures, obtained by the system AutoGraphiX, about the average eccentricity , girth and the spectral radius of graphs (see Aouchiche (2006) [1], available online at http://www.gerad.ca/~agx/). We give a proof of one conjecture and disprove two conjectures by counter examples. [Copyright &y& Elsevier]

Abstract: The rank of a graph is that of its adjacency matrix. A graph is called reduced if it has no isolated vertices and no two vertices with the same set of neighbors. We determine the maximum order of reduced trees as well as bipartite graphs with a given rank and characterize those graphs achieving the maximum order. [Copyright &y& Elsevier]

Abstract: The problem of identifying those simple, undirected graphs with vertices and edges that have the smallest minimum eigenvalue of the adjacency matrix is considered. Several general properties of the minimizing graphs are described. These strongly suggest bipartition, to the extent possible for the number of edges. In the bipartite case, the precise structure of the minimizing graphs is given for a number of infinite classes. [Copyright &y& Elsevier]

Abstract: Suppose that is the graph obtained by taking the box product of a path of length and a path of length . Let be the adjacency matrix of . In 1996, Rara showed that, if , then . We extend this result to allow and to be any positive integers, and show that [Copyright &y& Elsevier]

Abstract: We consider simple graphs and their adjacency matrices. In , Rara (1996) gives methods of reducing graphs which simplify the procedure of computing the determinant of their adjacency matrices. We continue this subject matter and give a general method of reducing graphs. By the use of this method we define a formula for computing the determinant of any planar grid and in particular settle the problem of their singularity. [Copyright &y& Elsevier]

Abstract: In this paper we consider threshold graphs (also called nested split graphs) and investigate some invariants of these graphs which can be of interest in bounding the largest eigenvalue of some graph spectra. [Copyright &y& Elsevier]

Abstract: In 1977, Ganter and Teirlinck proved that any matrix with nonzero elements can be partitioned into four submatrices of order of which at most two contain nonzero elements. In 1978, Kramer and Mesner conjectured that any matrix with nonzero elements can be partitioned into submatrices of order of which at most contain nonzero elements. In 1995, Brualdi et al. showed that this conjecture is true if , or . They also found a counterexample of this conjecture for , , and . When , Rho showed that this conjecture is true if . When and , we show that this conjecture is true if or . As a result, we show that when , this conjecture is true if also. [Copyright &y& Elsevier]

Abstract: We say that two graphs and with the same vertex set commute if their adjacency matrices commute. In this paper, we find all integers such that the complete bipartite graph is decomposable into commuting perfect matchings or commuting Hamilton cycles. We show that there are at most linearly independent commuting adjacency matrices of size ; and if this bound occurs, then there exists a Hadamard matrix of order . Finally, we determine the centralizers of some families of graphs. [Copyright &y& Elsevier]

Abstract: Let G be a simple graph. Let and denote the largest eigenvalue of the adjacency matrix and the Laplacian matrix of G, respectively. Let denote the largest vertex degree. If G has just one cycle, thenThe equality holds if and only if . AndThe equality holds if and only if , n is even. [Copyright &y& Elsevier]

The eigenvalues of a graph are the eigenvalues of its adjacency matrix. This paper presents some upper and lower bounds on the greatest eigenvalue and a lower bound on the smallest eigenvalue. [Copyright &y& Elsevier]

The early research on regular graphs of the French mathematician Georges Brunel (1856–1900) is discussed. Brunel developed early graph terminology and started the French “applied” approach towards graph theory. [Copyright &y& Elsevier]

We survey some old and some new characterizations of distance-regular graphs, which depend on information retrieved from their adjacency matrix. In particular, it is shown that a regular graph with d+1 distinct eigenvalues is distance-regular if and only if a numeric equality, involving only the spectrum of the graph and the numbers of vertices at distance d from each vertex, is satisfied. [Copyright &y& Elsevier]

Abstract: This note deals with the relationship between the total number of -walks in a graph, and the sum of the -th powers of its vertex degrees. In particular, it is shown that the the number of all -walks is upper bounded by the sum of the -th powers of the degrees. [Copyright &y& Elsevier]