Département de Mathématiques et d'Informatique, Université de Perpignan via Domitia, 52 Avenue Paul Alduy, 66100 Perpignan, France; firstname.lastname@example.org
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)
Mathematics Subject Classification: