Search

In [1] , the set of refined inertias H n for sign patterns is expanded to H n ⁎ for zero-nonzero patterns. Also, it is proved that there are no zero-nonzero patterns of even order 2 m that require H 2 m ⁎ . In this paper, it is shown that there are no zero-nonzero patterns of odd order n ≥ 5 that require H n ⁎ , which together with the previous result prove that there are no zero-nonzero patterns of order n ≥ 4 that require H n ⁎ . [ABSTRACT FROM AUTHOR]

Let G be a connected graph with vertex set V ( G ) = { v 1 , v 2 , … , v n } and edge set E ( G ) . The distance Laplacian matrix of G is defined as D L ( G ) = T r ( G ) − D ( G ) , where D ( G ) is the distance matrix and T r ( G ) = diag ( t r v 1 , t r v 2 , … , t r v n ) is the diagonal matrix of vertex transmissions of G . The largest eigenvalue of D L ( G ) is called the distance Laplacian spectral radius of G . In this paper, we obtain a graft transformation of a connected graph, which increases its distance Laplacian spectral radius. Using this transformation, we prove a conjecture involving the distance Laplacian spectral radius. [ABSTRACT FROM AUTHOR]

We prove a result concerning the behavior of the spectral radius of a hypergraph under relocations of edges. We determine the unique hypergraphs with maximum spectral radius among connected k -uniform hypergraphs with fixed number of pendant edges, the unique k -uniform hypertrees with respectively maximum, second maximum and third maximum spectral radius, the unique k -uniform unicyclic hypergraphs ( k -uniform linear unicyclic hypergraphs, respectively) with respectively maximum and second maximum spectral radius. We also determine the unique hypergraphs with maximum spectral radius among k -uniform unicyclic hypergraphs with given girth. [ABSTRACT FROM AUTHOR]

An ( n , m ) -graph is referred to be a graph with n vertices and m edges. Let Δ ( G ) and δ ( G ) be the maximum and minimum degree of a graph G and let μ ( G ) and q ( G ) be the Laplacian and signless Laplacian spectral radius of G , respectively. In this paper, we prove that for two connected nonregular ( n , m ) -graphs G and G ′ , if Δ ( G ) ≥ 2 m − ( n − 1 ) δ ( G ′ ) δ ( G ′ ) + 1 + δ ( G ′ ) and Δ ( G ) > Δ ( G ′ ) + δ ( G ′ ) − 1 , then μ ( G ) > μ ( G ′ ) and q ( G ) > q ( G ′ ) . Also, we obtain that for two connected nonregular ( n , m ) -graphs G and G ′ , if Δ ( G ) ≥ 2 m − ( n − 1 ) δ ( G ′ ) δ ( G ′ ) + 1 + 1 and Δ ( G ) > Δ ( G ′ ) , then μ ( G ) > μ ( G ′ ) − δ ( G ′ ) + 1 and q ( G ) > q ( G ′ ) − δ ( G ′ ) + 1 . [ABSTRACT FROM AUTHOR]

Let C n denote the cycle with n vertices, and let τ ( G ) be the number of triangles of G . If G is a graph with n vertices, then μ 1 ( G ) ≥ μ 2 ( G ) ≥ ⋯ ≥ μ n ( G ) denote the signless Laplacian spectrum of G . Two graphs are said to be Q -cospectral if they have the same signless Laplacian spectrum. A graph G is said to be Q − D S if there is no other non-isomorphic graph H such that G and H are Q -cospectral. In this paper, we prove that “Let G be a graph with n ≥ 12 vertices and 1 ≤ μ n ( G ) ≤ μ 2 ( G ) ≤ 5 < n < μ 1 ( G ) or let G be a graph with n ≥ 10 vertices and 0 < μ n ( G ) ≤ μ 2 ( G ) ≤ 4 < n < μ 1 ( G ) . If G and H are Q -cospectral, then G and H share the same degree sequences and τ ( G ) = τ ( H ) ”. As a consequence of our results, we show that all multi-wheel graphs K 1 ∨ ( C q 1 ∪ C q 2 ∪ ⋯ ∪ C q t ) are Q − D S . [ABSTRACT FROM AUTHOR]

Let G be a simple graph of order n with maximum degree Δ and minimum degree δ . Let ( d ) = ( d 1 , d 2 , … , d n ) and ( d ⁎ ) = ( d 1 ⁎ , d 2 ⁎ , … , d n ⁎ ) be the sequences of degrees and conjugate degrees of G . We define π = ∑ i = 1 n d i and π ⁎ = ∑ i = 1 n d i ⁎ , and prove that π ⁎ ≤ L E L ≤ I E ≤ π where LEL and IE are, respectively, the Laplacian-energy-like invariant and the incidence energy of G . Moreover, we prove that π − π ⁎ > ( δ / 2 ) ( n − Δ ) for a certain class of graphs. Finally, we compare the energy of G and π , and present an upper bound for the Laplacian energy in terms of degree sequence. [ABSTRACT FROM AUTHOR]

