Matching Extension and the Genus of a Graph,

Abstract

Let G be a graph with p points having a perfect matching and suppose n is a positive integer with n < or = (p-2)/2. Then G is n-extendable if every matching in G containing n lines is a subset of a perfect matching. In this paper we obtain an upper bound on the n-extendability of a graph in terms of its genus. Keywords: Euler contributions; Theorems. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1986
Accession Number
ADA166562

Entities

People

  • Michael D. Plummer

Organizations

  • Vanderbilt University

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Boundaries
  • Continents
  • Equations
  • Geographic Regions
  • Graph Theory
  • Inequalities
  • Linear Programming
  • Mathematics
  • New York
  • New Zealand
  • North America
  • Orientation (Direction)
  • Tennessee
  • Triangles
  • United States
  • Universities

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.