Spectra of Some Interesting Combinatorial Matrices Related to Oriented Spanning Trees on a Directed Graph

The Laplacian of a directed graph G is the matrix L(G) = O(G) –, A(G) where A(G) is the adjaceney matrix of G and O(G) the diagonal matrix of vertex outdegrees. The eigenvalues of G are the eigenvalues of A(G). Given a directed graph G we construct a derived directed graph D(G) whose vertices are the oriented spanning trees of G. Using a counting argument, we describe the eigenvalues of D(G) and their multiplicities in terms of the eigenvalues of the induced subgraphs and the Laplacian matrix of G. Finally we compute the eigenvalues of D(G) for some specific directed graphs G. A recent conjecture of Propp for D(H _n ) follows, where H _n stands for the complete directed graph on n vertices without loops.     

Almost all steinhaus graphs have diameter 2

A Steinhaus graph is a graph with n vertices whose adjacency matrix (a_{i, j}) satisfies the condition that a_{i, j} ? a_{a--1, j--1} + a _{i--1, j} (mod 2) for each 1 < i < j ≤ n. It is clear that a Steinhaus graph is determined by its first row. In [3] Bringham and Dutton conjecture that almost all Steinhaus graphs have diameter 2. That is, as n approaches infinity, the ratio of the number of Steinhaus graphs with n vertices having diameter 2 to the total number of Steinhaus graphs approaches 1. Here we prove Bringham and Dutton's conjecture.     

Maximality of the signless Laplacian energy

We study the problem of determining the graph with $n$ vertices having largest signless Laplacian energy. We conjecture it is the complete split graph whose independent set has (roughly) $2n∕3$ vertices. We show that the conjecture is true for several classes of graphs. In particular, the conjecture holds for the set of all complete split graphs of order $n$, for trees, for unicyclic and bicyclic graphs. We also give conditions on the number of edges, number of cycles and number of small eigenvalues so the graph satisfies the conjecture.     

Laplacian coefficients of trees with given number of leaves or vertices of degree two

Let G be a simple undirected n-vertex graph with the characteristic polynomial of its Laplacian matrix . It is well known that for trees the Laplacian coefficient c_n-2 is equal to the Wiener index of G, while c_n-3 is equal to the modified hyper-Wiener index of graph. Using a result of Zhou and Gutman on the relation between the Laplacian coefficients and the matching numbers in subdivided bipartite graphs, we characterize the trees with k leaves (pendent vertices) which simultaneously minimize all Laplacian coefficients. In particular, this extremal balanced starlike tree S(n,k) minimizes the Wiener index, the modified hyper-Wiener index and recently introduced Laplacian-like energy. We prove that graph S(n,n-1-p) has minimal Laplacian coefficients among n-vertex trees with p vertices of degree two. In conclusion, we illustrate on examples of these spectrum-based invariants that the opposite problem of simultaneously maximizing all Laplacian coefficients has no solution, and pose a conjecture on extremal unicyclic graphs with k leaves.     

On the eigenvalues of Cayley graphs on the symmetric group generated by a complete multipartite set of transpositions

Given a finite simple graph G with n vertices, we can construct the Cayley graph on the symmetric group S _n generated by the edges of G, interpreted as transpositions. We show that, if G is complete multipartite, the eigenvalues of the Laplacian of Cay (G) have a simple expression in terms of the irreducible characters of transpositions and of the Littlewood–Richardson coefficients. As a consequence, we can prove that the Laplacians of G and of Cay (G) have the same first nontrivial eigenvalue. This is equivalent to saying that Aldous’s conjecture, asserting that the random walk and the interchange process have the same spectral gap, holds for complete multipartite graphs.     

The Laplacian spread of graphs

The Laplacian spread of a graph is defined as the difference between the largest and second smallest eigenvalues of the Laplacian matrix of the graph. In this paper, bounds are obtained for the Laplacian spread of graphs. By the Laplacian spread, several upper bounds of the Nordhaus-Gaddum type of Laplacian eigenvalues are improved. Some operations on Laplacian spread are presented. Connected c-cyclic graphs with n vertices and Laplacian spread n − 1 are discussed.     

The Laplacian spectra of graphs with a tree structure

