Spectral characterization of some graphs

The lexicographic product (or composition) of a cycle of length r with a totally disconnected graph on n vertices is shown to be a graph characterized by the eigenvalues of its adjacency matrix for all odd r.     

Spectral characterization of some weighted rooted graphs with cliques

The level of a vertex in a rooted graph is one more than its distance from the root vertex. A generalized Bethe tree is a rooted tree in which vertices at the same level have the same degree. We characterize completely the eigenvalues of the Laplacian, signless Laplacian and adjacency matrices of a weighted rooted graph G obtained from a weighted generalized Bethe tree of k levels and weighted cliques in which

(1)

the edges connecting vertices at consecutive levels have the same weight,

(2)

each set of children, in one or more levels, defines a weighted clique, and

(3)

cliques at the same level are isomorphic.

These eigenvalues are the eigenvalues of symmetric tridiagonal matrices of order Moreover, we give results on the multiplicity of the eigenvalues, on the spectral radii and on the algebraic conectivity. Finally, we apply the results to the unweighted case and some particular graphs are studied.     

Spectral characterization of graphs whose second largest eigenvalue is less than 1

Graphs with second largest eigenvalue λ₂?1 are extensively studied, however, whether they are determined by their adjacency spectra or not is less considered. In this paper we completely characterize all the connected bipartite graphs with λ₂<1 that are determined by their adjacency spectra. In addition, we prove that all the connected non-bipartite graphs with girth no less than 4 and λ₂<1 are determined by their adjacency spectra.     

Spectral properties of Pascal graphs

We obtain spectral properties of the Pascal graphs by exploring its spectral graph invariants such as the algebraic connectivity, the first three largest Laplacian eigenvalues and the nullity. Some open problems pertaining to the Pascal graphs are given.     

Spectral characterizations of sandglass graphs

The sandglass graph is obtained by appending a triangle to each pendant vertex of a path. It is proved that sandglass graphs are determined by their adjacency spectra as well as their Laplacian spectra.     

Spectral radius and Hamiltonian graphs

In the paper, we will present two sufficient conditions for a bipartite graph to be Hamiltonian and a graph to be traceable, respectively.     

Spectral radius and Hamiltonicity of graphs

Let G be a graph of order n and μ(G) be the largest eigenvalue of its adjacency matrix. Let be the complement of G.Write K_n-1+v for the complete graph on n-1 vertices together with an isolated vertex, and K_n-1+e for the complete graph on n-1 vertices with a pendent edge.We show that:If μ(G)?n-2, then G contains a Hamiltonian path unless G=K_n-1+v; if strict inequality holds, then G contains a Hamiltonian cycle unless G=K_n-1+e.If , then G contains a Hamiltonian path unless G=K_n-1+v.If , then G contains a Hamiltonian cycle unless G=K_n-1+e.     

Spectral properties of complex unit gain graphs

A complex unit gain graph is a graph where each orientation of an edge is given a complex unit, which is the inverse of the complex unit assigned to the opposite orientation. We extend some fundamental concepts from spectral graph theory to complex unit gain graphs. We define the adjacency, incidence and Laplacian matrices, and study each of them. The main results of the paper are eigenvalue bounds for the adjacency and Laplacian matrices.     

Spectral results on graphs with regularity constraints

Graphs with (k, τ)-regular sets and equitable partitions are examples of graphs with regularity constraints. A (k, τ)-regular set of a graph G is a subset of vertices S ⊆ V(G) inducing a k-regular subgraph and such that each vertex not in S has τ neighbors in S. The existence of such structures in a graph provides some information about the eigenvalues and eigenvectors of its adjacency matrix. For example, if a graph G has a (k₁, τ₁)-regular set S₁ and a (k₂, τ₂)-regular set S₂ such that k₁ − τ₁ = k₂ − τ₂ = λ, then λ is an eigenvalue of G with a certain eigenvector. Additionally, considering primitive strongly regular graphs, a necessary and sufficient condition for a particular subset of vertices to be (k, τ)-regular is introduced. Another example comes from the existence of an equitable partition in a graph. If a graph G, has an equitable partition π then its line graph, L(G), also has an equitable partition, , induced by π, and the adjacency matrix of the quotient graph is obtained from the adjacency matrix of G/π.     

Spectral properties of the Laplacian on bond-percolation graphs

Bond-percolation graphs are random subgraphs of the d-dimensional integer lattice generated by a standard bond-percolation process. The associated graph Laplacians, subject to Dirichlet or Neumann conditions at cluster boundaries, represent bounded, self-adjoint, ergodic random operators with off-diagonal disorder. They possess almost surely the non-random spectrum [0, 4d] and a self-averaging integrated density of states. The integrated density of states is shown to exhibit Lifshits tails at both spectral edges in the non-percolating phase. While the characteristic exponent of the Lifshits tail for the Dirichlet (Neumann) Laplacian at the lower (upper) spectral edge equals d/2, and thus depends on the spatial dimension, this is not the case at the upper (lower) spectral edge,where the exponent equals 1/2.     

Spectral radius of graphs with given matching number

In this paper, we show that of all graphs of order n with matching number β, the graphs with maximal spectral radius are K_n if n = 2β or 2β + 1; if 2β + 2 ? n < 3β + 2; or if n = 3β + 2; if n > 3β + 2, where is the empty graph on t vertices.     

A characterization of ptolemaic graphs

A connected graph G is ptolemaic provided that for each four vertices U_i, 1 ≤ i ≤ 4, of G, the six distances d_ii = d_G (U_i, U_i), i ≠ j satisfy the inequality d₁₂d₃₄ ≤ d₁₃d₂₄ + d₁₄d₂₃ (shown by Ptolemy to hold in Euclidean spaces). Ptolemaic graphs were first investigated by Chartrand and Kay, who showed that weakly geodetic ptolemaic graphs are precisely Husimi trees (in particular, trees are ptolemaic). in the present paper several characterizations of ptolemaic graphs are given. It is shown, for example, that a connected graph G is ptolemaic if and only iffor each nondisjoint cliques P, Q of G, their intersection is a cutset of G which separates P-Q and Q-P. An operation is exhibited which generates all finite ptolemaic graphs from complete graphs.     

A characterization of competition graphs

Characterization of competition graphs for arbitrary and acyclic directed graphs are presented.     

A characterization of radius-critical graphs

A graph G is radius-critical if every proper induced connected subgraph of G has radius strictly smaller than the original graph. Our main purpose is to characterize all such graphs.