An Upper Bound For The Graovac-Pisanski(G-P) Index of The Fibonacci Cubes

Subject Areas : Statistics

Hojat Kaviani ¹ , LOTFALLAH POURFARAJ ²

1 - Department of Mathematics, Central Tehran BranchIslamic Azad University,Tehran, Iran
2 - Department of Mathematics, Central Tehran Branch, Islamic AzadUniversity, Tehran, Iran

Received: 2021-09-18 Accepted : 2022-02-02 Published : 2024-01-18

Keywords: خودریختی گراف ها&quot, &quot, شاخص G-Pگراف &quot, , &quot, مکعب های فیبوناچی&quot, شاخص وینر گراف&quot,

Abstract :

Let G be a simple connected graph with vertex set V(G) and edge set E(G). A topological index of graph G is a numeric value to which the graph is assigned and is invariant to G automorphisms.The Wiener index of a connected graph G is defined as W(G) = ∑{u,v}⊆V (G) d(u, v) where d(u,v) is the distance between vertices u and v in G . The Graovac-Pisanski (G-P) index of a graph G is a modified version of the Wiener index on the distance between each vertex u and its image α(u) , where α is an automorphism of graph G . Let Fn be the set of all binary strings of length n that have no two consecutive 1s. The Fibonacci cube Γn ,where n>1or n=1, is a graph with the vertex set Fn . In this graph, two vertices are adjacent if and only if their differ be at precisely one coordinate. In this paper, we obtain an upper bound for the G-P index of the Fibonacci cubes.

References:

[1] W J. Hsu, Fibonacci cubes- a new interconnection technology. IEEE Trans. Parallel Distr. Systems, 4 (1993) , no. 1. 3-12

[2] H. Wiener, Structural Determination of Paraffin Boiling Points, J. Am. Chem. Soc, 69 (1947) 17-20.

[3] M. Kovse, R. V. A, A. Vijayakumar, Wiener index and Steiner 3-Wiener index of a graph, Asian-European J.Math, Vol 14 (09), (2021), 2150165.

[4] A. Graovac, T. Pisanski, On the Wiener index of a graph, J. Math. Chem, 8 (1991) 53-62.

[5] M. Ghorbani, M. Hakimi-Nezhad, M. Dehmer and X. Li, Analysis of the Graovac-Pisanski Index of Some Polyhedral Graphs Based on Their Symmetry Group, Symmetry, (2020),12,1411.

[6] A. R. Ashrafi, J. Azarija, Kh. Fathalikhani, S. Klavzar and M. Petkovsek. Vertex and edge orbits of Fibonacci and Lucas cubes, Ann. Comb, 20 (2016) 209-229.A. Graovac, T. Pisanski, On the Wiener index of a graph, J. Math. Chem, 8 (1991) 53-62.

[7] A. Castro, S. Klavzar, M. Mollard and Y. Rho. On the domination number and 2-packing number of Fibonacci cubes and Lucas cubes, Comput. Math. Appl, 61 (2011) 2655-2660.

Full-Text:



 

 

دسترسي در سايتِ http://jnrm.srbiau.ac.ir

سال هشتم، شماره چهلم، بهمن و اسفند 1401

شماره شاپا: X588-2588

 

 

 

 

يک کران بالا براي شاخص G-P مکعب‌هاي فيبوناچي

        

 

حجت کاویاني1، لطف‌الله پور فرج2¹ 

 

(1و2)   گروه رياضي، دانشکده علوم پايه، واحد تهران مرکزي، دانشگاه آزاد اسلامي، تهران، ايران

 

 

تاريخ ارسال مقاله: 27/06/1400   تاريخ پذيرش مقاله: 13/11/1400

چکيده

شاخص وينر گراف همبند  به صورت   تعريف مي‌شود که درآن  فاصله‌ي بين رئوس  و در  است. شاخص گراوواک – پيسانسکي (G-P) يک گراف، نسخه اصلاح شده شاخص وينر روي فاصله بين هر رأس  و تصوير  آن رأس مي‌باشد که  يک خودريختي گراف  است. مجموعه  شامل تمام رشته‌هاي دودويي به طول  است که داراي هيچ دو مولفه متوالي  1 نباشند. مکعب فيبوناچي  گرافي با مجموعه رئوس  است. در اين گراف، دو رأس مجاور هستند اگر و تنها اگر در يک مؤلفه اختلاف داشته باشند. ما در اين مقاله يک کران بالا براي شاخص G-P مکعب‌هاي فيبوناچي به دست می‌آوریم.

 

