no. 3
Polynomial time algorithms for two classes of subgraph problem
RAIRO - Operations Research - Recherche Opérationnelle, Tome 42 (2008) no. 3, pp. 291-298

We design a O(n 3 ) 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 (keven,k≥6), not containing any (k-1)-regular subgraph is also constructed.

DOI : 10.1051/ro:2008015
Classification : 05C
Keywords: polynomial time algorithm, NP-complete, graph, star, regular graph, perfect marching 
@article{RO_2008__42_3_291_0,
     author = {Sridharan, Sriraman},
     title = {Polynomial time algorithms for two classes of subgraph problem},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {291--298},
     year = {2008},
     publisher = {EDP Sciences},
     volume = {42},
     number = {3},
     doi = {10.1051/ro:2008015},
     mrnumber = {2444488},
     zbl = {1161.05344},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro:2008015/}
}
TY  - JOUR
AU  - Sridharan, Sriraman
TI  - Polynomial time algorithms for two classes of subgraph problem
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2008
SP  - 291
EP  - 298
VL  - 42
IS  - 3
PB  - EDP Sciences
UR  - https://www.numdam.org/articles/10.1051/ro:2008015/
DO  - 10.1051/ro:2008015
LA  - en
ID  - RO_2008__42_3_291_0
ER  - 
%0 Journal Article
%A Sridharan, Sriraman
%T Polynomial time algorithms for two classes of subgraph problem
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2008
%P 291-298
%V 42
%N 3
%I EDP Sciences
%U https://www.numdam.org/articles/10.1051/ro:2008015/
%R 10.1051/ro:2008015
%G en
%F RO_2008__42_3_291_0
Sridharan, Sriraman. Polynomial time algorithms for two classes of subgraph problem. RAIRO - Operations Research - Recherche Opérationnelle, Tome 42 (2008) no. 3, pp. 291-298. doi: 10.1051/ro:2008015

[1] A.V. Aho, J.E. Hopcroft and J.D. Ullman, Data structures and algorithms, Addison-Wesley, Reading, Mass (1983). | Zbl | MR

[2] C. Berge, Graphes, Gauthier-Villars, Paris (1983). | Zbl | MR

[3] J.A. Bondy and U.S.R. Murty, Graph Theory and Applications, Macmillan, London (1978).

[4] V. Chvàtal, H. Fleishner, J. Sheehan and C. Thomassen, Three-regular subgraphs of four regular graphs. J. Graph Theor. 3 (1979) 371-386. | Zbl | MR

[5] J. Edmonds, Paths, trees and flowers. Can. J. Math. 17 (1965) 449-467. | Zbl | MR

[6] 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). | Zbl | MR

[7] M. Las Vergnas, A note on matchings in graphs. Cahiers du Centre d'Etudes de Recherche Opérationnelle 17 (1975) 257-260. | Zbl | MR

[8] 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. | Zbl | MR

[9] Sriraman Sridharan, A note on regular subgraphs of regular graphs. J. Math. Phys. Sci. 28 (5) (1994) 237-241. | Zbl | MR

[10] V.A. Tashkinov, Regular subgraphs of regular graphs. Soviet. Math. Dokl. Vol. 26 (1982). | Zbl

[11] W.T. Tutte, The factorization of linear graphs. J. London Math. Soc. 22 (1947) 107-111. | Zbl | MR

Cité par Sources :