Bicyclic graphs with exactly two main eigenvalues

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, and it is well known that a graph has exactly one main eigenvalue if and only if it is regular. In this work, all connected bicyclic graphs with exactly two main eigenvalues are determined.     

恰有两个主特征值的图的性质

设λ是图G的一个特征值,如果存在属于λ的一个特征向量X=(x_1,x_2,…,x_n)~T,使得(?)x_i≠0,则λ称为图G的主特征值.将恰有两个主特征值的一个充要条件做了进一步推广,并在此基础上给出恰有两个主特征值的图的一些性质以及恰有两个主特征值的图的一些运算结果.     

On Integral Graphs with Few Cycles

A graph is called integral if the spectrum of its adjacency matrix has only integer eigenvalues. In this paper, all integral graphs with at most two cycles (trees, unicyclic and bicyclic graphs) with no eigenvalue 0 are identified. Moreover, we give some results on unicyclic integral graphs with exactly one eigenvalue 0.     

Nowhere-zero eigenvectors of graphs

A vector is called nowhere-zero if it has no zero entry. In this article we search for graphs with nowhere-zero eigenvectors. We prove that distance-regular graphs and vertex-transitive graphs have nowhere-zero eigenvectors for all of their eigenvalues and edge-transitive graphs have nowhere-zero eigenvectors for all non-zero eigenvalues. Among other results, it is shown that a graph with three distinct eigenvalues has a nowhere-zero eigenvector for its smallest eigenvalue.     

Distance spectra and distance energy of integral circulant graphs

The distance energy of a graph G is a recently developed energy-type invariant, defined as the sum of absolute values of the eigenvalues of the distance matrix of G. There was a vast research for the pairs and families of non-cospectral graphs having equal distance energy, and most of these constructions were based on the join of graphs. A graph is called circulant if it is Cayley graph on the circulant group, i.e. its adjacency matrix is circulant. A graph is called integral if all eigenvalues of its adjacency matrix are integers. Integral circulant graphs play an important role in modeling quantum spin networks supporting the perfect state transfer. In this paper, we characterize the distance spectra of integral circulant graphs and prove that these graphs have integral eigenvalues of distance matrix D. Furthermore, we calculate the distance spectra and distance energy of unitary Cayley graphs. In conclusion, we present two families of pairs (G₁,G₂) of integral circulant graphs with equal distance energy - in the first family G₁ is subgraph of G₂, while in the second family the diameter of both graphs is three.     

On graphs with given main eigenvalues

An eigenvalue of a graph is main if it has an eigenvector, the sum of whose entries is not equal to zero. Extending previous results of Hagos and Hou et al. we obtain two conditions for graphs with given main eigenvalues. All trees and connected unicyclic graphs with exactly two main eigenvalues were characterized by Hou et al. Extending their results, we determine all bicyclic connected graphs with exactly two main eigenvalues.     

恰有两个Q-主特征值的三圈图

图G的无符号拉普拉斯矩阵定义为图G的邻接矩阵与度对角矩阵的和,其特征值称为图G的Q-特征值.图G的一个Q-特征值称为Q-主特征值,如果它有一个特征向量其分量的和不等于零.确定了所有恰有两个Q-主特征值的三圈图.     

On graphs whose star sets are (co-)cliques

In this paper we study graphs all of whose star sets induce cliques or co-cliques. We show that the star sets of every tree for each eigenvalue are independent sets. Among other results it is shown that each star set of a connected graph G with three distinct eigenvalues induces a clique if and only if G=K_1,2 or K_2,…,2. It is also proved that stars are the only graphs with three distinct eigenvalues having a star partition with independent star sets.     

ALL GRAPHS ON A NON-PRIME NUMBER OF VERTICES ARE DESTRUCTIBLE

ABSTRACT

A connected, nontrivial, simple graph of order v is said to be α,β destructible if α,β are integral factors of v and an α-set of edges, E', exists whose removal from G isolates exactly the vertices in a β-set V'. Graphs which are not α, β destructible for any α.β are called stable. In this paper we prove that all graphs on a non-prime number v of vertices are α,β destructible for some a which divides v.     

Tricyclic graphs with exactly two main eigenvalues

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. Let G ₀ be the graph obtained from G by deleting all pendant vertices and δ(G) the minimum degree of vertices of G. In this paper, all connected tricyclic graphs G with δ(G ₀) ≥ 2 and exactly two main eigenvalues are determined.     

ON STABLE GRAPHS

ABSTRACT

