Search or add a thesis

Advanced Search (Beta)
Home > Cycle Discrepancy of Graphs

Cycle Discrepancy of Graphs

Thesis Info

Access Option

External Link

Author

Laeeq Aslam

Program

PhD

Institute

University of the Punjab

City

Lahore

Province

Punjab

Country

Pakistan

Thesis Completing Year

2017

Thesis Completion Status

Completed

Subject

Computer Science

Language

English

Link

http://prr.hec.gov.pk/jspui/bitstream/123456789/12779/1/PhD%20Thesis%20Laeeq%20Aslam%20PHDCSF10M007.pdf

Added

2021-02-17 19:49:13

Modified

2024-03-24 20:25:49

ARI ID

1676727723989

Similar


In this thesis a new graph invariant, cycle discrepancy, is introduced. The optimal bounds on the cycle discrepancy for class of three-regular graphs and class of 3-colorable graphs are found. If the class of three-regular graphs is further restricted to Halin graphs, the established bound on cycle discrepancy reduces linearly. Necessary and sufficient conditions are given for a graph to have maximum possible cycle discrepancy. Further, it is shown that computing cycle discrepancy of a graph is an NP-hard problem. Let G = (V,E) be an undirected simple graph on n vertices. The cycle discrepancy of G, denoted as cycdisc(G) is in general bounded as: 0 ≤ cycdisc(G) ≤ ⌈n 2 ⌉. If G is a three colorable graph then cycdisc(G) is tightly bounded by ⌊n 3 ⌋. For d > 3, such d-colorable graphs are presented that have maximum possible cycle discrepancy. If G is a cubic graph then there is a tight bound of n+2 6 on its cycle discrepancy. An O(n2) algorithm is also presented to label the vertices of G such that cycdisc(G) ≤ n+2 6 . If G is not only cubic but also a Halin graph then cycdisc(G) ≤ n 8 +O(log n) and this bound is tight apart from the additive O(log n) term. It is also established that if minimum-degree of G is 3n 4 then cycdisc(G) = ⌈n 2 ⌉. Further, for n > 6, if maximum-degree of G is Δ and Δ2 < n − 1, then cycdisc(G) < ⌈n 2 ⌉. A graph is also constructed with maximum-degree n 2 + 2, that has maximum possible cycle discrepancy. This thesis provides a ground for further investigation in this area.
Loading...
Loading...

Similar Books

Loading...

Similar Chapters

Loading...

Similar News

Loading...

Similar Articles

Loading...

Similar Article Headings

Loading...

نسیم سخن کی ایک جھلک

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

متعہ كی لغوی تحقیق اورشرعی حیثیت تاریخی تناظر میں

This article deals with the issue of temporary marriage or "Mut'a" as is euplicated and regulated by Islamic Shariah in the early days of islam. Since those particular conditions did not prevail later, hence it became redundant. However, the term "Mut'a" has been used in the Holy Qur'an in multiple ways. Our scholarly interest focuses this particular dimension. Moreover a minor segment of Muslims still practice "Mut'a". However, the Sunni Scholars and followers have stopped practised on it. Iran e.g. still follows this temporary mode of marriage (they may opt to do so). However, according to Sunni traditions, this practice has been abolished. Hereby a scholarly investigation is done on "Mut'a", its terminology, its history its background and the particular conditionalities

Students’ Perceptions of the Learning Environment and Their Approaches to Study: Analysis of Two Public Sector Universities in Lahore

This study aimed at exploring the learning experiences (perceptions of learning environment* learning preferences, motivation and approaches to study) of students at two universities. The study was conducted with the students who were taking honours degrees or Master’s degrees at the two universities. Sample consisted of 912 students from four subject areas: social sciences, science and technology, humanities and business and management. The students were sampled from all four years. There were 494 men and 418 women between 17 and 27 years age. The study drew upon quantitative and qualitative data. In addition to measures of students’ learning preferences and motivation, Course Experience Questionnaire and Approaches to Learning and Studying Inventory were used to measure the students’ perceptions of the teaming environment and their approaches to study, respectively, Interviews were conducted with the students to provide context to findings from the survey data. One of the objectives of the study was to examine how the Course Experience Questionnaire and the Approaches to learning and Studying Inventory work in higher educational context of Pakistan. The Approaches to Learning and Studying Inventory seemed to work well in the new context; its intended constituent structure was confirmed in factor analysis, and the identified scales (deep approach* organized studying, surface approach and monitoring studying) exhibited moderate to high reliability. However, the Course Experience Questionnaire worked slightly less well; its intended constituent structure was only partly confirmed in the new context. The results showed that the learning environment encouraged the desirable approaches (deep approach, organized studying and monitoring studying) more than the less desirable approaches (surface approach). The students who had positive perceptions of the learning environment were more likely to use the desirable approaches to study; they also tended to prefer courses, leaching and assessment that support understanding, and were engaged and reliable in their studies. On the other hand, the students who had negative perceptions of the learning environment, were more likely to use surface approach to study, and were also more likely to prefer the courses, teaching and assessment that support transmission of information. Students showed greater preference for the learning environment that supports understanding than the learning environment that supports transmission of information. Multivariate analysis of variance identified meaningful variations in the students’ perceptions of the learning environment, learning preferences, motivation and approaches to study, related to institution, subject area, year of study, timing of the programme, gender and age. Students in social sciences and humanities perceived their learning environment more positively and were more likely to use deep approach to study than students in science and technology. There were variations in students’ perceptions of the learning environment and in their learning preferences with age. Male and female students differed in their perceptions and motivation but not in their learning preferences and approaches to study. Students in morning and evening programmes showed variation in their perceptions and motivation but not in their preferences and approaches to study. Students in different years of study also differed in their perceptions but not in their preferences. motivations and approaches to study.