International Journal of Applied Engineering Research
  • Year: 2010
  • Volume: 5
  • Issue: 8

Regular sub-graph of Complete Graph

  • Author:
  • Anupam Dutta1, Bichitra Kalita2, Hemanta K. Baruah3
  • Total Page Count: 9
  • Page Number: 1315 to 1323

1Patidarrang College, Muktapur, P.O. Loch, Kamrup, Assam, India.

2Department of computer application, Assam Engineering College, Guwahati-13, Assam, India.

3Department of Statistics, Gauhati University, Guwahati-14, Assam, India.

AMS-Sub-classification: 05c30, 05c45, 05c62, 05c83 (MSC 2000).

Abstract

For the complete graph k2m+2 for m≥2, we study Hamiltonian circuits and edge disjoint Hamiltonian circuits of various type of regular sub-graph of the complete graph K2m+2. We have been studied the perfect matching of these types of regular sub-graph of various degrees. Finally, we have established an algorithm to solve the traveling salesman problem when the weights of the edges are non-repeated of the complete graph K2m+2 for m≥2 for symmetrical problems.

Keywords

Regular graph, edge disjoints Hamiltonian circuit, the traveling salesman problem, and floor value