Search or add a thesis

Advanced Search (Beta)
Home > Hamiltonian Properties of Directed Toeplitz Graphs

Hamiltonian Properties of Directed Toeplitz Graphs

Thesis Info

Access Option

External Link

Author

Malik, Shabnam

Supervisor

Tudor Zamfirescu

Program

PhD

Institute

Government College University

City

Lahore

Province

Punjab

Country

Pakistan

Thesis Completing Year

2008

Thesis Completion Status

Completed

Subject

Mathemaics

Language

English

Link

http://prr.hec.gov.pk/jspui/handle/123456789/87

Added

2021-02-17 19:49:13

Modified

2024-03-24 20:25:49

ARI ID

1676726356883

Similar


To determine whether or not a given graph has a hamiltonian cycle is much harder than deciding whether it is Eulerian, and no algorithmically useful characterization of hamiltonian graphs is known, although several necessary conditions and many suf- ficient conditions (see [6]) have been discovered. In fact, it is known that determining whether there are hamiltonian paths or cycles in arbitrary graphs is N P-complete. The interested reader is referred in particular to the surveys of Berge ([5], Chapter 10), Bondy and Murty ([10], Chapters 4 and 9), J. C. Bermond [6], Flandrin, Faudree and Ryj ́ a c ˇ stek [21] and R. Gould [27]. Hamiltonicity in special classes of graphs is a major area of graph theory and a lot of graph theorists have studied it. One special class of graphs whose hamiltonicity has been studied is that of Toeplitz graphs, introduced by van Dal et al. [13] in 1996. This study was continued by C. Heuberger [32] in 2002. The Toeplitz graphs investigated in [13] and [32] were all undirected. We intend to extend here this study to the directed case. A Toeplitz matrix, named after Otto Toeplitz, is a square matrix (n × n) which has constant values along all diagonals parallel to the main diagonal. Thus, Toeplitz matrices are defined by 2n − 1 numbers. Toeplitz matrices have uses in different areas in pure and applied mathematics, and also in computer science. For example, they are closely connected with Fourier series, they often appear when differential or inte- gral equations are discretized, they arise in physical data-processing applications, in viiviii the theories of orthogonal polynomials, stationary processes, and moment problems; see Heinig and Rost [31]. For other references on Toeplitz matrices see [26], [28] and A special case of a Toeplitz matrix is a circulant matrix, where each row is ro- tated one element to the right relative to the preceding row. Circulant matrices and their properties have been studied in [14] and [28]. In numerical analysis circulant matrices are important because they are diagonalized by a discrete Fourier trans- form, and hence linear equations that contain them may be quickly solved using a fast Fourier transform. These matrices are also very useful in digital image processing. A directed or undirected graph whose adjacency matrix is circulant is called cir- culant. Circulant graphs and their properties such as connectivity, hamiltonicity, bipartiteness, planarity and colourability have been studied by several authors (see [8], [11], [15], [25], [35], [38], [41] and [24]). In particular, the conjecture of Boesch and Tindell [8], that all undirected connected circulant graphs are hamiltonian, was proved by Burkard and Sandholzer [11]. A directed or undirected Toeplitz graph is defined by a Toeplitz adjacency matrix. The properties of Toeplitz graphs; such as bipartiteness, planarity and colourability, have been studied in [18], [19], [20]. Hamiltonian properties of undirected Toeplitz graphs have been studied in [13] and [32]. For arbitrary digraphs the hamiltonian path and cycle problems are also very dif- ficult and both are N P-complete (see, e.g. the book [22] by Garey and Johnson). It is worthwhile mentioning that the hamiltonian cycle and path problems are N P- complete even for some special classes of digraphs. Garey, Johnson and Tarjan shows [23] that the problem remains N P-complete even for planar 3-regular digraphs. Some powerful necessary conditions, due to Gutin and Yeo [10], are considered for a digraphix to be hamiltonian. For information on hamiltonian and traceable digraphs, see e.g. the survey [2] and [3] by Bang-Jensen and Gutin, [9] by Bondy, [29] by Gutin and [39] by Volkmann. In this thesis, we investigate the hamiltonicity of directed Toeplitz graphs. The main purpose of this thesis is to offer sufficient conditions for the existence of hamil- tonian paths and cycles in directed Toeplitz graphs, which we will discuss in Chapters 3 and 4. The main diagonal of an (n × n) Toeplitz adjacency matrix will be labeled 0 and it contains only zeros. The n − 1 distinct diagonals above the main diago- nal will be labeled 1, 2, . . . , n − 1 and those under the main diagonal will also be labeled 1, 2, . . . , n − 1. Let s 1 , s 2 , . . . , s k be the upper diagonals containing ones and t 1 , t 2 , . . . , t l be the lower diagonals containing ones, such that 0 < s 1 < s 2 < · · · < s k < n and 0 < t 1 < t 2 < · · · < t l < n. Then, the corresponding di- rected Toeplitz graph will be denoted by T n s 1 , s 2 , . . . , s k ; t 1 , t 2 , . . . , t l . That is, T n s 1 , s 2 , . . . , s k ; t 1 , t 2 , . . . , t l is the graph with vertex set 1, 2, . . . , n, in which the edge (i, j), 1 ≤ i < j ≤ n, occurs if and only if j − i = s p or i − j = t q for some p and q (1 ≤ p ≤ k, 1 ≤ q ≤ l). In Chapter 1 we describe some basic ideas, terminology and results about graphs and digraphs. Further we discuss adjacency matrices, Toeplitz matrices, which we will encounter in the following chapters. In Chapter 2 we discuss hamiltonian graphs and add a brief historical note. We then discuss undirected Toeplitz graph, and finally mention some known results on hamiltonicity of undirected Toeplitz graphs found by van Dal et al. [13] and C. Heuberger [32].x Since all graphs in the main part of the thesis (Chapters 3 and 4) will be directed, we shall omit mentioning it in these chapters. We shall consider here just graphs without loops, because loops play no role in hamiltonicity investigations. Thus, un- less otherwise mentioned, in Chapters 3 and 4, by a graph we always mean a finite simple digraph. In Chapter 3, for k = l = 1 we obtain a characterization of cycles among directed Toeplitz graphs, and another result similar to Theorem 10 in [13]. Directed Toeplitz graphs with s 1 = 1 (or t 1 = 1) are obviously traceable. If we ask moreover that s 2 = 2, we see that the hamiltonicity of T n 1, 2; t 1 depends upon the parity of t 1 and n. Further in the same Chapter, we require s 3 = 3 and succeed to prove the hamiltonicity of T n 1, 2, 3; t 1 for all t 1 and n. In Chapter 4 we present a few results on Toeplitz graphs with s 1 = t 1 = 1 and s 2 = 3. They will often depend upon the parity of n. Chapter 5 contains some concluding remarks.
Loading...
Loading...

