حول مؤشر وينر للرسوم البيانية ذات رقم التفكك المعطى On the Wiener Index of Graphs with Given Dissociation Number

المجلة: match Communications in Mathematical and in Computer Chemistry، المجلد: 3، العدد: 96
DOI: https://doi.org/10.46793/match.96-3.31225
تاريخ النشر: 2026-03-12
المؤلف: Yibo Xu وآخرون
الموضوع الرئيسي: نظرية الرسوم البيانية وتطبيقاتها

نظرة عامة

في هذا القسم، يتم تقديم مفهوم مجموعة التفكك ضمن رسم بياني $ G = (V_G, E_G) $، حيث تعتبر مجموعة فرعية $ S \subseteq V_G $ مجموعة تفكك إذا لم يحتوي الرسم البياني الفرعي الناتج $ G[S] $ على مسار بطول 3، يُشار إليه بـ $ P_3 $. تركز الورقة على تحديد أكبر مجموعة تفكك، والتي تُعرف بأنها مجموعة التفكك ذات أكبر عدد من العناصر، ويشار إليها برقم التفكك لـ $ G $.

يحدد المؤلفون حدودًا دنيا حادة لمؤشر وينر عبر فئات مختلفة من الرسوم البيانية، بما في ذلك الأشجار، والرسوم البيانية الثنائية، والرسوم البيانية المتصلة العامة، جميعها تتميز بترتيب ثابت ورقم تفكك. بالإضافة إلى ذلك، تصف الأبحاث الرسوم البيانية التي تحقق أقصى مؤشرات وينر لترتيب ثابت $ n $ وأرقام تفكك محددة $ \phi \in \{2, \frac{2}{3}n, n-2, n-1\} $. تساهم هذه النتائج في فهم العلاقة بين هيكل الرسم البياني ومؤشر وينر، مما يوفر رؤى حول نظرية الرسوم البيانية القصوى.

مقدمة

في هذا القسم، يقدم المؤلفون المفاهيم والتعاريف الأساسية ذات الصلة بدراستهم لمؤشر وينر، وهو مؤشر طوبولوجي مهم في نظرية الرسوم البيانية، وخاصة في نظرية الرسوم البيانية الكيميائية. يعرفون أنواع الرسوم البيانية المعنية—غير الموجهة، البسيطة، والمتصلة—ويقدمون مصطلحات رئيسية مثل الجيران، درجة الرأس، الرؤوس المعلقة، والرؤوس شبه المعلقة. كما يشرح المؤلفون مفهوم مجموعة التفكك، وهي مجموعة فرعية من الرؤوس التي لا تحتوي على رسم بياني فرعي محدد (P3)، ويعرفون رقم التفكك، φ(G)، كحجم أكبر مجموعة تفكك.

التركيز الرئيسي للورقة هو استكشاف المشكلات القصوى المتعلقة بمؤشر وينر بين الرسوم البيانية المتصلة، الرسوم البيانية الثنائية، والأشجار ذات ترتيب ورقم تفكك ثابتين. يقدم المؤلفون نتائجهم الرئيسية، بما في ذلك نظرية تحدد حدودًا دنيا لمؤشر وينر بناءً على توازن رقم التفكك. على وجه التحديد، يستنتجون الشروط التي تتحقق فيها المساواة، موضحين الرسوم البيانية القصوى التي تحقق هذه الحدود. يبني هذا العمل على الدراسات السابقة لمؤشر وينر وخصائصه القصوى، بهدف المساهمة في فهم هياكل الرسوم البيانية ذات الخصائص التفككية المحددة.

نتائج

في هذا القسم، يتم تقديم نتائج أولية ستدعم إثبات النتائج الرئيسية. على وجه التحديد، يحدد اللمحة 2.1 علاقة تتعلق برقم التفكك $\phi(G)$ لرسم بياني بسيط $G$. ينص على أنه بالنسبة لأي رأس $v \in V(G)$، فإن رقم التفكك يحقق عدم المساواة $\phi(G) – 1 \leq \phi(G – v) \leq \phi(G)$.

بالإضافة إلى ذلك، يشير المؤلفون إلى عمل Brešar وآخرين [2]، الذين قدموا حدًا أدنى مهمًا لرقم التفكك لشجرة، وهو أمر أساسي للتحليل والنتائج اللاحقة في الورقة.

مناقشة

في هذا القسم، يقدم المؤلفون عدة نتائج مهمة تتعلق بمؤشر وينر للرسوم البيانية المتصلة. يحدد التوابع 1.2 أنه إذا كان $ G $ رسمًا بيانيًا متصلًا من ترتيب $ n $ مع الحد الأدنى لمؤشر وينر، فإن $ G $ هو متساوي الشكل مع الرسم البياني الكامل $ K_n $. توفر النظرية 1.3 حدًا أدنى حادًا لمؤشر وينر بين فئة الرسوم البيانية $ B_{n,\phi} $، حيث ينص على أن $ W(G) \geq n^2 + \phi^2 – n\phi – n $ يتحقق مع المساواة إذا وفقط إذا كان $ G $ متساوي الشكل مع $ K_{\phi, n-\phi} $.

