Eine Charakterisierung der Graphen, deren dritte Potenz 2-hamiltonsch ist

✍ Scribed by Günter Schaar

• Book ID: 102942235
• Publisher: John Wiley and Sons
• Year: 1975
• Tongue: English
• Weight: 649 KB
• Volume: 66
• Category: Article
• ISSN: 0025-584X
• DOI: 10.1002/mana.19750660114

✦ Synopsis

0. I m AnschluB an Untersuchungen von CHARTRAND und KAPOOR [l] wurde in [4] gezeigt, daS fur einen zusammenhangenden briickenlosen Graphen G mit n 2 5 Knoten die dritte Potenz 6 3 stets 2-hamiltonsch sein muB. Es erhebt sich die Frage, ob man in diesem Ergebnis die Voraussetzung der Briickenlosigkeit so weit abschwachen kann, daS sich eine die Graphen mit 2-hamiltonscher dritter Potenz kennzeichnende Bedingung ergibt. Die Satze 1 und 2 der vorliegenden Arbeit liefern eine vollstandige Antwort auf diese Fragestellung. Hinsichtlich der im Folgenden verwendeten Terminologie und Notation verweisen wir auf [4] ; insbesondere betrachten wir nur endliche, ungerichtete, schlichte Graphen. Zusatzlich definieren wir fiir einen zusammenhangenden Graphen G : Ein Knoten a soll ein reiner Bruckenknoten genannt werden genau dann, wenn jede mit a inzidierende Kante eine nichttriviale Briicke ist. Eine aus drei verschiedenen Knoten a, b, c bestehende Menge (a, b, c ) heiBe ein reines Bruckendreieck genau dann, wenn ( I ) ( a , b ) , (a, c ) und (b, c) Kanten sind, (2) jede weiterevon den unter (1) aufgefiihrten verschiedene -Kante, die mit einem der drei Knoten a, b, c inzidiert, eine nichttriviale Briicke ist, (3) jeder der drei Knoten a , b, c mindestens die Valenz 3 besitzt. Dabei bezeichnet die Valenz eines Knotens a in einem Graphen G wie ublich die Anzahl der mit a inzidierenden Kanten. SchlieBlich soll fur einen Weg s in einem Graphen, der den Knoten a mit dem Knoten b verbindet, die abkiirzende Schreibweise a(. * a ) b vereinbart werden. (u(. 7 0 ) a bedeutet den trivialen Weg a.