BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
In 1977 Smith characterized graphs with exactly one positive eigenvalue. Since then, many particular results related to graphs with exactly two positive eigenvalues have emerged. In this paper we conclude this investigation by giving a full characterization of these graphs.
A topological index reflects the physical, chemical and structural properties of a molecule, and its study has an important role in molecular topology, chemical graph theory and mathematical chemistry. It is a natural problem to characterize non-isomorphic graphs with the same topological index value. By introducing a relation on trees with respect to edge division vectors, denoted by ⟨Tn,⪯⟩, in this paper we give some results for the relation order in ⟨Tn,⪯⟩, it allows us to compare the size of the topological index value without relying on the specific forms of them, and naturally we can determine which trees have the same topological index value. Based on these results we characterize some classes of trees that are uniquely determined by their edge division vectors and construct infinite classes of non-isomorphic trees with the same topological index value, particularly such trees of order no more than 10 are completely determined.
Let Gn,α be the set of connected graphs with order n and independence number α. Given k=n−α, the graph with minimum spectral radius among Gn,α is called the minimizer graph. Stevanović in the classical book [D. Stevanović, Spectral Radius of Graphs, Academic Press, Amsterdam, 2015.] pointed that determining minimizer graph in Gn,α appears to be a tough problem on page 96. Very recently, Lou and Guo in \cite{Lou} proved that the minimizer graph of Gn,α must be a tree if α≥⌈2n⌉. In this paper, we further give the structural features for the minimizer graph in detail, and then provide of a constructing theorem for it. Thus, theoretically we completely determine the minimizer graphs in Gn,α along with their spectral radius for any given k=n−α≤2n. As an application, we determine all the minimizer graphs in Gn,α for α=n−1,n−2,n−3,n−4,n−5,n−6 along with their spectral radii, the first four results are known in \cite{Xu,Lou} and the last two are new.
The inertia of a graph G is defined to be the triplet In(G)=(p(G),n(G), η(G)), where p(G), n(G) and η(G) are the numbers of positive, negative and zero eigenvalues (including multiplicities) of the adjacency matrix A(G), respectively. Traditionally p(G) (resp. n(G)) is called the positive (resp. negative) inertia index of G. In this paper, we introduce three types of congruent transformations for graphs that keep the positive inertia index and negative inertia index. By using these congruent transformations, we determine all graphs with exactly two positive eigenvalues and one zero eigenvalue.
In this paper we consider r-regular graphs G that admit the vertex set partition such that one of the induced subgraphs is the join of an s-vertex clique and a t-vertex co-clique and represents a star complement for an eigenvalue μ of G. The cases in which one of the parameters s,t is less than 2 or μ=r are already resolved. It is conjectured in [J. Wang, X. Yuan, L. Liu, Regular graphs with a prescribed complete multipartite graph as a star complement, Linear Algebra Appl.~579 (2019) 302--319] that if s,t≥2 and μ=r, then μ=−2,t=2 and G=(s+1)K2. For μ=−t we verify this conjecture to be true. We further study the case in which μ=−t and confirm the conjecture provided t2−4μ2t−4μ3=0. For the remaining possibility we determine the structure of a putative counterexample and relate its existence to the existence of a particular 2-class block design. It occurs that the smallest counterexample would have 1265 vertices.
A graph is minimally k-connected (k-edge-connected) if it is k-connected (k-edge-connected) and deleting arbitrary chosen edge always leaves a graph which is not k-connected (k-edge-connected). A classic result of minimally k-connected graph is given by Mader who determined the extremal size of a minimally k-connected graph of high order in 1937. Naturally, for a fixed size of a minimally k-(edge)-connected graphs, what is the extremal spectral radius? In this paper, we determine the maximum spectral radius for the minimally 2-connected (2-edge-connected) graphs of given size, moreover the corresponding extremal graphs are also determined.
Let Sn denote the symmetric group of degree n with n≥3. Set S={cn=(1 2… n),cn−1,(1 2)}. Let Γn=Cay(Sn,S) be the Cayley graph on Sn with respect to S. In this paper, we show that Γn (n≥13) is a normal Cayley graph, and that the full automorphism group of Γn is equal to Aut(Γn)=R(Sn)⋊⟨Inn(ϕ)⟩≅Sn⋊Z2, where R(Sn) is the right regular representation of Sn, ϕ=(1 2)(3 n)(4 n−1)(5 n−2)⋯ (∈Sn), and Inn(ϕ) is the inner isomorphism of Sn induced by ϕ.
Let p be an odd prime, and D2p=⟨τ,σ∣τp=σ2=e,στσ=τ−1⟩ the dihedral group of order 2p. In this paper, we provide the number of (connected) Cayley (di-)graphs on D2p up to isomorphism by using the Pólya enumeration theorem. In the process, we also enumerate (connected) Cayley digraphs on D2p of out-degree k up to isomorphism for each k.
In this paper, we give a necessary and sufficient condition for the integrality of Cayley graphs over the dihedral group Dn=⟨a,b∣an=b2=1,bab=a−1⟩. Moreover, we also obtain some simple sufficient conditions for the integrality of Cayley graphs over Dn in terms of the Boolean algebra of ⟨a⟩, from which we find infinite classes of integral Cayley graphs over Dn. In particular, we completely determine all integral Cayley graphs over the dihedral group Dp for a prime p.
Let G(4,2) be the set of connected regular graphs with four distinct eigenvalues in which exactly two eigenvalues are simple, G(4,2,−1) (resp. G(4,2,0)) the set of graphs belonging to G(4,2) with −1 (resp. 0) as an eigenvalue, and G(4,≥−1) the set of connected regular graphs with four distinct eigenvalues and second least eigenvalue not less than −1. In this paper, we prove the non-existence of connected graphs having four distinct eigenvalues in which at least three eigenvalues are simple, and determine all the graphs in G(4,2,−1). As a by-product of this work, we characterize all the graphs belonging to G(4,≥−1) and G(4,2,0), respectively, and show that all these graphs are determined by their spectra.
An eigenvalue of a graph G is called a main eigenvalue if it has an eigenvector the sum of whose entries is not equal to zero. It is well known that a graph G has exactly two main eigenvalues if and only if there exists a unique pair of integers a and b such that ∑u∈N(v)d(u)=ad(v)+b for every vertex v∈V(G). We collect such connected graph G in the set G(a,b). In this paper, we mainly focus to the existence of such a and b, and give the necessary and sufficient condition for G(a,b)=∅. In addition, we give the bound for the vertex degrees of G∈G(a,b) and use the bound to characterize the graphs in G(a,b) for some feasible pairs (a,b).
In this paper, we completely characterize the graphs with third largest distance eigenvalue at most −1 and smallest distance eigenvalue at least −3. In particular, we determine all graphs whose distance matrices have exactly two eigenvalues (counting multiplicity) different from −1 and −3. It turns out that such graphs consist of three infinite classes, and all of them are determined by their distance spectra. We also show that the friendship graph is determined by its distance spectrum.
Harary and Schwenk posed the problem forty years ago: Which graphs have distinct adjacency eigenvalues? In this paper, we obtain a necessary and sufficient condition for an Hermitian matrix with simple spectral radius and distinct eigenvalues. As its application, we give an algebraic characterization to the Harary-Schwenk's problem. As an extension of their problem, we also obtain a necessary and sufficient condition for a positive semidefinite matrix with simple least eigenvalue and distinct eigenvalues, which can provide an algebraic characterization to their problem with respect to the (normalized) Laplacian matrix.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.