A connected, nontrivial, simple graph G of order v is said to be α, β destructible if α, β are integral factors of v and an α-set of edges, E', exists whose removal from G isolates exactly the vertices in a β-set V'. Graphs which are not α, β destructible for any α,β are called stable. Classes of stable graphs are provided and critically stable graphs of prime order are characterized.     

Constructably Laplacian integral graphs

A graph is Laplacian integral if the spectrum of its Laplacian matrix consists entirely of integers. We consider the class of constructably Laplacian integral graphs - those graphs that be constructed from an empty graph by adding a sequence of edges in such a way that each time a new edge is added, the resulting graph is Laplacian integral. We characterize the constructably Laplacian integral graphs in terms of certain forbidden vertex-induced subgraphs, and consider the number of nonisomorphic Laplacian integral graphs that can be constructed by adding a suitable edge to a constructably Laplacian integral graph. We also discuss the eigenvalues of constructably Laplacian integral graphs, and identify families of isospectral nonisomorphic graphs within the class.     

Trees, unicyclic graphs and bicyclic graphs with exactly two Q-main eigenvalues

The signless Laplacian matrix of a graph G is defined to be the sum of its adjacency matrix and degree diagonal matrix, and its eigenvalues are called Q-eigenvalues of G. A Q-eigenvalue of a graph G is called a Q-main eigenvalue if it has an eigenvector the sum of whose entries is not equal to zero. In this work, all trees, unicyclic graphs and bicyclic graphs with exactly two Q-main eigenvalues are determined.     

Two spectral characterizations of regular, bipartite graphs with five eigenvalues

Graphs with a few distinct eigenvalues usually possess an interesting combinatorial structure. We show that regular, bipartite graphs with at most six distinct eigenvalues have the property that each vertex belongs to the constant number of quadrangles. This enables to determine, from the spectrum alone, the feasible families of numbers of common neighbors for each vertex with other vertices in its part. For particular spectra, such as [6,2⁹,0⁶,-2⁹,-6] (where exponents denote eigenvalue multiplicities), there is a unique such family, which makes it possible to characterize all graphs with this spectrum.Using this lemma we also to show that, for r?2, a graph has spectrum if and only if it is a graph of a 1-resolvable transversal design TD(r,r), i.e., if it corresponds to the complete set of mutually orthogonal Latin squares of size r in a well-defined manner.     

Q‐integral unicyclic,bicyclic and tricyclic graphs

A graph is called Q‐integral if its signless Laplacian spectrum consists of integers. In this paper, we characterize a class of k‐cyclic graphs whose second smallest signless Laplacian eigenvalue is less than one. Using this result we determine all the Q‐integral unicyclic, bicyclic and tricyclic graphs.     

On the maximum multiplicity of an eigenvalue in a matrix whose graph contains exactly one cycle

We consider the general problem of determining the maximum possible multiplicity of an eigenvalue in a Hermitian matrix whose graph contains exactly one cycle. For some cases we express that maximum multiplicity in terms of certain parameters associated with the graph.     

Spectrum of the 1‐Laplacian and Cheeger's Constant on Graphs

We develop a nonlinear spectral graph theory, in which the Laplace operator is replaced by the 1 ? Laplacian Δ₁. The eigenvalue problem is to solve a nonlinear system involving a set valued function. In the study, we investigate the structure of the solutions, the minimax characterization of eigenvalues, the multiplicity theorem, etc. The eigenvalues as well as the eigenvectors are computed for several elementary graphs. The graphic feature of eigenvalues are also studied. In particular, Cheeger's constant, which has only some upper and lower bounds in linear spectral theory, equals to the first nonzero Δ₁ eigenvalue for connected graphs.     

A CHARACTERIZATION OF STABLE GRAPHS ON A MAXIMUM(MINIMUM) NUMBER OF EDGES

ABSTRACT

A connected, nontrivial, simple graph of order v is said to be α,β destructible if α,β are factors of v and an α-set of edges, E', exists whose removal from G isolates exactly the vertices in α,β-set V'. Graphs which are not α,β destructible for any α,β are called stable, If G is a stable graph on a prime number p ≥ 7 of vertices, then we show that G has a maximum number of edges if and only if G is K_2,p-2, We also characterize stable graphs on a minimum number of edges.     

Graphs with Exactly Two Negative Eigenvalues

In this paper we determine all finite connected graphs whose spectrum contains exactly two negative eigenvalues. The main theorem says that a graph has exactly two negative eigenvalues if and only if its “canonical graph” (defined below) is one of nine particular graphs on 3, 4, 5 and 6 vertices.