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.     

The energy of random graphs

In 1970s, Gutman introduced the concept of the energy E(G) for a simple graph G, which is defined as the sum of the absolute values of the eigenvalues of G. This graph invariant has attracted much attention, and many lower and upper bounds have been established for some classes of graphs among which bipartite graphs are of particular interest. But there are only a few graphs attaining the equalities of those bounds. We however obtain an exact estimate of the energy for almost all graphs by Wigner’s semi-circle law, which generalizes a result of Nikiforov. We further investigate the energy of random multipartite graphs by considering a generalization of Wigner matrix, and obtain some estimates of the energy for random multipartite graphs.     

Energy of generalized line graphs

The energy of a graph is equal to the sum of the absolute values of its eigenvalues. Line graphs play an important role in the study of graph theory. Generalized line graphs extend the ideas of both line graphs and cocktail party graphs. In this paper, we establish relations between the energy of the generalized line graph of a graph G and the Laplacian and signless Laplacian energies of G. We give upper and lower bounds for the energy of generalized line graphs. Finally, we present upper and lower bounds for some special graphs.     

Energy of line graphs

The energy of a graph is equal to the sum of the absolute values of its eigenvalues. The energy of a matrix is equal to the sum of its singular values. We establish relations between the energy of the line graph of a graph G and the energies associated with the Laplacian and signless Laplacian matrices of G.     

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.     

Towards a spectral theory of graphs based on the signless Laplacian, II

A spectral graph theory is a theory in which graphs are studied by means of eigenvalues of a matrix M which is in a prescribed way defined for any graph. This theory is called M-theory. We outline a spectral theory of graphs based on the signless Laplacians Q and compare it with other spectral theories, in particular to those based on the adjacency matrix A and the Laplacian L. As demonstrated in the first part, the Q-theory can be constructed in part using various connections to other theories: equivalency with A-theory and L-theory for regular graphs, common features with L-theory for bipartite graphs, general analogies with A-theory and analogies with A-theory via line graphs and subdivision graphs. In this part, we introduce notions of enriched and restricted spectral theories and present results on integral graphs, enumeration of spanning trees, characterizations by eigenvalues, cospectral graphs and graph angles.     

On integral sum graphs

A graph G is said to be an integral sum graph if its nodes can be given a labeling f with distinct integers, so that for any two distinct nodes u and v of G, uv is an edge of G if and only if f(u)+f(v)=f(w) for some node w in G. A node of G is called a saturated node if it is adjacent to every other node of G. We show that any integral sum graph which is not K₃ has at most two saturated nodes. We determine the structure for all integral sum graphs with exactly two saturated nodes, and give an upper bound for the number of edges of a connected integral sum graph with no saturated nodes. We introduce a method of identification on constructing new connected integral sum graphs from given integral sum graphs with a saturated node. Moreover, we show that every graph is an induced subgraph of a connected integral sum graph. Miscellaneous related results are also presented.     

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.     

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

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

On the seidel integral complete multipartite graphs

For a simple undirected graph G, denote by A(G) the (0,1)-adjacency matrix of G. Let thematrix S(G) = J-I-2A(G) be its Seidel matrix, and let S _G (??) = det(??I-S(G)) be its Seidel characteristic polynomial, where I is an identity matrix and J is a square matrix all of whose entries are equal to 1. If all eigenvalues of S _G (??) are integral, then the graph G is called S-integral. In this paper, our main goal is to investigate the eigenvalues of S _G (??) for the complete multipartite graphs G = $G = K_{n_1 ,n_2 ,...n_t } $ . A necessary and sufficient condition for the complete tripartite graphs K _m,n,t and the complete multipartite graphs to be S-integral is given, respectively.     

The least eigenvalue of graphs with given connectivity

Let G be a simple graph and A(G) be the adjacency matrix of G. The eigenvalues of G are those of A(G). In this paper, we characterize the graphs with the minimal least eigenvalue among all graphs of fixed order with given vertex connectivity or edge connectivity.     

Planar unit-distance graphs having planar unit-distance complement

A graph G=(V,E) is called a unit-distance graph in the plane if there is an embedding of V into the plane such that every pair of adjacent vertices are at unit distance apart. If an embedding of V satisfies the condition that two vertices are adjacent if and only if they are at unit distance apart, then G is called a strict unit-distance graph in the plane. A graph G is a (strict) co-unit-distance graph, if both G and its complement are (strict) unit-distance graphs in the plane. We show by an exhaustive enumeration that there are exactly 69 co-unit-distance graphs (65 are strict co-unit-distance graphs), 55 of which are connected (51 are connected strict co-unit-distance graphs), and seven are self-complementary.     

