المرجع الالكتروني للمعلوماتية
المرجع الألكتروني للمعلوماتية

الرياضيات
عدد المواضيع في هذا القسم 9761 موضوعاً
تاريخ الرياضيات
الرياضيات المتقطعة
الجبر
الهندسة
المعادلات التفاضلية و التكاملية
التحليل
علماء الرياضيات

Untitled Document
أبحث عن شيء أخر المرجع الالكتروني للمعلوماتية


Hamilton-Connected Graph  
  
1873   11:31 صباحاً   date: 28-2-2022
Author : Alspach, B
Book or Source : "Johnson Graphs are Hamilton-Connected." Ars Math. Contemporanea 6
Page and Part : ...


Read More
Date: 2-8-2016 1412
Date: 23-4-2022 1674
Date: 28-3-2022 1215

Hamilton-Connected Graph

 

HamiltonConnectedGraph

A graph G is Hamilton-connected if every two vertices of G are connected by a Hamiltonian path (Bondy and Murty 1976, p. 61). In other words, a graph is Hamilton-connected if it has a u-v Hamiltonian path for all pairs of vertices u and v. The illustration above shows a set of Hamiltonian paths that make the wheel graph W_5 hamilton-connected.

By definition, a graph with vertex count n having a detour matrix whose off-diagonal elements are all equal to n-1 is Hamilton-connected. Conversely, any graph having a detour matrix with an off-diagonal element less than n-1 is not Hamilton-connected.

All Hamilton-connected graphs are Hamiltonian. All complete graphs are Hamilton-connected (with the trivial exception of the singleton graph), and all bipartite graphs are not Hamilton-connected.

Dupuis and Wagon (2014) conjectured that all non-bipartite Hamiltonian vertex-transitive graphs are Hamilton-connected except for odd cycle graphs C_n with n>=5 and the dodecahedral graph.

A simple algorithm for determining if a graph is Hamilton-connected proceeds as follows. For all pairs (v_i,v_j) of vertices:

1. Add a new vertex .

2. Add new edges  and .

3. If this graph is not Hamiltonian, return false; otherwise, continue to next pair.

If the algorithm checks all pairs without returning false, return true.

A small modification of a theorem due to Chvátal and Erdős establishes that if alpha(G)<kappa(G) for a graph G, where alpha(G) is the independence number and kappa(G) the vertex connectivity, then G is Hamilton-connected (A. E. Brouwer, pers. comm., Dec. 17, 2012).

As a result of the theorem that for a connected regular graph G on n>1 vertices with vertex degree k and smallest graph eigenvalue s,

 alpha<=(n(-s))/(k-s),

it therefore follows that if

 (n(-s))/(k-s)<kappa,

for a connected regular graph, the graph is Hamilton-connected (A. E. Brouwer, pers. comm., Dec. 17, 2012).

Every 8-connected claw-free graph is Hamilton-connected (Hu et al. 2005), as is every Johnson graph (Alspach 2013). Chen and Quimpo (1981) proved that a connected Cayley graph on a finite Abelian group of odd order with vertex degree at least three is Hamilton-connected.

Pensaert (2002) conjectured that for n>3k with k>2, the generalized Petersen graph GP(n,k) is Hamilton-laceable if n is even and k is odd, and Hamilton-connected otherwise.

HamiltonConnectedGraphs

The numbers of Hamilton-connected simple graphs on n=1, 2, ... nodes are 1, 1, 1, 1, 3, 13, 116, ... (OEIS A057865), the first few of which are illustrated above.

Examples of Hamilton-connected graphs include antiprism graphs, complete graphs, Möbius ladders, prism graphs of odd order, wheel graphs, the truncated prism graph, truncated cubical graph, truncated tetrahedral graph, Grötzsch graph, Frucht graph, and Hoffman-Singleton graph.


REFERENCES

Alspach, B. "Johnson Graphs are Hamilton-Connected." Ars Math. Contemporanea 6, 21-23, 2013.

Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 61, 1976.

Chen, C. C. and Quimpo, N. F. "On Strongly Hamiltonian Abelian Group Graphs." In Combinatorial Mathematics. VIII. Proceedings of the Eighth Australian Conference held at Deakin University, Geelong, August 25-29, 1980 

(Ed. K. L. McAvaney). Berlin: Springer-Verlag, pp. 23-34, 1981.

Dupuis, M. and Wagon, S. "Laceable Knights." To appear in Ars Math Contemp.Hu, Z.; Tian, F.; and Wei, B. "Hamilton Connectivity of Line Graphs and Claw-Free Graphs." J. Graph Th. 50, 130-141, 2005.

Pensaert, W. P. J. "Hamilton Paths in Generalized Petersen Graphs." Thesis. Waterloo, Ontario, Canada. January 2002.

 http://etd.uwaterloo.ca/etd/wpjpensaert2002.pdf.Sloane, N. J. A. Sequence A057865 in "The On-Line Encyclopedia of Integer Sequences."




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


يعتبر علم المثلثات Trigonometry علماً عربياً ، فرياضيو العرب فضلوا علم المثلثات عن علم الفلك كأنهما علمين متداخلين ، ونظموه تنظيماً فيه لكثير من الدقة ، وقد كان اليونان يستعملون وتر CORDE ضعف القوسي قياس الزوايا ، فاستعاض رياضيو العرب عن الوتر بالجيب SINUS فأنت هذه الاستعاضة إلى تسهيل كثير من الاعمال الرياضية.

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