Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-23T10:53:57.513Z Has data issue: false hasContentIssue false
  • English
  • Français

Polynomial time algorithms for two classes of subgraph problem

Published online by Cambridge University Press:  20 August 2008

Sriraman Sridharan
Sriraman Sridharan*
Affiliation:
Département de Mathématiques et d'Informatique, Université de Perpignan via Domitia, 52 Avenue Paul Alduy, 66100 Perpignan, France; [email protected]
Get access

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

Keywords

Polynomial time algorithmNP-completegraphstarregular graphperfect marching.
Type
Research Article
Information
RAIRO - Operations Research , Volume 42 , Issue 3 , July 2008 , pp. 291 - 298
Copyright
© EDP Sciences, ROADEF, SMAI, 2008

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

A.V. Aho, J.E. Hopcroft and J.D. Ullman, Data structures and algorithms, Addison-Wesley, Reading, Mass (1983).
C. Berge, Graphes, Gauthier-Villars, Paris (1983).
J.A. Bondy and U.S.R. Murty, Graph Theory and Applications, Macmillan, London (1978).
V. Chvàtal, H. Fleishner, J. Sheehan and C. Thomassen, Three-regular subgraphs of four regular graphs. J. Graph Theor. 3 (1979) 371–386.
Edmonds, J., Paths, trees and flowers. Can. J. Math. 17 (1965) 449–467. CrossRef
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).
Las Vergnas, M., A note on matchings in graphs. Cahiers du Centre d'Etudes de Recherche Opérationnelle 17 (1975) 257–260.
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.
V.A. Tashkinov, Regular subgraphs of regular graphs. Soviet. Math. Dokl. Vol. 26 (1982).
Tutte, W.T., The factorization of linear graphs. J. London Math. Soc. 22 (1947) 107–111. CrossRef