A Characterization for the Existence of Connected \(f\)-Factors of \(\textit{ Large}\) Minimum Degree

It is well known that when \(f(v)\) is a constant for each vertex \(v\), the connected \(f\)-factor problem is NP-Complete. In this note we consider the case when \(f(v) \geq \lceil \frac{n}{2.5}\rceil\) for each vertex \(v\), where \(n\) is the number of vertices. We present a diameter based charac...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2016-01
Main Authors: Narayanaswamy, N S, Rahul, C S
Format: Article
Language:English
Subjects:
Algorithms
Apexes
Graph algorithms
Polynomials
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:It is well known that when \(f(v)\) is a constant for each vertex \(v\), the connected \(f\)-factor problem is NP-Complete. In this note we consider the case when \(f(v) \geq \lceil \frac{n}{2.5}\rceil\) for each vertex \(v\), where \(n\) is the number of vertices. We present a diameter based characterization of graphs having a connected \(f\)-factor (for such \(f\)). We show that if a graph \(G\) has a connected \(f\)-factor and an \(f\)-factor with 2 connected components, then it has a connected \(f\)-factor of diameter at least 3. This result yields a polynomial time algorithm which first executes the Tutte's \(f\)-factor algorithm, and if the output has 2 connected components, our algorithm searches for a connected \(f\)-factor of diameter at least 3.
ISSN:2331-8422