Die Beziehungen zwischen dem Diameter eines Graphen und dem Minimum der k-Grade seiner Knotenpunkte
Die Beziehungen zwischen dem Diameter eines Graphen und dem Minimum der \(k\)-Grade seiner Knotenpunkte
In einer vorangehenden Arbeit wurde folgender Satz bewiesen: Es sei \( G=(X, U) \) ein ungerichteter, endlicher, zusammenhängender, schlingenloser Graph ohne Mehrfachkanten, \( g_{k} \) der kleinste \( k \)-Grad seiner Knotenpunkte, \( h \) die kleinste natürliche Zahl, \( h \geq 2 \), so dass die Ungleichung \( g_{k} \geq\left[\frac{\mid x_{1}}{h}\right] \) erfüllt ist. Dann gilt für den Diameter \( D(G) \) des Graphen \( G \) die Ungleichung (1) \( D(G) \leq(2 k+1)(h-1)-1 \). Dabei versteht man unter dem \( k \)-Grad \( g_{k}(x) \) eines Knotenpunktes \( x \in X \) die Anzahl der Knotenpunkte \( y \) aus \( X \) für welche die Ungleichung \( 1 \leq d(x, y) \leq k \) gilt. In der vorliegenden Arbeit wird folgender Satz bewiesen: Eine notwendige Bedingung dafir, daß in den Voraussetzungen des obigen Satzes für \( h \geq 3 \) die Gleichheit \( D(G)=(2 k+1)(h-1)-1 \) gilt, ist: \( \left[\frac{|x|}{h}\right] \geq 2 k \) Es wird ebenfalls gezeigt, daß für die komplementären Graphen der sogenannten Mooreschen Graphen in (1) mit \( {k}=1, {~h}=2 \) das Gleichheitszeichen gilt. Ist \(G(X,U)\) ein Moorescher Graph mit \( g \geq 2\), \(D(G) \geq 2 \), so ist sein komplementärer Graph \(\bar{G}=(X, \bar{U}) \) ein regulärer, Hamiltonscher Graph mit \( D(\bar{G})=2 \). [Hierbei ist \( g=\max _{x \in x} g(x) \) mit \( g(x)=g_{1}(x) \) gesetzt.]
This page was built for publication: Die Beziehungen zwischen dem Diameter eines Graphen und dem Minimum der \(k\)-Grade seiner Knotenpunkte
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5607115)