2-Extendability in Two Classes of Claw-Free Graphs

Abstract

A graph G is 2-extendable if it has at least six vertices and every pair of independent edges extends to (i.e., is a subset of) a perfect matching. In this paper two classes of claw-free graphs are discussed: those which are 3- regular and 3-connected and those which are 4-regular and 4-connected (as well as even). None of the first class is 2-extendable, whereas those of the second class which are 2-extendable are determined. More particularly in the graphs belonging to these classes, those pairs of independent edges which extend to a perfect matching are determined.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1992
Accession Number
ADA254639

Entities

People

  • Michael D. Plummer

Organizations

  • Vanderbilt University

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Attachment
  • Contracts
  • Graph Theory
  • Joining
  • Lepidoptera
  • Mathematics
  • Observation
  • Symmetry
  • Tennessee
  • Triangles
  • Universities

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.