CFP last date
20 May 2024
Call for Paper
June Edition
IJCA solicits high quality original research papers for the upcoming June edition of the journal. The last date of research paper submission is 20 May 2024

Submit your paper
Know more
The week's pick
Responsive image
Enhancing Privacy Preservation: Multi-Attribute Protection with P-Sensitive K-Anonymity

Twinkle Patel Kiran Amin
Random Articles
Reseach Article

Maximal Triangle Free Graph and Travelling Salesman Problem

by Jayanta Kr Choudhury, Bichitra Kalita
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 85 - Number 17
Year of Publication: 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 },
issue_date = { January 2014 },
volume = { 85 },
number = { 17 },
month = { January },
year = { 2014 },
issn = { 0975-8887 },
pages = { 22-30 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume85/number17/14934-3493/ },
doi = { 10.5120/14934-3493 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T22:02:43.329978+05:30
%A Jayanta Kr Choudhury
%A Bichitra Kalita
%T Maximal Triangle Free Graph and Travelling Salesman Problem
%J International Journal of Computer Applications
%@ 0975-8887
%V 85
%N 17
%P 22-30
%D 2014
%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
  1. Woodall, D. , 1973, "The Binding number of a graph and its Anderson number", J. Combin, Theory B 15, p. p. 225 – 255.
  2. Shi, R. , 1985, "The binding number of a graph and its triangle", Acta Math. Appl. Sinica (English series) 2, pp. 79 – 86.
  3. Goddard, W. , Kleitman, D. J. , 1993, "A note on maximal triangle free graphs", Journal in graph theory, Vol. 17, issue 5, pp. 629 – 631.
  4. Furedi, Z. , Reimer, D. , A'kos Seress, 1991, "Hajnal's triangle-free game and extremal graph problems", Congressus Numerantium 82, p. p. 123 – 128.
  5. Briegmann, D. , Komusiewiccz, C. , Moser, H. , 2009, "On Generating Triangle Free Graph", Proc. AGT.
  6. Brandt, S. , Brinkmann, G. and Harmuth, T. , (2000), "The Generator of Maximal Triangle Free Graph", Graph & combinatorics 16: 149-157.
  7. Kalita, B. , 2005, "Some Investigation on Graph Theory, PhD thesis". Finance India. Vol. XIX, NO-4DEC (P. P. 1430-1438).
  8. Kalita, B. , 2003, "Application of three edges extension of planar (TEEP) graph for the Solution of traveling salesman problem" Proc. 48th ISTAM conference.
  9. Kalita, B. , 2003, "Non-isomorphic Hamiltonian Sub-Graphs of complete graph and their application" Proc. Indian Sc. Congress, Ahmedabad.
  10. Kalita, B. , 2006, "Sub Graph of Complete Graph" Proceeding, International Conference on Foundation of computer Science. Lasvegas, U. S. A. p. p. 71-77.
  11. 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.
  12. 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.
  13. 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.
  14. 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

Computer Science
Information Sciences

Keywords

Algorithm Maximal Triangle Free Graph (MTFG) Complete Graph Hamiltonian Graphs Traveling Salesman Problem (TSP).

Powered by PhDFocusTM