Accession Number : ADA254639


Title :   2-Extendability in Two Classes of Claw-Free Graphs


Corporate Author : VANDERBILT UNIV NASHVILLE TN DEPT OF MATHEMATICS


Personal Author(s) : Plummer, Michael D


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a254639.pdf


Report Date : Jan 1992


Pagination or Media Count : 19


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.


Descriptors :   *GRAPHS , EDGES , MATCHING , PAPER


Subject Categories : Numerical Mathematics


Distribution Statement : APPROVED FOR PUBLIC RELEASE