Search

In this paper, we discuss various connections between the smallest eigenvalue of the adjacency matrix of a graph and its structure. There are several techniques for obtaining upper bounds on the smallest eigenvalue, and some of them are based on Rayleigh quotients, Cauchy interlacing using induced subgraphs, and Haemers interlacing with vertex partitions and quotient matrices. In this paper, we are interested in obtaining lower bounds for the smallest eigenvalue. Motivated by results on line graphs and generalized line graphs, we show how graph decompositions can be used to obtain such lower bounds.

Given a graph G on n vertices, for which m is it possible to partition the edge set of the m-fold complete graph mKn into copies of G? We show that there is an integer m0, which we call the partition modulus of G, such that the set M(G) of values of m for which such a partition exists consists of all but finitely many multiples of m0. Trivial divisibility conditions derived from G give an integer m1 that divides m0; we call the quotient m0/m1 the partition index of G. It seems that most graphs G have partition index equal to 1, but we give two infinite families of graphs for which this is not true. We also compute M(G) for various graphs and outline some connections between our problem and the existence of designs of various types. [ABSTRACT FROM AUTHOR]

In 1995, Brouwer proved that the toughness of a connected k-regular graph G is at least k/λ-2, where λ is the maximum absolute value of the non-trivial eigenvalues of G. Brouwer conjectured that one can improve this lower bound to k/λ-1 and that many graphs (especially graphs attaining equality in the Hoffman ratio bound for the independence number) have toughness equal to k/λ. In this paper, we improve Brouwer's spectral bound when the toughness is small and we determine the exact value of the toughness for many strongly regular graphs attaining equality in the Hoffman ratio bound such as Lattice graphs, Triangular graphs, complements of Triangular graphs and complements of point-graphs of generalized quadrangles. For all these graphs with the exception of the Petersen graph, we confirm Brouwer's intuition by showing that the toughness equals k/(-λmin), where λmin is the smallest eigenvalue of the adjacency matrix of the graph. [ABSTRACT FROM AUTHOR]

An r-cut of the complete r-uniform hypergraph Krn is obtained by partitioning its vertex set into r parts and taking all edges that meet every part in exactly one vertex. In other words it is the edge set of a spanning complete r-partite subhypergraph of Krn. An r-cut cover is a collection of r-cuts such that each edge of Krn is in at least one of the cuts. While in the graph case r = 2 any 2-cut cover on average covers each edge at least 2-o(1) times, when r is odd we exhibit an r-cut cover in which each edge is covered exactly once. When r is even no such decomposition can exist, but we can bound the average number of times an edge is cut in an r-cut cover between $1+\frac1{r+1}$ and $1+\frac{1+o(1)}{\log r}$. The upper bound construction can be reformulated in terms of a natural polyhedral problem or as a probability problem, and we solve the latter asymptotically. [ABSTRACT FROM AUTHOR]

In this paper, we study the relationship between eigenvalues and the existence of certain subgraphs in regular graphs. We give a condition on an appropriate eigenvalue that guarantees a lower bound for the matching number of a t-edge-connected d-regular graph when t ≤ d - 2. This work extends some classical results of von Baebler [Comment. Math. Helv., 10 (1937), pp. 275-287] and Berge [Théorie des Graphes et Ses Applications, Collection Universitaire de Mathematiques II, Dunod, Paris, 1958] and more recent work of Cioab ă, Gregory, and Haemers [J. Combin. Theory Ser. B, 99 (2009), pp. 287-297]. We also study the relationships between the eigenvalues of a d-regular t-edge-connected graph G and the maximum number of pairwise disjoint connected subgraphs in G that are each joined to the rest of the graph by exactly t edges. [ABSTRACT FROM AUTHOR]