Similar Books

Loading...

Similar Chapters

Loading...

Similar News

Loading...

Similar Articles

Loading...

Similar Article Headings

Loading...

5۔ عدالتی انصاف کے حصول میں درپیش مشکلات

اسلامی ریاست میں قوانینِ حدودو قصاص کی تنفیذ کے لیے لازمی ہے کہ عدالت کو اس بات کا پابند کیا جائے کہ عوام کوفوری اور سستے عدل کی سہولت فراہم کی جائے ۔ عدالتی نظام میں فوری اور سستے عدل کی فراہمی بڑی اہمیت کی حامل ہے کیونکہ عدل وانصاف کی فراہمی میں بہت ذیادہ وقت لگنے کے بعد قانون کانفاذ اپنی افادیت کھو بیٹھتا ہے۔ اسی طرح اگر عدل و انصاف کی فراہمی کے لیے بھاری رقم بھی درکار ہو ، تو قانون سازی کا مقصد فوت ہوکر رہ جائے گا۔ لہذا ضروری ہے کہ عدالتیں رعا یا کو فور ی اور سستے انصاف کی فراہمی کو یقینی بنائیں ۔ہمیں عہد نبوی ﷺ اور عہد صحابہ کر ام سے بے شمار مثالیں ملتی ہیں کہ مقدمہ عدالت میں آ جانے کے بعد اس کا فوری فیصلہ کیا جاتا تھا اور اس پر عمل درآمد کروایا جاتا تھا۔ اس کے علاوہ عدلیہ کا انتظامیہ کی بے جا مداخلت سے آزاد ہونا اور سب پر بالادستی ہونا قیام عدل کی لازمی شرط ہے ۔ اسلام کے نظام عدل میں عدالت حاکم وقت سے لے کر عام شہر ی تک ہر ایک کو جواب دہی کے لیے طلب کر سکتی ہے اور قانون کے مطابق سزا بھی دے سکتی ہے اور عدالت کےکام میں انتظامیہ کا کوئی چھوٹا یا بڑا مداخلت کرنے کا کوئی حق نہیں رکھتا۔ یہ قاضی یا جج کی بالا دستی نہیں بلکہ قانون کی بالا دستی ہے جو خود جج یا قاضی پر بھی عائد ہوتی ہے ۔ موجودہ عدالتی نظام اس ضرورت کو پورا نہیں کررہا ، بلکہ اس کا کام تو عوام الناس کے درمیان مستقل کشمکش کو باقی رکھنا اور مقدمہ بازی کو مستقل صور ت دینا ہے۔ اسلام کا نظام عدل اس چیز کو بر داشت نہیں کرتا۔
فور ی...

MANAJEMEN PENDIDIKAN ISLAM DI PESANTREN: PERSPEKTIF EPISTEMOLOGI

