Research Article
Maximal Triangle Free Graph and Travelling Salesman Problem
|
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
| Volume 85 - Issue 17 |
| Published: January 2014 |
| Authors: Jayanta Kr Choudhury, Bichitra Kalita |
10.5120/14934-3493
|
Jayanta Kr Choudhury, Bichitra Kalita . Maximal Triangle Free Graph and Travelling Salesman Problem. International Journal of Computer Applications. 85, 17 (January 2014), 22-30. DOI=10.5120/14934-3493
@article{ 10.5120/14934-3493,
author = { Jayanta Kr Choudhury,Bichitra Kalita },
title = { Maximal Triangle Free Graph and Travelling Salesman Problem },
journal = { International Journal of Computer Applications },
year = { 2014 },
volume = { 85 },
number = { 17 },
pages = { 22-30 },
doi = { 10.5120/14934-3493 },
publisher = { Foundation of Computer Science (FCS), NY, USA }
}
%0 Journal Article
%D 2014
%A Jayanta Kr Choudhury
%A Bichitra Kalita
%T Maximal Triangle Free Graph and Travelling Salesman Problem%T
%J International Journal of Computer Applications
%V 85
%N 17
%P 22-30
%R 10.5120/14934-3493
%I Foundation of Computer Science (FCS), NY, USA
Abstract
In this paper, a maximal triangle free graph has been generated from the complete graph K_(2m+3) for m?2 by deleting (m^2+3m+1) number of edges. In addition, two theorems have been established for it. Finally, an algorithm has been developed under different cases to solve the traveling salesman problem when the weights of the edges are non-repeated of the complete graph K_(2m+3) for m?2.
References
- Woodall, D. , 1973, "The Binding number of a graph and its Anderson number", J. Combin, Theory B 15, p. p. 225 – 255.
- Shi, R. , 1985, "The binding number of a graph and its triangle", Acta Math. Appl. Sinica (English series) 2, pp. 79 – 86.
- Goddard, W. , Kleitman, D. J. , 1993, "A note on maximal triangle free graphs", Journal in graph theory, Vol. 17, issue 5, pp. 629 – 631.
- Furedi, Z. , Reimer, D. , A'kos Seress, 1991, "Hajnal's triangle-free game and extremal graph problems", Congressus Numerantium 82, p. p. 123 – 128.
- Briegmann, D. , Komusiewiccz, C. , Moser, H. , 2009, "On Generating Triangle Free Graph", Proc. AGT.
- Brandt, S. , Brinkmann, G. and Harmuth, T. , (2000), "The Generator of Maximal Triangle Free Graph", Graph & combinatorics 16: 149-157.
- Kalita, B. , 2005, "Some Investigation on Graph Theory, PhD thesis". Finance India. Vol. XIX, NO-4DEC (P. P. 1430-1438).
- Kalita, B. , 2003, "Application of three edges extension of planar (TEEP) graph for the Solution of traveling salesman problem" Proc. 48th ISTAM conference.
- Kalita, B. , 2003, "Non-isomorphic Hamiltonian Sub-Graphs of complete graph and their application" Proc. Indian Sc. Congress, Ahmedabad.
- Kalita, B. , 2006, "Sub Graph of Complete Graph" Proceeding, International Conference on Foundation of computer Science. Lasvegas, U. S. A. p. p. 71-77.
- Dutta. Anupam, Kalita. B. , Baruah. H. K. , 2010, "Regular sub-graph of complete graph" International Journal of Applied Engineering Research. Vol. 5. No-8, p. p. 1315-1323.
- Dutta. A, Kalita. B, Baruah. H. K. , (2010), "Regular Planar Sub-Graphs of Complete Graph and Their Application", IJAER, Vol-5 no-3, p. p. 377-386.
- Choudhury, J. K. , Kalita, B. , 2011, "An Algorithm for TSP" Bulletin of Pure and Applied Sciences, Vol 30 E (Math &Stat. ) Issue (No. 1), p. p. 111-118.
- Choudhury, J. K. , Dutta, A, Kalita,B. , 2012, "Graph Factorization and Its Application", International Journals of Multidisciplinary Research Academy, Vol 2, Issue-3, p. p. 208-220.
Index Terms
Keywords