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; firstname.lastname@example.org
Accepted: 1 August 2007
We design a O(n3) polynomial time algorithm for finding a (k-1)- regular subgraph in a k-regular graph without any induced star K1,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 K1,3 (k even, k ≥ 6), not containing any (k-1)-regular subgraph is also constructed.
Mathematics Subject Classification: 05C
Key words: Polynomial time algorithm / NP-complete / graph / star / regular graph / perfect marching.
© EDP Sciences, ROADEF, SMAI, 2008