Management of Islamic education in pesantren needs to return to its historical roots in order to confirm the identity, character, distinctiveness and uniqueness. There is a spirit that is timeless, even the underlying model of ideal education in the contemporary era. Development of Islamic epistemology for education should be able to give birth to a generation of Muslims who worships in the field of religion and experts in the field of science and technology. Pesantren as an educational institution of Islam with a good management should be able to play its role to achieve this goal. Whereas in fact there who think that pesantren have not been able to put its strategic position in the development of science in accordance with the times. Nevertheless, the existence of Islamic educational institutions such as pesantren is evidence that pesantren have been organized in a good management so that it can survive in changing times from time to time. More precisely knowing Islamic education management in pesantren from the perspective of epistemology may illustrate that pesantren will continue to be needed to confront the changing times.

Laser Ablation Studies of Metal Alloys Using Libs and Time of Flight Mass Spectrometry

Laser ablation is a versatile technique used for the investigations of technological advanced and industrially important materials. In this technique, the interaction of a short and intense laser pulse forms a plasma plume. The laser produced plasma plume consists of radiation which arises due to transitions of electrons from the excited states of atoms and ions. The aim of this thesis is the fabrication of the laser ablation time of flight mass spectrometer (LA-TOF-MS) with an improved resolution and to compare the compositional results of mass spectra from LA-TOF-MS with the emission spectra obtained from laser induced breakdown spectroscopy (LIBS). The compositional analysis using calibration free (CF-LIBS) techniques is based on the observed emission spectra of the laser produced plasma plume whereas, the elemental composition analysis using laser ablation time of flight mass spectrometer (LA TOFMS) is based on the mass spectra of the ions produced by laser ablation. We have successfully designed and locally fabricated an improved version of the laser ablation time-of-flight mass spectrometer (LA-TOF-MS) for isotope mass analysis and elemental analysis of materials. This system is coupled with a Q-switched Nd: YAG laser, which is capable of delivering the energy of about 850 mJ at 1064 nm and 500 mJ at 532 nm. The resolution of system has been improved by adjusting spatial and space focusing, and optimizing other parameters. The capability of the system has been exploited by the isotopic analysis and compositional analysis of different alloy samples, having certified composition. The laser ablation time of flight mass spectrometer complementary with Laser induced breakdown spectroscopy has xxi been used for the quantitative determination of constituents of certified samples; different Karats of gold (18K, 19K, 20K, 22K, 24K), Brass alloy (Cu 62%, Zn 38%) and Cu-Ni Alloy (75% Cu, 25% Ni). Moreover, the samples with the unknown compositions such as different brands of the cigarette available in Pakistan have also been investigated using LIBS and LA-TOF-MS techniques. Initially five Karats of gold alloys, 18K, 19K, 20K, 22K and 24K having certified composition of gold as 75%, 79%, 85%, 93% and 99.99% were selected and their precise elemental compositions were determined by LIBS and LA-TOF-MS. Here internal reference line self-absorption correction laser induce breakdown spectroscopy (IRSAC-LIBS) technique have been utilized for the quantitative determination of constituents present in different Karats. Elemental compositions of these gold alloys were also determined using a Laser Ablation time of flight mass spectrometer (LA-TOF-MS). The quantitative analysis of brass alloy has been studied using Laser Induced Breakdown Spectroscopy (LIBS), Energy Dispersive X-ray Spectroscopy (EDX) and Laser Ablation Time of Flight Mass Spectrometry (LA-TOF-MS). The emission lines of copper (Cu I) and zinc (Zn I) are used to calculate the plasma parameters. Here we have compared the elemental composition obtained by SCF-LIBS and IRSAC-LIBS with LA-TOF-MS and EDX. After utilizing SCF-LIBS and IRSAC-LIBS for quantitative analysis, we have compared the composition for Cu-Ni alloy using three calibration free LIBS techniques other than IRSAC-LIBS, and also compared the results with laser ablation LA-TOF-MS. For the quantitative determination of constituents of Cu-Ni Alloy (Pakistani five rupee coin of year 2004) of known composition (Cu 75%, Ni 25%), we have utilized one line calibrations-free (OL-CF xxii LIBS), self-calibration free (SCF-LIBS), and algorithm based calibration free (AB-CF LIBS) techniques. Results obtained by these LIBS based techniques have also been compared with LA-TOF-MS. The samples of fourteen different brands of cigarettes available in Pakistan have also been analyzed using the above mentioned techniques. We have also performed compositional analysis of the trace elements in different brands of tobacco available in Pakistan using one line calibration free (OLCF-LIBS) and Laser ablation Time of Flight Mass Spectrometer (LA-TOFMS). The results obtained by (CF-LIBS) are comparable with (LA-TOF-MS). The compositional results obtained by OL-CF-LIBS, SCF-LIBS, IRSAC-LIBS and algorithm based AB-CF LIBS are in agreement with that of LA-TOF-MS and other standard techniques. The analysis of different industrial important alloys and different brands of cigarettes demonstrates that LIBS complemented with LA-TOF-MS are powerful techniques for the elemental analysis of the major and trace elements in any solid samples.