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

Asian Research Index Whatsapp Chanel
Asian Research Index Whatsapp Chanel

Join our Whatsapp Channel to get regular updates.

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

محمد پاشا محمود

محمد پاشا محمودؔ
مصر کی ڈاک سے یہ معلوم کر کے بڑا افسوس ہوا کہ محمد پاشا محمود جو زغلول پاشا کے وفد کے ممبر تھے، اور بعد کوالگ ہو کر مصر کی وزارت میں شامل ہوگئے تھے، وفات پاگئے، ان کو ہندوستان سے یہ نسبت تھی کہ محمد علی مرحوم کے ساتھ اوکسفورڈ میں انھوں نے بھی تعلیم پائی تھی، پیرس میں وفد خلافت اور وفد مصر کی ملاقاتوں کے سلسلہ میں ان دونوں رفیقوں میں بڑی دلچسپ گفتگو ہوئی تھی، اور خاکسار سے زغلول پاشا کی ثالثی میں صحیح بخاری کی صحت پر ایک پر لطف مناظرہ ہوا تھا، زغلول پاشا کا یہ فقرہ جو محمد پاشا محمود کو مخاطب کرکے انھوں نے کہا تھا اب تک کانوں میں گونج رہا ہے، ودع الامام یتکلم۔ اﷲ تعالیٰ نام کی طرح اُن کی عاقبت بھی محمود فرمائے۔ (سید سلیمان ندوی، فروری ۱۹۴۱ء)

 

متابعتِ رسولﷺ (تکمیلِ ایمان) کے سات درجے: مکتوبات امام ربانی مجدد الفِ ثانی کی روشنی میں

The digit seven has great importance in our life. Seven rounds of  Holy Kabah, seven heavens, seven layers of earth, seven levels of  hell, seven recitation of Holy Quran, seven interior and exterior (meanings) of holy Quran, seven stages of human life, etc. Hazrat Mujadid Alf Sani mentioned the seven degrees and their secrets of the obedience of the Holy Prophet: Say: "if you do love (obey) Allah, then follow me, Allah will (love) save you". Actually the perfect following of the Holy Prophet is the source of the completion of faith. As we adopt the following of the Holy Prophet, so and so our faith will reach to the perfection. In this article, the introduction of seven degrees of the following of the Holy Prophet and their secrets are described, in the light of 54th writing in book II. So books so that every Muslim after seeing his faith, could be able to complete the degrees of the perfection of faith and could get the nearness of God.

Thermodynamical Behaviour of 1-1 Strong Electrolytes in Water, Dimethyl Sulfoxide and Water- Dimethyl Sulfoxide Mixtures.

The densities, viscosities and relative viscosities of solutions of several univalent electrolytes Lithium bromide (LiBr), Sodium bromide (NaBr), Potassium bromide (KBr), Rubidium bromide (RbBr) Cesium bromide (CsBr) and reference salts tetra butyl ammonium tetra phenyl borate (BU4NBPh4 ), tetra butyl ammonium bromide (BU4NBr) and potassium chloride (KCl) were measured over the entire range of concentration at 25 oC to 45oC in pure DMSO, pure water and DMSO- H2O binary mixtures. Data was analysed by Jones-Dole equation to determine ion –ion interactions (the A- coefficients), ion- solvent interaction, (the B- coefficients) for alkali metal bromides in pure DMSO, pure water and DMSO- H2O binary mixtures. The values of A- coefficients were small and almost positive in all the cases. The values of B- coefficients were large and almost positive of all the salts in DMSO and DMSO- H2O mixtures, which showed the structure making abilities of the salts in DMSO- H2O mixtures at all the five temperatures. The values of viscosity B- coefficients were found negative for KBr, RbBr and CsBr in pure water at all the five temperatures, which showed the structure breaking abilities of the salts while the values of viscosity B- coefficients of LiBr and NaBr in water at all the five temperatures were found positive and behave as structure makers. iv The viscosity B- coefficient data was further splitted into ionic B- coefficient for non-aqueous solvents by using Gill and Sharma’s convention and Gurney’s convention into ionic B- coefficients for aqueous solvent systems. From ionic B- coefficient data it was observed that in pure DMSO all the alkali metals have strong structure making abilities. It was also observed that these structure making abilities were decreased with the increase in ionic radii or temperature. While in aqueous solvents (DMSO- H2O) mixtures the structure forming capabilities were weakened and structure breaking abilities were appeared at all temperatures. In pure water except Li+ and Na+ all the ions showed the structure breaking properties, which increased with the increase in temperature. The data obtained during this study was found in good agreement with those values which were already available in literature. The Transition state parameters such as free energies and energies of activation for viscous flow have been calculated for the whole solvent system. From the present study it is concluded that the energy of activation of viscous flow is influenced by the concentration and the size of the solute particles. So the energy of activation of viscous flow for CsBr is greater than for RbBr, KBr, NaBr and LiBr in DMSO and DMSO-H2O mixtures. It is also observed that the energy of activation of viscous flow are greater for alkali metal bromides in water than in DMSO due to the presence of a network of hydrogen bonds in water. For the free energy of activation for viscous flow, it is observed that the free energy of activation for viscous flow increases with temperature.