Über die Anzahl der von den 1-Faktoren eines Graphen überdeckten Ecken

✍ Scribed by W. Mader

• Publisher: John Wiley and Sons
• Year: 1973
• Tongue: English
• Weight: 327 KB
• Volume: 56
• Category: Article
• ISSN: 0025-584X
• DOI: 10.1002/mana.19730560120

✦ Synopsis

Eine Ecke x des Graphen G heil3e (von den I-Faktoren von G ) iiberdeckt, wenn es zu jeder mit x inzidenten Kante [x, y] einen I-Faktor von G gibt, welcher diese Kante [x, y] enthalt. Wir werden zeigen, daB die Anzahl der uberdeckten Ecken jedes 2fach zusammenhangenden Graphen G, welcher einen I-Faktor besitzt, grol3er oder gleich dem Minimalgrad n von G ist. Wenn n 2 3 gilt, dann ist die Anzahl der uberdeckten Ecken sogar groI3er als n oder es existieren n Ecken a,, . . . , u, vom Grad n in G mit N ( a I , G ) = N (a2,G) = * . . N (an, a), wobei N (a, G ) die Menge der zu a in G benachbarten Ecken bezeichne. Hieraus ergibt sich unmittelbar eine Verschlrfung der Vermutung von J. ZAKS (Vermutung 1 aus [2] bzw. Vermutung 2 aus [3]), daB jeder n-fach zusammenhangende Graph, der einen I-Faktor besitzt, n uberdeckte Ecken enthalt. 1) Wir betrachten hier nur endliche Graphen. In der Terminologie und Bezeichnung halte ich mich an [I], werde aber einiges wiederholen. Fur einen Teilgraphen H von G (Bee.: H G) sei

N ( H , G