Bounds on separated pairs of subgraphs, eigenvalues and related polynomials

Research output: Book/ReportReportProfessional

211 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

Fingerprint

Subgraph
Eigenvalue
Polynomial
Graph in graph theory
Explicit Bounds
Minimum Distance
Large Set
Vertex of a graph

Keywords

  • Graphs
  • Eigenvalues
  • Polynomials
  • mathematics

Cite this

van Dam, E. R. (1995). Bounds on separated pairs of subgraphs, eigenvalues and related polynomials. (Research memorandum / Tilburg University, Faculty of Economics and Business Administration; Vol. FEW 699). Unknown Publisher.
van Dam, E.R. / Bounds on separated pairs of subgraphs, eigenvalues and related polynomials. Unknown Publisher, 1995. 10 p. (Research memorandum / Tilburg University, Faculty of Economics and Business Administration).
@book{b667448d47974d2799295606fae4b166,
title = "Bounds on separated pairs of subgraphs, eigenvalues and related polynomials",
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.",
keywords = "Graphs, Eigenvalues, Polynomials, mathematics",
author = "{van Dam}, E.R.",
note = "Pagination: 10",
year = "1995",
language = "English",
volume = "FEW 699",
series = "Research memorandum / Tilburg University, Faculty of Economics and Business Administration",
publisher = "Unknown Publisher",

}

van Dam, ER 1995, Bounds on separated pairs of subgraphs, eigenvalues and related polynomials. Research memorandum / Tilburg University, Faculty of Economics and Business Administration, vol. FEW 699, vol. FEW 699, Unknown Publisher.

Bounds on separated pairs of subgraphs, eigenvalues and related polynomials. / van Dam, E.R.

Unknown Publisher, 1995. 10 p. (Research memorandum / Tilburg University, Faculty of Economics and Business Administration; Vol. FEW 699).

Research output: Book/ReportReportProfessional

TY - BOOK

T1 - Bounds on separated pairs of subgraphs, eigenvalues and related polynomials

AU - van Dam, E.R.

N1 - Pagination: 10

PY - 1995

Y1 - 1995

N2 - 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.

AB - 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.

KW - Graphs

KW - Eigenvalues

KW - Polynomials

KW - mathematics

M3 - Report

VL - FEW 699

T3 - Research memorandum / Tilburg University, Faculty of Economics and Business Administration

BT - Bounds on separated pairs of subgraphs, eigenvalues and related polynomials

PB - Unknown Publisher

ER -

van Dam ER. Bounds on separated pairs of subgraphs, eigenvalues and related polynomials. Unknown Publisher, 1995. 10 p. (Research memorandum / Tilburg University, Faculty of Economics and Business Administration).