Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649743 | Discrete Mathematics | 2009 | 10 Pages |
Abstract
Let G=(V,E) be a graph and let f be a function f:VâN. A partial f-factor of G is a subgraph H of G, such that the degree in H of every vertex vâV is at most f(v). We study here the recognition problem of graphs, where all maximal partial f-factors have the same number of edges. Graphs which satisfy that property for the function f(v)â¡1 are known as equimatchable and their recognition problem is the subject of several previous articles in the literature. We show the problem is polynomially solvable if the function f is bounded by a constant, and provide a structural characterization for graphs with girth at least 5 in which all maximal partial 2-factors are of the same size.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
David Tankus, Michael Tarsi,