May 27, 2016
In this paper, we give some bounds for principal eigenvector and spectral radius of connected uniform hypergraphs in terms of vertex degrees, the diameter, and the number of vertices and edges.
December 14, 2016
Let $H$ be an induced subgraph of the hypercube $Q_k$, for some $k$. We show that for some $c = c(H)$, the vertices of $Q_n$ can be partitioned into induced copies of $H$ and a remainder of at most $O(n^c)$ vertices. We also show that the error term cannot be replaced by anything smaller than $\log n$.
August 7, 2013
This paper gives a tight upper bound on the spectral radius of the signless Laplacian of graphs of given order and clique number. More precisely, let G be a graph of order n, let A be its adjacency matrix, and let D be the diagonal matrix of the row-sums of A. If G has clique number r, then the largest eigenvalue q(G) of the matrix Q=A+D satisfies q(G)<= 2(1-1/r)n. If G is a complete regular r-partite graph, then equality holds in the above inequality. This result confirms ...
May 30, 2019
Let $L(G)$ denote the maximum number of leaves in any spanning tree of a connected graph $G$. We show the (known) result that for the $n$-cube $Q_n$, $L(Q_n) \sim 2^n = |V(Q_n)|$ as $n\rightarrow \infty$. Examining this more carefully, consider the minimum size of a connected dominating set of vertices $\gamma_c(Q_n)$, which is $2^n-L(Q_n)$ for $n\ge2$. We show that $\gamma_c(Q_n)\sim 2^n/n$. We use Hamming codes and an "expansion" method to construct leafy spanning trees in ...
August 8, 2006
Let F(G) be a fixed linear combination of the k extremal eigenvalues of a graph G and of its complement. The problem of finding max{F(G):v(G)=n} generalizes a number of problems raised previously in the literature. We show that the limit max{F(G):v(G)=n}/n exists when n tends to infinity. We also answer a question of Gernert about the sum of the two maximal eigenvalues of a graph.
January 14, 2016
Eigenvectors of large matrices (and graphs) play an essential role in combinatorics and theoretical computer science. The goal of this survey is to provide an up-to-date account on properties of eigenvectors when the matrix (or graph) is random.
January 6, 2010
The d-dimensional Hamming torus is the graph whose vertices are all of the integer points inside an a_1 n X a_2 n X ... X a_d n box in R^d (for constants a_1, ..., a_d > 0), and whose edges connect all vertices within Hamming distance one. We study the size of the largest connected component of the subgraph generated by independently removing each vertex of the Hamming torus with probability 1-p. We show that if p=\lambda / n, then there exists \lambda_c > 0, which is the pos...
October 23, 2020
The $k^{\text{th}}$ power of a graph $G=(V,E)$, $G^k$, is the graph whose vertex set is $V$ and in which two distinct vertices are adjacent if and only if their distance in $G$ is at most $k$. This article proves various eigenvalue bounds for the independence number and chromatic number of $G^k$ which purely depend on the spectrum of $G$, together with a method to optimize them. Our bounds for the $k$-independence number also work for its quantum counterpart, which is not kno...
February 22, 2021
In this work we present a survey of results on the problem of finding the minimum cardinality of the support of eigenfunctions of graphs.
August 20, 2013
This paper gives tight upper bound on the largest eigenvalue q(G) of the signless Laplacian of graphs with no paths of given order. The main ingredient of our proof is a stability result of its own interest, about graphs with large minimum degree and with no long paths. This result extends previous work of Ali and Staton.