In 1962, Erdős proved a theorem on the existence of Hamilton cycles in graphs with given minimum degree and number of edges. Significantly strengthening in case of balanced bipartite graphs, Moon and Moser proved a corresponding theorem in 1963. In this paper we establish several spectral analogues of Moon and Moser's theorem on Hamilton paths in balanced bipartite graphs and nearly balanced bipartite graphs. One main ingredient of our proofs is a structural result of its own interest, involving Hamilton paths in balanced bipartite graphs with given minimum degree and number of edges. [ABSTRACT FROM AUTHOR]

We show that the d -cube is determined by the spectrum of its distance matrix. [ABSTRACT FROM AUTHOR]

Given simple graphs G , H 1 , … , H n , where n = | V ( G ) | , the generalized corona, denoted G ∘ ˜ Λ i = 1 n H i , is the graph obtained by taking one copy of graphs G , H 1 , … , H n and joining the i th vertex of G to every vertex of H i . In this paper, we determine and study the characteristic, Laplacian and signless Laplacian polynomial of G ∘ ˜ Λ i = 1 n H i . This leads us to construct new pairs of cospectral, L -cospectral and Q -cospectral graphs. As an application, we give a simple proof for Csikvari's Lemma on eigenvalues of graphs. [ABSTRACT FROM AUTHOR]

A multigraph is a graph with possible multiple edges, but no loops. The multiplicity of a multigraph is the maximum number of edges between any pair of vertices. We prove that, for a multigraph G with multiplicity m and minimum degree δ ≥ 2 k , if the algebraic connectivity is greater than min ⁡ { 2 k − 1 ⌈ ( δ + 1 ) / m ⌉ , 2 k − 1 2 } , then G has at least k edge-disjoint spanning trees; for a multigraph G with multiplicity m and minimum degree δ ≥ k , if the algebraic connectivity is greater than min ⁡ { 2 ( k − 1 ) ⌈ ( δ + 1 ) / m ⌉ , k − 1 } , then the edge connectivity is at least k . These extend some earlier results. A balloon of a graph G is a maximal 2-edge-connected subgraph that is joined to the rest of G by exactly one cut-edge. We provide spectral conditions for the number of balloons in a multigraph, which also generalizes an earlier result. [ABSTRACT FROM AUTHOR]

In this note, we determined the distance signatures of the incidence matrices of affine resolvable designs. This proves a conjecture by Kohei Yamada. [ABSTRACT FROM AUTHOR]

We confirm a conjecture in Wocjan and Elphick (2013) [4] about a lower bound of the chromatic number of a graph. [ABSTRACT FROM AUTHOR]

An oriented hypergraph is a hypergraph where each vertex-edge incidence is given a label of +1 or −1, and each adjacency is signed the negative of the product of the incidences. An oriented hypergraph is balanced if the product of the adjacencies in each circle is positive. We provide a combinatorial interpretation for entries of k th power of the oriented hypergraphic Laplacian via the number of signed weak walks of length k . Using closed weak walks we prove a new characterization of balance for oriented hypergraphs and matrices that generalizes Harary's Theorem for signed graphs. [ABSTRACT FROM AUTHOR]

The distance matrix of a simple graph G is D ( G ) = ( d i j ) , where d i j is the distance between i th and j th vertices of G . The spectrum of the distance matrix is known as the distance spectrum or D -spectrum of G . A simple connected graph G is called distance regular if it is regular, and if for any two vertices x , y ∈ G at distance i , there are constant number of neighbors c i and b i of y at distance i − 1 and i + 1 from x respectively. In this paper we prove that distance regular graphs with diameter d have at most d + 1 distinct D -eigenvalues. We find an equitable partition and the corresponding quotient matrix of the distance regular graph which gives the distinct D -eigenvalues. We also prove that distance regular graphs satisfying b i = c d − 1 have at most ⌈ d 2 ⌉ + 2 distinct D -eigenvalues. Applying these results we find the distance spectrum of some distance regular graphs including the well known Johnson graphs. Finally we also answer the questions asked by Lin et al. [16] . [ABSTRACT FROM AUTHOR]

