Bounds on separated pairs of subgraphs, eigenvalues and related polynomials

Research output: Book/ReportReport

267 Downloads (Pure)

Abstract

We give a bound on the sizes of two sets of vertices at a given minimum distance (a separated pair of subgraphs) in a graph in terms of polynomials and the spectrum of the graph. We find properties of the polynomial optimizing the bound. Explicit bounds on the number of vertices at maximal distance and distance two from a given vertex, and on the size of two equally large sets at maximal distance are given, and we find graphs for which the bounds are tight.
Original languageEnglish
PublisherUnknown Publisher
Number of pages10
VolumeFEW 699
Publication statusPublished - 1995

Publication series

NameResearch memorandum / Tilburg University, Faculty of Economics and Business Administration
VolumeFEW 699

Keywords

  • Graphs
  • Eigenvalues
  • Polynomials
  • mathematics

Fingerprint Dive into the research topics of 'Bounds on separated pairs of subgraphs, eigenvalues and related polynomials'. Together they form a unique fingerprint.

Cite this