Publication

Expanding graphs, Ramanujan graphs, and 1-factor perturbations

Antoine Musitelli
2006
Journal Articles

Abstract

We construct (k±1)-regular graphs which provide sequences of expanders by adding or substracting appropriate 1- factors from given sequences of k- regular graphs. We compute numerical examples in a few cases for which the given sequences are from the work of Lubotzky, Phillips, and Sarnak (with k − 1 the order of a finite field). If k + 1 = 7, our construction results in a sequence of 7- regular expanders with all spectral gaps at least 6−2√5 ≈ 1.52; the corresponding minoration for a sequence of Ramanujan 7- regular graphs (which is not known to exist) would be 7 − 2√6 ≈ 2.10.

Official source

https://infoscience.epfl.ch/entities/publication/9357b184-f09b-4b08-ae75-b6c66c581801

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Antoine Musitelli
2006
Journal Articles

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/9357b184-f09b-4b08-ae75-b6c66c581801

About this result

Related concepts (32)

Expander graph

In graph theory, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion. Expander constructions have spawned research in pure and applied mathematics, with several applications to complexity theory, design of robust computer networks, and the theory of error-correcting codes. Intuitively, an expander graph is a finite, undirected multigraph in which every subset of the vertices that is not "too large" has a "large" boundary.

Spectral graph theory

In mathematics, spectral graph theory is the study of the properties of a graph in relationship to the characteristic polynomial, eigenvalues, and eigenvectors of matrices associated with the graph, such as its adjacency matrix or Laplacian matrix. The adjacency matrix of a simple undirected graph is a real symmetric matrix and is therefore orthogonally diagonalizable; its eigenvalues are real algebraic integers. While the adjacency matrix depends on the vertex labeling, its spectrum is a graph invariant, although not a complete one.

Regular graph

In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each internal vertex are equal to each other. A regular graph with vertices of degree k is called a k‐regular graph or regular graph of degree k. Also, from the handshaking lemma, a regular graph contains an even number of vertices with odd degree.

Related publications (4)

Expanding graphs, Ramanujan graphs, and 1-factor perturbations

Chat with Graph Search

Isogeometric Analysis And Proper Orthogonal Decomposition For The Acoustic Wave Equation

Reconstruction of Images from Gabor Graphs with Applications in Facial Image Processing

On the inapproximability of independent domination in 2P3-free perfect graphs