واژه‌هاي کليدي: مکعب‌هاي فيبوناچي، شاخص وينر گراف، شاخص G-P گراف، خودريختي گراف‌ها.

 

---

[1] . عهده­دار مکاتبات:                                                                                   Email: [e-mail]

1- مقدمه

فرض کنيد  يک عدد صحيح غير منفي باشد. ابرمکعب  بعدي گرافي است که رئوس آن رشته‌هاي دودويي هستند و دو رأس آن با هم مجاورند اگر و تنها اگر فاصله همينگ آن‌ها يک باشد. منظور از فاصله همينگ بين دو رشته، تعداد مولفه‌هايي است که آن دو رشته با هم اختلاف دارند. هسو در سال ۱۹۹۳ مکعب‌هاي فيبوناچي را تعريف کرد ]1[. اعداد فيبوناچي به صورت  و  و  () تعريف شده‌اند. يک مکعب فيبوناچي زيرگرافي از يک ابرمکعب است که مجموعه رئوس آن رشته‌هاي دودويي هستند به طوريکه هيچ دو 1 متوالي در رشته‌ها وجود ندارد، لذا داريم  ]1[ (شکل ۱). رأسي از  که داراي  تا است را با  نشان مي‌دهيم. فرض کنيد  مجموعه رئوسي از  باشند که به طور دقيق شامل  تا 1 است، بنابراين  مجموعه‌اي از رئوس  است که فاصله آن‌ها از  برابر است. همچنين 

 و .

 

 

شکل (1): مکعب‌های فیبوناچی

 

در سال ۱۹۴۷ هارولد وينر شاخص وينر گراف همبند  را به صورت  تعريف کرد که در آن  فاصله بين رئوس  و  در گراف همبند  است ]2[. اين شاخص در ]3[ براي مکعب‌هاي فيبوناچي محاسبه شده است. در سال ۱۹۹۱ گراوواک و پيسانسکي نسخه اصلاح شده‌اي از شاخ وينر ارائه کردند که علاوه بر فواصل بين رئوس، تقارن روي رئوس گراف‌ها را نيز شامل مي‌شود. اگر  يک گراف از مرتبه  و  گروه خودريختي‌هاي گراف  باشد آن‌گاه شاخص گراوواک – پيسانسکي (G-P) آن برابر است با ]4[.

 

فرض کنيد  يک گراف باشد، عمل گروه  روي ، آن را به مدارهايش افراز مي‌کند. رئوس  و  متعلق به يک مدار هستند اگر و تنها اگر  موجود باشد به طوري که .

 

قضیه ۱-۱]5[: اگر  يک گراف همبند و  مدارهاي  تحت عمل  باشند، آن‌گاه

 

 

2- مدارهاي مکعب‌هاي فيبوناچي 

فرض کنيد  يک گراف باشد. مجموعه مدارهاي رأسي حاصل از عمل  که روي  عمل مي‌کند را با  و تعداد اين مدارها را با  نشان مي‌دهيم. همچنين مجموعه مدارهاي رأسي گراف  از اندازه  را با  و تعداد آن‌ها را با  نشان مي‌دهيم.

اشرفي و همکاران گروه خودريختي مکعب‌هاي فيبوناچي را مورد مطالعه قرار داده‌اند ]6[. نگاشت معکوس  را به صورت زير درنظر بگيريد:

 

 

در اين صورت  تنها خودريختي نا‌بديهي است] 7[. 

 

قضیه 2-1] ۷[: براي هر  داريم . بنابراين مکعب‌هاي فيبوناچي داراي مدارهاي رأسي از اندازه‌هاي  و  هستند. در قضيه زير تعداد مدارهاي مکعب‌هاي فيبوناچي محاسبه شده است.

 

قضیه ۲-۲] ۶[: اگر ، آن‌گاه

 

 

 

 

براي مثال مدارهاي  به صورت زير است:

 

 

3- نتیجه اصلی

در اين بخش يک کران بالا براي شاخص G-P مکعب‌هاي فيبوناچي به دست مي‌آوريم.

 

قضيه 3-1: فرض کنيد  و   در اين صورت داريم:

. 

 

برهان. چون  و  و براي هر مدار از  داريم ، لذا با استفاده از قضيه ۱-۱ حکم برقرار است.

 

گزاره 3-2: براي هر رأس  متعلق به مدارهاي  داريم:

 

 

که درآن  برابر با تعداد  ها در  است.

 

برهان. فرض کنيد رأس  متعلق به مدارهاي  و . دو حالت زير را در نظر مي‌گيريم:

۱) .

