Mathematica Eterna
Offener Zugang

Abstrakt

Eine kurze Anmerkung zur Graphenfunktionalität

Jessica, J

Die Funktionalität eines Graphen G ist dort gegeben, wo die meisten aller abgeleiteten Teilgraphen H von Funktionalität erfasst werden. Sie wird in Analogie zur Entartung beschrieben, die verallgemeinert: Wenn wir in der obigen Definition durch ersetzen, erhalten wir die Entartung von G. Die Verwendung der meisten abgeleiteten Teilgraphen stellt sicher, dass die Funktionalität nicht zunimmt, wenn wir abgeleitete Teilgraphen verwenden. Wie bei vielen anderen Graphparametern wird der Begriff der Graphenfunktionalität nützlich, wenn sein Wert klein ist, d. h. endlich ist, unabhängig von der Größe des Graphen. Vor allem Graphen mit kleiner Funktionalität lassen sich kompakt darstellen, wie in [3] gezeigt wurde. In diesem Artikel wird der Begriff der Graphenfunktionalität nicht formal beschrieben; die dort bewiesenen Ergebnisse implizieren jedoch, dass Graphen mit endlicher Funktionalität durch binäre Wörter der Länge dargestellt werden können