Polynomial time algorithms for two classes of subgraph problem
We design a polynomial time algorithm for finding a -1)- regular subgraph in a -regular graph without any induced star (claw-free). A polynomial time algorithm for finding a cubic subgraph in a 4-regular locally connected graph is also given. A family of -regular graphs with an induced star (, not containing any (-1)-regular subgraph is also constructed.