اگر براي هر  هر دو مولفه  و  برابر  نباشند، آن‌گاه با توجه به تعريف نگاشت معکوس  تمام   تا  در  در جايگاهي متفاوت با   تا  در  قرار خواهند گرفت. بنابراين فاصله همينگ آن‌ها برابر  است. در غير اين صورت  موجود است به طوري که براي مولفه‌هاي غير متوالي  و  داريم . لذا با توجه به تعريف نگاشت معکوس ، رئوس  و  در دو مولفه  ام و  ام داراي  مي‌باشند بنابراين فاصله همينگ آن‌ها کمتر از  است. در نتيجه . 

۲) .

اگر براي هر  هر دو مولفه  و  برابر  نباشند و ، آن‌گاه با توجه به تعريف نگاشت معکوس  تمام   تا  در  در جايگاهي متفاوت با   تا  در  قرار خواهند گرفت. بنابراين فاصله همينگ آن‌ها برابر  است. در غير اين صورت  موجود است به طوري که براي مولفه‌هاي  و  داريم  يا ، آن‌گاه با توجه به تعريف نگاشت معکوس ، رئوس  و  در دو مولفه  ام و  ام داراي  مي‌باشند بنابراين فاصله همينگ آن‌ها کمتر از  است. در نتيجه.

 

فرض کنيد ، براي هر  منظور از مجموعه رئوس از  است که در آن‌ها  تا  وجود دارد. همچنين چون هر رأس ،  تا  و  تا  دارد، پس براي شمارش ، در هر رشته تايي ابتدا  ها را قرار داده و سپس  ها را در  مکان باقي مانده بين  ها جاي گذاري مي‌کنيم. بنابراين

 

 

قضيه ۳-۳ : اگر  عددي زوج باشد آن‌گاه تعداد رئوس  که  تا  دارند برابر است با

 

 

برهان. فرض کنيد  زوج و  رأسي از مدار  باشد که . بنابر تعريف نگاشت معکوس ، داريم . بنابراين رشته  متقارن است و دو مولفه وسط آن بايد  باشند، لذا  که. همچنين به دليل متقارن بودن ، تعداد  هاي آن نمي‌تواند عددي فرد باشد. پس بايد تعداد  عدد  را در  قرار مي‌دهيم. براي اين کار ابتدا  ها را قرار مي‌دهيم و سپس  ها را در  مکان باقي مانده بين  ها جاي گذاري مي‌کنيم.

 

 

قضيه 3-4 : فرض کنيد  عددي فرد باشد در اين صورت:

الف) هرگاه  فرد باشد آن‌گاه تعداد رئوس متعلق به مدارهاي  که  تا  دارند برابر است با

 

 

ب) هرگاه  زوج باشد آن‌گاه تعداد رئوس متعلق به مدارهاي  که  تا  دارند برابر است با

 

 

برهان.

الف) فرض کنيد  فرد باشد و  رأسي از مدار  باشد که . بنابر تعريف نگاشت معکوس ، داريم  درنتيجه رشته  متقارن است. چون  فرد است پس مولفه وسط در رأس  حتما عدد  مي‌باشد و بنابر تعريف مکعب فيبوناچي دو مولفه کناري آن نمي‌توانند  باشند لذا  که . بنابراين بايد تعداد  عدد  را در  قرار دهيم. ابتدا  ها را قرار مي‌دهيم و سپس  ها را در   مکان باقي مانده بين  ها جاي گذاري مي‌کنيم.

ب) فرض کنيد  زوج باشد و  رأسي از مدار  باشد که . بنابر تعريف نگاشت معکوس ، داريم . بنابراين رشته  متقارن است. چون  زوج است پس در مولفه وسط حتما عدد  بايد قرار بگيرد لذا  که . بنابراين بايد تعداد عدد  را در  قرار دهيم. ابتدا  ها را قرار مي‌دهيم و  ها را در  مکان باقي مانده بين  قرار مي‌دهيم.

 

 