كما يقدم المؤلفون الشجرة $ S^*_{n,\phi} $، التي تم إنشاؤها من رسم بياني نجمي عن طريق إرفاق حواف معلقة، ويحددون الأشجار في $ T_{n,\phi} $ ذات الحد الأدنى لمؤشر وينر من خلال النظرية 1.4. تؤكد هذه النظرية أن $ W(T) \geq 3n^2 – 2n\phi – 12n + 8\phi + 9 $ مع المساواة إذا وفقط إذا كان $ T $ متساوي الشكل مع $ S^*_{n,\phi} $. أخيرًا، تحدد النظرية 1.5 الرسوم البيانية في $ G_{n,\phi} $ لقيم محددة من $ \phi $ (2، $ \frac{2}{3}n $، $ n-2 $، و $ n-1 $) التي تحقق أقصى مؤشرات وينر، مما يوفر حدودًا وشروطًا صريحة للمساواة في كل حالة. يختتم القسم بخريطة طريق لبقية الورقة، موضحًا الإثباتات والاتجاهات البحثية المستقبلية.

Journal: match Communications in Mathematical and in Computer Chemistry, Volume: 3, Issue: 96
DOI: https://doi.org/10.46793/match.96-3.31225
Publication Date: 2026-03-12
Author(s): Yibo Xu et al.
Primary Topic: Graph theory and applications

Overview

In this section, the concept of a dissociation set within a graph $ G = (V_G, E_G) $ is introduced, where a subset $ S \subseteq V_G $ qualifies as a dissociation set if the induced subgraph $ G[S] $ does not contain a path of length 3, denoted as $ P_3 $. The paper focuses on identifying the maximum dissociation set, which is defined as the dissociation set with the largest cardinality, referred to as the dissociation number of $ G $.

The authors establish sharp lower bounds for the Wiener index across various classes of graphs, including trees, bipartite graphs, and general connected graphs, all characterized by fixed order and dissociation number. Additionally, the research characterizes the graphs that achieve maximum Wiener indices for fixed order $ n $ and specific dissociation numbers $ \phi \in \{2, \frac{2}{3}n, n-2, n-1\} $. These findings contribute to the understanding of the relationship between graph structure and the Wiener index, providing insights into extremal graph theory.

Introduction

In this section, the authors introduce the foundational concepts and definitions relevant to their study of the Wiener index, a significant topological index in graph theory, particularly in chemical graph theory. They define the types of graphs considered—undirected, simple, and connected—and introduce key terms such as neighbors, degree of a vertex, pendant vertices, and quasi-pendant vertices. The authors also explain the concept of a dissociation set, which is a subset of vertices that does not contain a specific subgraph (P3), and define the dissociation number, φ(G), as the size of the largest dissociation set.

The main focus of the paper is to explore extremal problems related to the Wiener index among connected graphs, bipartite graphs, and trees with a fixed order and dissociation number. The authors present their primary results, including a theorem that establishes lower bounds for the Wiener index based on the parity of the dissociation number. Specifically, they derive conditions under which equality holds, characterizing the extremal graphs that achieve these bounds. This work builds on previous studies of the Wiener index and its extremal properties, aiming to contribute to the understanding of graph structures with specific dissociation characteristics.

Results

In this section, preliminary results are presented that will support the proof of the main findings. Specifically, Lemma 2.1 establishes a relationship involving the dissociation number $\phi(G)$ of a simple graph $G$. It states that for any vertex $v \in V(G)$, the dissociation number satisfies the inequality $\phi(G) – 1 \leq \phi(G – v) \leq \phi(G)$.

Additionally, the authors reference the work of Brešar et al. [2], who provided a significant lower bound for the dissociation number of a tree, which is integral to the subsequent analysis and results in the paper.

Discussion

In this section, the authors present several significant results regarding the Wiener index of connected graphs. Corollary 1.2 establishes that if $ G $ is a connected graph of order $ n $ with the minimum Wiener index, then $ G $ is isomorphic to the complete graph $ K_n $. Theorem 1.3 provides a sharp lower bound for the Wiener index among the class of graphs $ B_{n,\phi} $, stating that $ W(G) \geq n^2 + \phi^2 – n\phi – n $ holds with equality if and only if $ G $ is isomorphic to $ K_{\phi, n-\phi} $.

The authors also introduce the tree $ S^*_{n,\phi} $, which is constructed from a star graph by attaching pendant edges, and characterize trees in $ T_{n,\phi} $ with the minimum Wiener index through Theorem 1.4. This theorem asserts that $ W(T) \geq 3n^2 – 2n\phi – 12n + 8\phi + 9 $ with equality if and only if $ T $ is isomorphic to $ S^*_{n,\phi} $. Finally, Theorem 1.5 characterizes graphs in $ G_{n,\phi} $ for specific values of $ \phi $ (2, $ \frac{2}{3}n $, $ n-2 $, and $ n-1 $) that achieve maximum Wiener indices, providing explicit bounds and conditions for equality in each case. The section concludes with a roadmap for the remainder of the paper, outlining the proofs and future research directions.