Extending Matchings in Planar Graphs 4

Abstract

The structure of certain non-2-extendable planar graphs is studied first. In particular, 4-connected 5-regular planar graphs which are not 2-extendable are investigated and examples of these are presented. It is then proved that all 5-connected even planar graphs are 2-extendable. Finally, a certain configuration called a generalized butterfly is defined and it is shown that 4-connected maximal planar even graphs which contain no generalized butterfly are 2-extendable.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1989
Accession Number
ADA210315

Entities

People

  • Michael D. Plummer

Organizations

  • Vanderbilt University

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Attachment
  • Boundaries
  • Graph Theory
  • Inequalities
  • Joining
  • Lepidoptera
  • Mathematics
  • Symmetry
  • Triangles

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.