From the parameters ( n , k , t , λ , μ ) of a directed strongly regular graph (dsrg) A. Duval (1988) [4] showed how to compute the eigenvalues and multiplicities of the adjacency matrix, and thus the rank of the adjacency matrix. For every rational number q , where 1 5 ≤ q ≤ 7 10 , there is a feasible (i.e., satisfying Duval's conditions) parameter set for a dsrg with rank 5 and with k n = q . In this paper we show that there exist a dsrg with such a feasible parameter set only if k n is 1 5 , 1 3 , 2 5 , 1 2 , 3 5 , or 2 3 . Every dsrg with rank 5 therefore has parameters of a known graph. The proof is based on an enumeration of 5 × 5 matrices with entries in { 0 , 1 } . [ABSTRACT FROM AUTHOR]

A P-set of a symmetric matrix A is a set α of indices such that the nullity of the matrix obtained from A by removing rows and columns indexed by α is | α | more than the nullity of A . It is known that each subset of a P-set is a P-set. It is also known that a set of indices such that each singleton subset is a P-set need not be a P-set. This note shows that if all pairs of vertices of a set with at least two elements are P-sets, then the set is a P-set. [ABSTRACT FROM AUTHOR]

Connected graphs with the same number of vertices and edges are called unicyclic graphs. All unicyclic graphs whose second largest eigenvalue does not exceed 1, denoted by U ( λ 2 ) , are determined by Xu [10] . Let G t , s denote the graph obtained by attaching t ≥ 1 pendent paths of length 2 and s ≥ 0 pendent edges to a vertex of a triangle. In this paper, we first prove that the graph G t , s is determined by its adjacency spectrum. Then we prove that the graphs in U ( λ 2 ) are determined by their adjacency spectra except for four graphs. [ABSTRACT FROM AUTHOR]

Let G = ( V , E ) be a simple graph with vertex set V ( G ) = { v 1 , v 2 , … , v n } and edge set E ( G ) . The distance signless Laplacian spectral radius of a connected graph G is the spectral radius of the distance signless Laplacian matrix of G , defined as Q ( G ) = Tr ( G ) + D ( G ) , where Tr ( G ) is the diagonal matrix of vertex transmissions of G and D ( G ) is the distance matrix of G . In [10] , Xing et al. determined the graph with minimum distance signless Laplacian spectral radius among the trees with fixed number of vertices. For n ≥ 3 , let T n − 3 , 1 1 be the n -vertex tree of maximum degree n − 2 . In this paper, we show that T n − 3 , 1 1 gives the second minimum distance signless Laplacian spectral radius among the trees with fixed number of vertices. Moreover, we prove two conjectures involving the second largest eigenvalue of the distance signless Laplacian matrix Q ( G ) of graph G . [ABSTRACT FROM AUTHOR]

By | V ( G ) | , | E ( G ) | , η ( G ) , and m ( G ) we denote respectively the order, the number of edges, the nullity, and the matching number of a (simple) graph G . Recently Wang and Wong have proved that for every graph G , η ( G ) ≤ | V ( G ) | − 2 m ( G ) + 2 c ( G ) , where c ( G ) = | E ( G ) | − | V ( G ) | + θ ( G ) , θ ( G ) being the number of connected components of G . In this paper graphs G that satisfy the equality η ( G ) = | V ( G ) | − 2 m ( G ) + 2 c ( G ) are characterized. [ABSTRACT FROM AUTHOR]

There is a mistake in the proof of Lemma 10 of Yuan (2014) [3] , and the corrected proof is provided in this Corrigendum note. [ABSTRACT FROM AUTHOR]

The distance Laplacian matrix of a connected graph G is defined in [2,3] and it is proved that for a graph G on n vertices, if the complement of G is connected, then the second smallest distance Laplacian eigenvalue is strictly greater than n . In this article, we consider the graphs whose complement is a tree or a unicyclic graph, and characterize the graphs among them having n + 1 as the second smallest distance Laplacian eigenvalue. We prove that the largest distance Laplacian eigenvalue of a path is simple and the corresponding eigenvector has the similar property like that of a Fiedler vector. [ABSTRACT FROM AUTHOR]

Abstract: We prove that the diameter of the commuting graph of the full matrix ring over the real numbers is at most five. This answers, in the affirmative, a conjecture proposed by Akbari–Mohammadian–Radjavi–Raja, for the special case of the field of real numbers. [Copyright &y& Elsevier]

Abstract: The energy of a simple graph , denoted by , is defined as the sum of the absolute values of all eigenvalues of its adjacency matrix. Let denote the cycle of order and the graph obtained from joining two cycles by a path with its two leaves. Let denote the class of all bipartite bicyclic graphs but not the graph , which is obtained from joining two cycles and ( and ) by an edge. In [I. Gutman, D. Vidović, Quest for molecular graphs with maximal energy: a computer experiment, J. Chem. Inf. Sci. 41(2001) 1002–1005], Gutman and Vidović conjectured that the bicyclic graph with maximal energy is , for and . In [X. Li, J. Zhang, On bicyclic graphs with maximal energy, Linear Algebra Appl. 427(2007) 87–98], Li and Zhang showed that the conjecture is true for graphs in the class . However, they could not determine which of the two graphs and has the maximal value of energy. In [B. Furtula, S. Radenković, I. Gutman, Bicyclic molecular graphs with the greatest energy, J. Serb. Chem. Soc. 73(4)(2008) 431–433], numerical computations up to were reported, supporting the conjecture. So, it is still necessary to have a mathematical proof to this conjecture. This paper is to show that the energy of is larger than that of , which proves the conjecture for bipartite bicyclic graphs. For non-bipartite bicyclic graphs, the conjecture is still open. [Copyright &y& Elsevier]