Toughness and Matching Extension in Graphs,

Abstract

In the present paper, we wish to treat some relationships between toughness of a graph and the n-extendability of the graph. We will prove two results. The first says essentially that if a graph has sufficiently high toughness (and has an even number of points) then it must be n-extendable. The second result applies to graphs with toughness less than one and presents an upper bound on the value of n for which such a graph can be n-extendable. In the final section, we compare and contrast these results with the n-factor results of Enomoto, Jackson, Katerinis and A. Saito.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 1986
Accession Number
ADA169177

Entities

People

  • M. D. Plummer

Organizations

  • Vanderbilt University

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Continents
  • Contracts
  • Contrast
  • Decomposition
  • Geographic Regions
  • Graph Theory
  • Mathematics
  • Michigan
  • New York
  • North America
  • Tennessee
  • Toughness
  • United States

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.
  • Materials Science (Mechanical Engineering).