Eigenvalues and separation in graphs
type: Item
instance of: scholarly article
title: Eigenvalues and separation in graphs
zbMATH Open document ID: 0771.05062
DOI: 10.1016/0024-3795(93)90030-R
author: Z. Miller
author: Dan Pritikin
published in: Linear Algebra and its Applications
publication date: 1993-05-16T00:00:00Z
review text: If \(f:V(G)\to V(H)\) is a one-to-one map of graphs \(G\) and \(H\), where \(| G|\leq| H|\), then \(\text{sep}(G,H)=\max\min\{\text{dist}_ H(f(x),f(y)):xy\in E(G)\}\) where the maximum is over all such functions \(f\). The study of \(\text{sep}(G,H)\) is an extension of problems arising in coding theory, for example. The authors apply a method involving the Kronecker product to obtain the eigenvalues of powers of the \(n\)-cube \(Q(n)\) and of powers of the discrete torus \(C_ n\times C_ n\). They obtain, among other things, functions \(s(k,p)\) and \(t(k,p)\) such that if \(G\) is a graph with \(p\) points and \(q\) edges, where \(q>s(k,p)\) or \(q>t(k,p)\), then \(\text{sep}(G,Q(n))\leq k\) or \(\text{sep}(G,C_ n\times C_ n)\leq k\).
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 05C12
zbMATH DE Number: 167840
zbMATH Keywords: separation
zbMATH Keywords: edge-isoperimetric problem
zbMATH Keywords: map
zbMATH Keywords: eigenvalues
zbMATH Keywords: discrete torus
reviewed by: J. W. Moon
MaRDI profile type: Publication
cites work: \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
cites work: Q4173399
cites work: Q3907599
cites work: Relations between packing and covering numbers of a tree
cites work: On the separation number of a graph
Recommended article: Q4866083
Recommended article: Q4661928
Recommended article: Eigenvalues of finite graphs
Recommended article: Q3435575
Recommended article: Eigenvalues, Multiplicities and Graphs
Recommended article: Q4886769
Recommended article: Eigenvalues and degree deviation in graphs
Recommended article: Eigenvalues and the degree sequences of graphs
Recommended article: On graphs with distinct eigenvalues
Recommended article: Vertex-connectivity and eigenvalues of graphs
description: scientific article; zbMATH DE number 167840