Polynomial time algorithms for two classes of subgraph problem

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

Received: 14 June 2006
Accepted: 1 August 2007

Abstract

We design a O(n³) 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.