Journal of the Korean Society for Industrial and Applied Mathematics
( Vol.11 NO.4 / 2007 )



Title 


Applications of Graph Theory(ENG) 


Author 


S. Pirzada ,Ashay Dharwadker 


MSC 





Publication 





Page 


1938 Page 


Abstract 


1. The CantorSchroderBernstein Theorem
2. Fermat's(litte) Theorem
3. The NielsonSchreier Theroem
4. The Snp Assembly Problem
5. Computer Network Security
6. The Timetabling Problem
7. Map Coloring and Gsm Mobile Phone Networks
8. Knight's Tours 


Own Status 





Keyword 





Note 





Summary 


Graph theory is becoming increasingly significant as it is applied
to other areas of mathematics, science and technology. It is being
actively used in fields as varied as biochemistry (genomics),
electrical engineering (communication networks and coding theory),
computer science (algorithms and computation) and operations
research (scheduling). The powerful combinatorial methods found in
graph theory have also been used to prove fundamental results in
other areas of pure mathematics. This paper, besides giving a
general outlook of these facts, includes new graph theoretical
proofs of Fermat's Little Theorem and the NielsonSchreier Theorem.
New applications to DNA sequencing (the SNP assemble problem) and
computer network security (worm propagation) using minimum vertex
covers in graphs are discussed. We also show how to apply edge
coloring and matching in graphs for scheduling (the timetabling
problem) and vertex coloring in graphs for map coloring and the
assignment of frequencies in GSM mobile phone networks. Finally, we
revisit the classical problem of finding reentrant knight's tours
on a chessboard using Hamiltonian circuits in graphs. 


Attach 


[PDF] 



