شماره ركورد
34859
پديد آورنده
سلام البدري
عنوان
برچسبگذاري گريسفولِ برخي گرافها
مقطع تحصيلي
كارشناسي ارشد
رشته تحصيلي
رياضي- رياضي محض ـ جبر
سال تحصيل
1403
تاريخ دفاع
1405/1/30
استاد راهنما
مهدي علائيان
استاد مشاور
/
دانشكده
دانشكده رياضي
چكيده
اين پاياننامه به بررسي ساختاري برچسبگذاريهاي گريسفول (Graceful) و آلفا (α‑labeling) در گرافها ميپردازد و تأكيد ويژهاي بر درختها و مشخصههاي مبتني بر ماتريس دارد. گفته ميشود گرافي با 𝑚m يال گريسفول است اگر بتوان به هر رأس گراف يك عدد صحيح متمايز از مجموعه {0,1,…,m} اختصاص داد، بهگونهاي كه برچسبهاي القايي يالها (يعني قدرمطلق تفاضل برچسبهاي دو رأس مجاور) دقيقاً مجموعه {1,2,…,m} باشند. پيشرفتهاي حاصل در برخي ردههاي خاص از گرافها هنوز به حل حدس درخت گريسفول (Graceful Tree Conjecture) منجر نشده است؛ حدسي كه بيان ميكند هر درخت داراي يك برچسبگذاري گريسفول است. مفهوم مرتبط با آن برچسبگذاري α است كه نوعي محدوديت بر برچسبگذاري گريسفول اعمال ميكند و با افزودن يك شرط ترتيبي بر برچسبهاي رأسها، آنها را به صورت يك افراز به دو زيرمجموعه تقسيم ميكند. نوآوري اصلي اين پژوهش ارائهٔ رويكردي مبتني بر ماتريس براي بررسي برچسبگذاريهاي گريسفول و α است كه از يك برچسبگذاري رأسي الهام گرفته شده است. در اين چارچوب، برچسبگذاري گريسفول بهصورت برچسبگذارياي از يك گراف تعريف ميشود كه در آن هر خط قطري ماتريس (بهجز قطر اصلي) دقيقاً شامل يك درايهٔ برابر با 1 است. همچنين براي برچسبگذاريهاي α، شرايط لازم و كافي دربارهٔ الگوي صفرها در بخش مثلثيِ پايين ماتريس وجود دارد، همراه با وجود درايهاي به صورت a_βλ=1 بهگونهاي كه β−λ=1 . اين مشخصهها ويژگيهاي تركيبياتيِ برچسبگذاري را به نمايشهاي جبريِ مبتني بر ماتريس مرتبط ميكنند. روش ماتريسي ارائهشده براي خانوادههاي خاصي از درختها به كار گرفته ميشود. نشان داده ميشود كه تحت برخي شرايط ساختاري، گرافهاي سوپراستار (درختهاي ريشهداري كه از گرافهاي ستارهاي ساخته ميشوند و برگهاي آنها به يك ريشهٔ مشترك متصل ميشوند) داراي برچسبگذاري α هستند. همچنين ثابت ميشود كه درختهاي سوپرريشهدار (كه از اتصال چند درخت ريشهدار به يك ريشهٔ مشترك ساخته ميشوند) در صورتي كه درختهاي تشكيلدهنده گريسفول باشند و ريشهٔ آنها با برچسبگذاري شده باشد، خود نيز گريسفول خواهند بود. علاوه بر اين، ساختارهاي بازگشتي خانوادههاي نامتناهي از درختهاي داراي برچسبگذاري گريسفول و α توليد ميكنند. نتايج نشان ميدهد كه ماتريسهاي مجاورت تعميميافته ابزاري ساختاريافته و كارآمد براي تحليل و ساخت نظاممند خانوادههاي درختي برچسبگذاريشده هستند
تاريخ ورود اطلاعات
1405/03/04
عنوان به انگليسي
Graceful Labeling of Certain Graphs
تاريخ بهره برداري
4/19/2026 12:00:00 AM
دانشجوي وارد كننده اطلاعات
سلام البدري
چكيده به لاتين
This thesis presents a structural investigation of graceful and α-labelings of graphs, with particular emphasis on trees and matrix-based characterizations. A graph with m edges is said to be graceful if it is possible to assign a distinct integer to every vertex of the graph using the integers {0,1,…,m} in such a way that the induced edge labels (the absolute difference between the labels of adjacent vertices) are exactly {1,2,…,m}. Progress on special classes does not seem to have led to a resolution of the Graceful Tree Conjecture which states that every tree has a graceful labeling. Closely related is α-labeling which restricts graceful labeling by adding an ordering constraint on the vertex labels in the form of a partition into two subsets. The main novelty is the invention of a matrix based approach for considering graceful and α labelings, which is motivated by a vertex labeling. In this context, graceful labelings are defined as labelings of a graph in which each diagonal line (excluding the main diagonal) has exactly one entry equal to 1 . Moreover, the α-labelings have necessary and sufficient zero-pattern conditions in the lower triangular part of the matrix and the existence of an entry a_βλ=1 such that β-λ=1. These characterizations link the combinatorial labeling properties to algebraic matrix representations. The matrix methodology is applied to specific families of trees. It is proved that, under certain structural requirements, superstar graphs (rooted trees built from star graphs by connecting their leaves to a common root) have α-labelings. Super-rooted trees (constructed from several rooted trees by connecting their roots to a common root) are proven graceful if the constituent trees are graceful with roots labeled 0 or m. Recursive constructions yield infinite families of graceful and α labeled trees. The results show that generalized adjacency matrices are both a structured and efficient tool for analyzing and systematically constructing labeled tree families
كليدواژه هاي فارسي
برچسبگذاري گريسفول , برچسبگذاري آلفا , ماتريس مجاورت تعميميافته , گرافهاي درختي
كليدواژه هاي لاتين
Graceful labeling , α-labeling , Generalized adjacency matrix , Tree graphs
Author
Badri
SuperVisor
Dr.Alaeiyan