Girth in graphs (Q792338)

Sei \(\Gamma_a\) die Klasse der endlichen zusammenhängenden Graphen vom Minimalgrad mindestens \(a\), und sei \(\Gamma_{a,k}\) die Klasse der \(G \in \Gamma_a\) mit der Taillenweite mindestens \(k\). Satz 1: Für \(q \geq q_n\) ist jedes \(G \in \Gamma_{3,q}\) auf \(K_n\) kontrahierbar. Der Verf. führt den Begriff \(k\)-zyklisch-eckenzusammenhängend ein. Satz 2: Jedes \(G \in \Gamma_{3,4k-6}\) enthält einen induzierten Teilgraph \(H\), der aus einem \(k\)-zyklisch-eckenzusammenhängenden Graph \(H^*\) entsteht, indem jede Kante von \(H^*\) durch höchstens \(2k-3\) Ecken unterteilt wird. Weiter wird gezeigt, daß in einem \(n\)-zyklisch- eckenzusammenhängenden Graph \(G \in \Gamma_3\) für hinreichend großes \(n\) {\parindent=6mm \begin{itemize}\item[a)]durch je \(k\) unabhängige Kanten in \(G\) ein Kreis existiert und \item[b)]\(G\) (im Fall \(k \geq 2)\) Kreise jeder geraden Länge modulo \(k\) enthält. \end{itemize}} Ähnliche Resultate betreffen die Existenz gewisser Konfigurationen in \(n\)-zyklisch-eckenzusammenhängenden Graphen für große \(n\). Im letzten Paragraphen werden folgende Ergebnisse erhalten. Satz 3: Ein \(G \in \Gamma_{4,5}\) mit \(n\) Ecken, wobei \(n/(\log n)_4 > 2^{13}(k-1)^2\), enthält \(k\) disjunkte Kreise gleicher Länge. Ein ähnliches Resultat bezieht sich auf die \(G \in \Gamma_{3,7}\). Satz 4: Zu \(k\) existiert \(m_k\), so daß jeder Graph \(G \in \Gamma_{3k+1}\) mit \(n \geq m_k\) Ecken \(k\) disjunkte Kreise gleicher Länge hat.