Trees are very common in the theory and applications of combinatorics. In this article, we consider graphs whose underlying structure is a tree, except that its vertices are graphs in their own right and where adjacent graphs (vertices) are linked by taking their join. We study the spectral properties of the Laplacian matrices of such graphs. It turns out that in order to capture known spectral properties of the Laplacian matrices of trees, it is necessary to consider the Laplacians of vertex-weighted graphs. We focus on the second smallest eigenvalue of such Laplacians and on the properties of their corresponding eigenvector. We characterize the second smallest eigenvalue in terms of the Perron branches of a tree. Finally, we show that our results are applicable to advancing the solution to the problem of whether there exists a graph on n vertices whose Laplacian has the integer eigenvalues 0, 1, …, n ? 1.     

On the complexity of reconstructing H‐free graphs from their Star Systems

In the Star System problem we are given a set system and asked whether it is realizable by the multi‐set of closed neighborhoods of some graph, i.e. given subsets S₁, S₂, …, S_n of an n‐element set V does there exist a graph G = (V, E) with {N[v]: v∈V} = {S₁, S₂, …, S_n}? For a fixed graph H the H‐free Star System problem is a variant of the Star System problem where it is asked whether a given set system is realizable by closed neighborhoods of a graph containing no H as an induced subgraph. We study the computational complexity of the H‐free Star System problem. We prove that when H is a path or a cycle on at most four vertices the problem is polynomial time solvable. In complement to this result, we show that if H belongs to a certain large class of graphs the H‐free Star System problem is NP‐complete. In particular, the problem is NP‐complete when H is either a cycle or a path on at least five vertices. This yields a complete dichotomy for paths and cycles. Copyright © 2010 John Wiley & Sons, Ltd. 68:113‐124, 2011     

Diperfect graphs

Gallai and Milgram have shown that the vertices of a directed graph, with stability number α(G), can be covered by exactly α(G) disjoint paths. However, the various proofs of this result do not imply the existence of a maximum stable setS and of a partition of the vertex-set into paths μ₁, μ₂, ..., μ_k such tht |μ_i ∩S|=1 for alli. Later, Gallai proved that in a directed graph, the maximum number of vertices in a path is at least equal to the chromatic number; here again, we do not know if there exists an optimal coloring (S ₁,S ₂, ...,S _k) and a path μ such that |μ ∩S _i|=1 for alli. In this paper we show that many directed graphs, like the perfect graphs, have stronger properties: for every maximal stable setS there exists a partition of the vertex set into paths which meet the stable set in only one point. Also: for every optimal coloring there exists a path which meets each color class in only one point. This suggests several conjecties similar to the perfect graph conjecture. Dedicated to Tibor Gallai on his seventieth birthday     

On the Laplacian integral tricyclic graphs

A graph is called Laplacian integral if all its Laplacian eigenvalues are integers. In this paper, we give an edge subdividing theorem for Laplacian eigenvalues of a graph (Theorem 2.1) and characterize a class of k-cyclic graphs whose algebraic connectivity is less than one. Using these results, we determine all the Laplacian integral tricyclic graphs. Furthermore, we show that all the Laplacian integral tricyclic graphs are determined by their Laplacian spectra.     

Fast Fourier Transform for Fitness Landscapes

We cast some classes of fitness landscapes as problems of spectral analysis on various Cayley graphs. In particular, landscapes derived from RNA folding are realized on Hamming graphs and analyzed in terms of Walsh transforms; assignment problems are interpreted as functions on the symmetric group and analyzed in terms of the representation theory of S_n. We show that explicit computation of the Walsh/Fourier transforms is feasible for landscapes with up to 10⁸ configurations using fast Fourier transform techniques. We find that the cost function of a linear sum assignment problem involves only the defining representation of the symmetric group, while quadratic assignment problems are superpositions of the representations indexed by the partitions (n), (n−1,1), (n−2,2), and (n−2,1,1). These correspond to the four smallest eigenvalues of the Laplacian of the Cayley graph obtained by using transpositions as the generating set on S_n.     

The First Three Levels of an Order Preserving Hamiltonian Path in the Subset Lattice