نتيجه 3-5 : تعداد رئوس  که  تا  دارند برابر است با

الف) اگر  و  هر دو زوج باشند، آن‌گاه

 

 

 ب) اگر  زوج و  فرد باشند. آن‌گاه

 

 

پ) اگر  فرد و  زوج باشند. آن‌گاه

 

 

ت) اگر  و  هر دو فرد باشند. آن‌گاه

.

 

قضيه 3-6: در مکعب فيبوناچي  داريم:

الف) اگر  عددي زوج باشد، آن‌گاه

 

ب) اگر  عددي فرد باشد، آن‌گاه

 

که  تعداد  ها در رئوس  است.

 

برهان.

الف) فرض کنيد زوج و  مدارهاي با اندازه  در باشند. با استفاده از نتيجه 3-5، تعداد رئوس  که به طور دقيق  تا  دارند و دو به دو در يک مدار قرار دارند برابر است با

 

 

که  زوج و . و تعداد رئوس  که به طور دقيق  تا  دارند و دو به دو در يک مدار قرار دارند برابر است با

 

 

که  فرد و .

فرض کنيد   و ، در اين صورت با استفاده از گزاره 3-2 داريم: 

 

 

بنابراين

 

لذا

 

بنابر اين با استفاده از قضيه 3-1 داريم

 

ب) فرض کنيد عددي فرد و  مدارهاي با اندازه  در  باشند با استفاده از نتيجه 3-5 تعداد رئوس  که به طور دقيق  تا  دارند و دو به دو در يک مدار قرار دارند برابر است با

 

 

که  زوج و. تعداد رئوس  که به طور دقيق  تا  دارند و دو به دو در يک مدار قرار دارند برابر است با

 

 

که  فرد و

 

فرض کنيد   و  در اين صورت با استفاده از گزاره 3-2 داريم:

 

 

 

جدول (1): شاخص G-P مکعب‌هاي فيبوناچي ()

۷	۶	۵	۴	۳	۲
۶۸۰	۳۱۵	۶۵	۳۲	۵	۳
۹۱۸	۳۵۷	۷۸	۳۲	۵	۳	کران محاسبه شده

 

بنابراين

 

لذا

 

بنابر اين با استفاده از قضيه 3-1 داريم: 

 

 

براي   تساوي برقرار است. در حالت کلي اگر  زوج باشد و  رأسي از مدارهاي  باشد و مولفه هاي غير مجاور  و  هردو  نباشند آن‌گاه تساوي برقرار است. اگر  فرد باشد و هر دو مولفه  و  مخالف  باشند يا  آن‌گاه تساوي برقرار است. در غير اين صورت کران ارئه شده در قضيه ۹ شارپ است. در جدول زير شاخص G-P و کران حاصل از قضيه 3-6 براي برخي مکعب‌هاي فيبوناچي آمده است.

 

 

فهرست منابع

[1] W J. Hsu, Fibonacci cubes- a new interconnection technology. IEEE Trans. Parallel Distr. Systems, 4 (1993) , no. 1. 3-12

 

[2] H. Wiener, Structural Determination of Paraffin Boiling Points, J. Am. Chem. Soc, 69 (1947) 17-20.

 

[3] M. Kovse, R. V. A, A. Vijayakumar, Wiener index and Steiner 3-Wiener index of a graph, Asian-European J.Math, Vol 14 (09), (2021), 2150165.

 

[4] A. Graovac, T. Pisanski, On the Wiener index of a graph, J. Math. Chem, 8 (1991) 53-62.

 

[5] M. Ghorbani, M. Hakimi-Nezhad, M. Dehmer and X. Li, Analysis of the Graovac-Pisanski Index of Some Polyhedral Graphs Based on Their Symmetry Group, Symmetry, (2020),12,1411.

 

[6] A. R. Ashrafi, J. Azarija, Kh. Fathalikhani, S. Klavzar and M. Petkovsek. Vertex and edge orbits of Fibonacci and Lucas cubes, Ann. Comb, 20 (2016) 209-229.A. Graovac, T. Pisanski, On the Wiener index of a graph, J. Math. Chem, 8 (1991) 53-62.

 

[7] A. Castro, S. Klavzar, M. Mollard and Y. Rho. On the domination number and 2-packing number of Fibonacci cubes and Lucas cubes, Comput. Math. Appl, 61 (2011) 2655-2660.