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

Asian Research Index Whatsapp Chanel
Asian Research Index Whatsapp Chanel

Join our Whatsapp Channel to get regular updates.

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...

ان کو خبر نہیں کہ لہو بولتا بھی ہے

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

ابن ہمام اور ان کی کتاب فتح القدیر کا تعارف و منہج

Fath ul Qadeer is one of the most comprehensive and well organized works in the Hanafi School of thought. Full name of this book is Fath ul Qadeer Lel ‘Aajez el Faqeer. It is a commentary and illustration of Hedaya, the most popular and authentic book in Islamic jurisprudence and in Islamic schools of thought. It is compendium of Islamic knowledge with a discussion on various subjects that are from various types of fiqh and Usool-e-fiqh. Author, Ibn e Hamam used a critical explanation of words from lexical to technical, their grammatical analysis, connection on the basis of grammatical and syntax regulations and illustration of differences between synonyms. The methodology of this book is unique as it provide unprejudiced and impartial in analysis of various topics under discussion and the rational and logical arguments given by the author in support of his view make this book a significant work and a remarkable milestone in fiqh collections. The paper concludes with a comprehensive analysis of the aspects dealt with in terms of methodology and its characteristics.

Fixed Frequency Sliding Mode Control for Parallel Inverters in a Microgrid With Distributed Generation

With the growing electricity demand and environmental challenges, integration of the high penetration distribution generation (DG) into the utility grid is utmost important to improve the grid efficiency. Microgrid helps in facilitating the penetration of various DGs in the distribution network, while ensuring efficient, reliable and resilient operation in an islanded mode during a utility outage. However, the power electronic interface with DG units needs robust control techniques that can achieve high performance in all the loading conditions and conditions at the utility grid. Microgrid contains a cluster of loads along with DG units operating as a unified controlled system. Interconnecting DGs with a grid using power electronic converters has increase concerns regarding safe operation and protection of the equipment. Many control strategies have been proposed for enhancing the stability of microgrid for proper load sharing. However, these controllers have problems of slow dynamic response, disturbance to uncertainties and weak tracking of the references. Therefore, this work proposes new approaches using nonlinear control technique based on the sliding mode control (SMC) for an islanded mode as well as grid-connected mode of operation. Fixed Frequency Sliding Mode Voltage Control (FFSMVC) technique is developed for single and parallel voltage source inverter (VSI) in islanded mode, to maintain the quality of the output voltage of the DG system despite unbalanced and/or non-linear load currents. Fix frequency slide mode control is efficient in reducing the chattering phenomena, which otherwise call unnecessary harmonics and power loss in the system. Further, this controller improves the steady state and dynamic response under sudden load fluctuation. Droop control approach is investigated to guarantee the accurate power sharing among DG units in parallel operation. Fixed Frequency Sliding Mode Current Control (SMCC) approach is adopted for the grid-tied mode, where the controller works as a current controller. The proposed controller effectively abandons the grid voltage disturbances and the parameter uncertainties. Furthermore, PQ sharing control is designed for the parallel operating of DG units by delivering available power to the grid side in order to ensure power-sharing requirements. Both controllers have been simulated in the real-time domain of Simulink/MATLAB environment. Finally, the performance of the proposed FFSMC is compared with the classical proportional integral (PI) controller. The simulation results show the Total Harmonics Distortion (THD) of the output voltage of 0.86% and 1.54% for FFSMVC, and 1.82% and 6.84% for PI controller under linear and nonlinear loads respectively. The results also validate that the proposed control technique is quite effective due to its robust response and less sensitive to external disturbances.