Consider the lattice whose elements are the subsets of the set of positive integers not greater than n ordered by inclusion. The Hasse diagram of this lattice is isomorphic to the n-dimensional hypercube. It is trivial that this graph is Hamiltonian. Let be a Hamiltonian path. We say it is monotone, if for every i, either (a) all subsets of S _i appear among S ₁,...,S _i − 1, or (b) only one (say S) does not, furthermore S _i + 1 = S. Trotter conjectured that if n is sufficiently large, then there are no monotone Hamiltonian paths in the n-cube. He also made a stronger conjecture that states that there is no path with the monotone property that covers all the sets of size at most three. In this paper we disprove this strong conjecture by explicitly constructing a monotone path covering all the 3-sets.     

The Shannon Capacity of a Union

For an undirected graph , let denote the graph whose vertex set is in which two distinct vertices and are adjacent iff for all i between 1 and n either or . The Shannon capacity c(G) of G is the limit , where is the maximum size of an independent set of vertices in . We show that there are graphs G and H such that the Shannon capacity of their disjoint union is (much) bigger than the sum of their capacities. This disproves a conjecture of Shannon raised in 1956. Received: December 8, 1997     

Induced embeddings in Steinhaus graphs

Fix any positive integer n. Let S be the set of all Steinhaus graphs of order n(n − 1)/2 + 1. The vertices for each graph in S are the first n(n − 1)/2 + 1 positive integers. Let I be the set of all labeled graphs of order n with vertices of the form i(i − 1)/2 + 1 for the first n positive integers i. This article shows that the function ϕ : S → I that maps a Steinhaus graph to its induced subgraph is a bijection. Therefore, any graph of order n is isomorphic to an induced subgraph of a Steinhaus graph of order n(n − 1)/2 + 1. This considerably tightens a result of Brigham, Carrington, and Dutton in [Brigham, Carrington, & Dutton, Combin. Inform. System Sci. 17 (1992)], which showed that this could be done with a Steinhaus graph of order 2ⁿ⁻¹. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 1–9, 1998     

On the Laplacian energy of a graph

In this paper we consider the energy of a simple graph with respect to its Laplacian eigenvalues, and prove some basic properties of this energy. In particular, we find the minimal value of this energy in the class of all connected graphs on n vertices (n = 1, 2, ...). Besides, we consider the class of all connected graphs whose Laplacian energy is uniformly bounded by a constant α ⩾ 4, and completely describe this class in the case α = 40.     

An improvement of fraisse's sufficient condition for hamiltonian graphs

Let G be a k-connected graph of order n. For an independent set c, let d(S) be the number of vertices adjacent to at least one vertex of S and > let i(S) be the number of vertices adjacent to at least |S| vertices of S. We prove that if there exists some s, 1 ≤ s ≤ k, such that Σ_xiEX d(X\{X_i}) > s(n?1) – k[s/2] – i(X)[(s?1)/2] holds for every independetn set X ={x₀, x₁ ?x_s} of s + 1 vertices, then G is hamiltonian. Several known results, including Fraisse's sufficient condition for hamiltonian graphs, are dervied as corollaries.     

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.     

Regular Steinhaus graphs of odd degree

A Steinhaus matrix is a binary square matrix of size n which is symmetric, with a diagonal of zeros, and whose upper-triangular coefficients satisfy a_i,j=a_i−1,j−1+a_i−1,j for all 2?i<j?n. Steinhaus matrices are determined by their first row. A Steinhaus graph is a simple graph whose adjacency matrix is a Steinhaus matrix. We give a short new proof of a theorem, due to Dymacek, which states that even Steinhaus graphs, i.e. those with all vertex degrees even, have doubly-symmetric Steinhaus matrices. In 1979 Dymacek conjectured that the complete graph on two vertices K₂ is the only regular Steinhaus graph of odd degree. Using Dymacek’s theorem, we prove that if (a_i,j)_1?i,j?n is a Steinhaus matrix associated with a regular Steinhaus graph of odd degree then its sub-matrix (a_i,j)_2?i,j?n−1 is a multi-symmetric matrix, that is a doubly-symmetric matrix where each row of its upper-triangular part is a symmetric sequence. We prove that the multi-symmetric Steinhaus matrices of size n whose Steinhaus graphs are regular modulo 4, i.e. where all vertex degrees are equal modulo 4, only depend on parameters for all even numbers n, and on parameters in the odd case. This result permits us to verify Dymacek’s conjecture up to 1500 vertices in the odd case.