Planar Hypotraceable Graph

 

A planar hypotraceable graph is a hypotraceable graph that is also planar. A number of planar hypotraceable graphs are illustrated above.

Using a theorem of Thomassen (1974), the Wiener-Araya graph on 42 vertices can be used to construct a planar hypotraceable graph on 162 vertices, smaller than the 186-vertex graph obtained from the 48-Zamfirescu graph using Thomassen's construction. These graphs are implemented in the Wolfram Language as GraphData[{" src="https://mathworld.wolfram.com/images/equations/PlanarHypotraceableGraph/Inline1.svg" style="height:21px; width:6px" />"PlanarHypohamiltonian", 162}" src="https://mathworld.wolfram.com/images/equations/PlanarHypotraceableGraph/Inline2.svg" style="height:21px; width:6px" />] and GraphData[{" src="https://mathworld.wolfram.com/images/equations/PlanarHypotraceableGraph/Inline3.svg" style="height:21px; width:6px" />"PlanarHypohamiltonian", 186}" src="https://mathworld.wolfram.com/images/equations/PlanarHypotraceableGraph/Inline4.svg" style="height:21px; width:6px" />], respectively.

Jooyandeh et al. (2017) showed that there exist planar hypotraceable graphs on 154 vertices, as well as on all vertex counts greater than or equal to 156.

Using the 70-node Araya-Wiener graph, a 340-node cubic planar hypotraceable graph can be constructed (Araya and Wiener 2011).

Holton and Sheehan (1993) asked if there exists an integer  such that a cubic planar hypotraceable graph exists for every even integer , and Araya and Wiener (2011) settled the question with .

---

REFERENCES

Araya, M. and Wiener, G. "On Cubic Planar Hypohamiltonian and Hypotraceable Graphs." Elec. J. Combin. 18, 2001.

 http://www.combinatorics.org/ojs/index.php/eljc/article/view/v18i1p85/.Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, pp. 61 and 239-240, 1976.

Grotschel, M. "On the Monotone Symmetric Travelling Salesman Problem: Hypohamiltonian/Hypotraceable Graphs and Facets." Math. Operations Res. 5, 285-292, 1980.

Grünbaum, B. "Vertices Missed by Longest Paths or Circuits." J. Combin. Th. A 17, 31-38, 1974.

Holton, D. A. and Sheehan, J. The Petersen Graph. Cambridge, England: Cambridge University Press, 1993.

Jooyandeh, M.; McKay, B. D.; Östergård, P. R. J.; Pettersson, V. H.; and Zamfirescu, C. T. "Planar Hypohamiltonian Graphs on 40 Vertices." J. Graph Th. 84, 121-133, 2017.

Kapoor, S. F.; Kronk, H. V.; and Lick, D. R. "On Detours in Graphs." Canad. Math. Bull. 11, 195-201, 1968.

Thomassen, C. "Hypohamiltonian and Hypotraceable Graphs." Disc. Math. 9, 91-96, 1974.

Walter, H. "Über die Nichtexistenz eines Knotenpunktes, durch den alle längsten Wege eines Graphen gehen." J. Combin. Th. 6, 1-6, 1969.

Wiener, G. and Araya, M. "The Ultimate Question." 20 Apr 2009.

 http://arxiv.org/abs/0904.3012.Wiener, G. and Araya, M. "On Planar Hypotraceable Graphs." J. Graph Th. 67, 55-68, 2011.

اخر الاخبار

اخبار العتبة العباسية المقدسة

قسم صناعة الشبابيك يستعرض أعماله للمشاركين في البرنامج المركزي الأسبوعي

جامعة الكفيل تنظم حملة للتبرع بالدم للأطفال المصابين بالثلاسيميا والأورام السرطانية

قسم الشؤون الفكرية يصدر العدد 55 من مجلة العميد المحكمة

المجمع العلمي يجري اختبار القبول للمتقدمين إلى دورة ربيع القرآن في كربلاء

المزيد

الآخبار الصحية

كنز غذائي على طبقك.. ماذا تفعل السبانخ بجسمك؟

ما لا يتوقعه أحد.. "سر غذائي" في الجبن الدسم

لتحسين الهضم والنوم.. هذا أفضل وقت لتناول العشاء

10 طرق بسيطة وغير مألوفة لحرق المزيد من السعرات يوميا

المزيد

الآخبار التكنلوجية

سابقة بعالم الطيران.. طائرة تقرر الهبوط بنفسها بعد ظرف طارئ

"الإنفلونزا الخارقة" تكتسح دول العالم.. وتثير قلقا كبيرا

مرحلة ما قبل الأعراض.. دواء جديد يستهدف "شرارة" الزهايمر

إزالة ثاني أكسيد الكربون من الغلاف الجوي.. ما دور المحيطات والبحار؟

المزيد

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength