RAIRO - Operations Research

Table of Contents - July 2008 - Volume 42, Issue 03  

Research Article

Polynomial time algorithms for two classes of subgraph problem

Sriraman Sridharan

Département de Mathématiques et d'Informatique, Université de Perpignan via Domitia, 52 Avenue Paul Alduy, 66100 Perpignan, France; sriraman@univ-perp.fr

Abstract

We design a O(n3) polynomial time algorithm for finding a (k-1)- regular subgraph in a k-regular graph without any induced star K 1,3(claw-free). A polynomial time algorithm for finding a cubic subgraph in a 4-regular locally connected graph is also given. A family of k-regular graphs with an induced star K 1,3 (k even, k ≥ 6), not containing any (k-1)-regular subgraph is also constructed.

(Received June 14 2006)

(Accepted August 1 2007)

(Online publication August 20 2008)

Key Words:

  • Polynomial time algorithm;
  • NP-complete;
  • graph;
  • star;
  • regular graph;
  • perfect marching.

Mathematics Subject Classification:

  • 05C