An extension of regular supermagic graphs

A graph is called supermagic if it admits a labelling of the edges by pairwise different consecutive positive integers such that the sum of the labels of the edges incident with a vertex is independent of the particular vertex. In this paper we consider an extension of regular supermagic graphs and apply it to some constructions of supermagic graphs. Using the extension we prove that for any graph G there is a supermagic regular graph which contains an induced subgraph isomorphic to G.     

On the spectral spread of bicyclic graphs with given girth

The spectral spread of a graph is defined to be the difference between the largest and the least eigenvalue of the adjacency matrix of the graph. A graph G is said to be bicyclic, if G is connected and |E(G)| = |V(G)|+ 1. Let B(n, g) be the set of bicyclic graphs on n vertices with girth g. In this paper some properties about the least eigenvalues of graphs are given, by which the unique graph with maximal spectral spread in B(n, g) is determined.     

On integral Cayley sum graphs

Let S be a subset of a finite abelian group G. The Cayley sum graph Cay⁺(G, S) of G with respect to S is a graph whose vertex set is G and two vertices g and h are joined by an edge if and only if g + h ∈ S. We call a finite abelian group G a Cayley sum integral group if for every subset S of G, Cay⁺(G, S) is integral i.e., all eigenvalues of its adjacency matrix are integers. In this paper, we prove that all Cayley sum integral groups are represented by Z₃ and Zn₂ ⁿ, n ≥ 1, where Z_k is the group of integers modulo k. Also, we classify simple connected cubic integral Cayley sum graphs.     

Note on unicyclic graphs with given number of pendent vertices and minimal energy

For a simple graph G, the energy E(G) is defined as the sum of the absolute values of all eigenvalues of its adjacency matrix. Let G(n,p) denote the set of unicyclic graphs with n vertices and p pendent vertices. In [H. Hua, M. Wang, Unicyclic graphs with given number of pendent vertices and minimal energy, Linear Algebra Appl. 426 (2007) 478-489], Hua and Wang discussed the graphs that have minimal energy in G(n,p), and determined the minimal-energy graphs among almost all different cases of n and p. In their work, certain case of the values was left as an open problem in which the minimal-energy species have to be chosen in two candidate graphs, but cannot be determined by comparing of the corresponding coefficients of their characteristic polynomials. This paper aims at solving the problem completely, by using the well-known Coulson integral formula.     

The integral graphs with index 3 and exactly two main eigenvalues

A graph is called integral if the spectrum of its adjacency matrix has only integral eigenvalues. An eigenvalue of a graph is called main eigenvalue if it has an eigenvector such that the sum of whose entries is not equal to zero. In this paper, we show that there are exactly 25 connected integral graphs with exactly two main eigenvalues and index 3.     

Sharp bounds on the distance spectral radius and the distance energy of graphs

The D-eigenvalues {μ₁,μ₂,…,…,μ_p} of a graph G are the eigenvalues of its distance matrix D and form the D-spectrum of G denoted by spec_D(G). The greatest D-eigenvalue is called the D-spectral radius of G denoted by μ₁. The D-energy E_D(G) of the graph G is the sum of the absolute values of its D-eigenvalues. In this paper we obtain some lower bounds for μ₁ and characterize those graphs for which these bounds are best possible. We also obtain an upperbound for E_D(G) and determine those maximal D-energy graphs.     

Some results on exclusive sum graphs

Let N(Z) denote the set of all positive integers (integers). The sum graph G ⁺(S) of a finite subset S?N(Z) is the graph (S,E) with uv∈E if and only if u+v∈S. A graph G is said to be an (integral) sum graph if it is isomorphic to the sum graph of some S?N(Z). A sum labelling S is called an exclusive sum labelling if u+v∈S?V(G) for any edge uv∈E(G). We say that G is labeled exclusively. The least number r of isolated vertices such that G∪rK ₁ is an exclusive sum graph is called the exclusive sum number ε(G) of graph G. In this paper, we discuss the exclusive sum number of disjoint union of two graphs and the exclusive sum number of some graph classes.