# Polynomial time algorithms for two classes of subgraph problem

RAIRO - Operations Research (2008)

- Volume: 42, Issue: 3, page 291-298
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topSridharan, Sriraman. "Polynomial time algorithms for two classes of subgraph problem." RAIRO - Operations Research 42.3 (2008): 291-298. <http://eudml.org/doc/250400>.

@article{Sridharan2008,

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 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.
},

author = {Sridharan, Sriraman},

journal = {RAIRO - Operations Research},

keywords = {Polynomial time algorithm; NP-complete; graph; star; regular graph; perfect marching.; polynomial time algorithm; perfect matching},

language = {eng},

month = {8},

number = {3},

pages = {291-298},

publisher = {EDP Sciences},

title = {Polynomial time algorithms for two classes of subgraph problem},

url = {http://eudml.org/doc/250400},

volume = {42},

year = {2008},

}

TY - JOUR

AU - Sridharan, Sriraman

TI - Polynomial time algorithms for two classes of subgraph problem

JO - RAIRO - Operations Research

DA - 2008/8//

PB - EDP Sciences

VL - 42

IS - 3

SP - 291

EP - 298

AB -
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.

LA - eng

KW - Polynomial time algorithm; NP-complete; graph; star; regular graph; perfect marching.; polynomial time algorithm; perfect matching

UR - http://eudml.org/doc/250400

ER -

## References

top- A.V. Aho, J.E. Hopcroft and J.D. Ullman, Data structures and algorithms, Addison-Wesley, Reading, Mass (1983). Zbl0487.68005
- C. Berge, Graphes, Gauthier-Villars, Paris (1983).
- J.A. Bondy and U.S.R. Murty, Graph Theory and Applications, Macmillan, London (1978). Zbl1134.05001
- V. Chvàtal, H. Fleishner, J. Sheehan and C. Thomassen, Three-regular subgraphs of four regular graphs. J. Graph Theor. 3 (1979) 371–386. Zbl0427.05055
- J. Edmonds, Paths, trees and flowers. Can. J. Math.17 (1965) 449–467. Zbl0132.20903
- M.R. Garey and D.S. Johnson, Computers and Intractability: A guide to the theory of NP-Completeness, W.H. Freeman and company, NY (1979). Zbl0411.68039
- M. Las Vergnas, A note on matchings in graphs. Cahiers du Centre d'Etudes de Recherche Opérationnelle17 (1975) 257–260. Zbl0315.05123
- K.R. Parthasarathy and Sriraman Sridharan, On a generalization of Berge-Sauer conjecture, Combinatorics and Applications, edited by K.S. Vijayan and N.M. Singhi, Indian Stat. Institute, Calcutta (1982) 261–264.
- Sriraman Sridharan, A note on regular subgraphs of regular graphs. J. Math. Phys. Sci.28 (5) (1994) 237–241. Zbl0837.05098
- V.A. Tashkinov, Regular subgraphs of regular graphs. Soviet. Math. Dokl. Vol. 26 (1982). Zbl0512.05056
- W.T. Tutte, The factorization of linear graphs. J. London Math. Soc.22 (1947) 107–111. Zbl0029.23301

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.