Articles

Rad-Graph

Diskrete Mathematik > Graphentheorie > Einfache Graphen > Kegel-Graphen >
Diskrete Mathematik > Graphentheorie > Einfache Graphen > Anmutige Graphen >
Diskrete Mathematik > Graphentheorie > Einfache Graphen > Integralgraphen >

DOWNLOAD Mathematica NotebookWheelGraphs

Wie in dieser Arbeit definiert, ein Radgraph W_n der Ordnung n, manchmal einfach n-Rad genannt (Harary 1994, p. 46; Pemmaraju und Skiena 2003, S. 248; Tutte 2005, S. 78), ist ein Graph, der einen Zyklus der Ordnung n-1 enthält und bei dem jeder Graphknoten im Zyklus mit einem anderen Graphknoten verbunden ist, der als Nabe bezeichnet wird. Die Kanten eines Rades, die die Nabe einschließen, werden Speichen genannt (Skiena 1990, S. 146). Das Rad W_n kann als Graphenverbindung K_1+C_(n-1) definiert werden, wobei K_1 der Singleton-Graph und C_n der Zyklus-Graph ist, was ihn zu einem (n,1)-Kegel-Graphen macht.

Es gibt zwei Konventionen für die Indizierung von Rad-Graphen, wobei einige Autoren (z.B., Gallian 2007) nehmen die Konvention an, dass W_n den Radgraphen auf n+1 Knoten bezeichnet.

Der Tetraeder-Graph (d.h. K_4) ist isomorph zu W_4, und W_5 ist isomorph zum vollständigen dreiteiligen Graphen K_(1,2,2). Im Allgemeinen ist der n-Rad-Graph das Skelett einer (n-1)-Pyramide.

W_5 ist einer der beiden Graphen, die man erhält, wenn man zwei Kanten aus dem Pentatop-Graphen K_5 entfernt, der andere ist der Haus-X-Graph.

Rad-Graphen sind anmutig (Frucht 1979).

Der Radgraph W_n hat für n=7 die Graphendimension 2 (und ist damit eindimensional) und ansonsten die Dimension 3 (und damit nicht eindimensional) (Erdős et al. 1965, Buckley und Harary 1988).

Jeder Radgraph ist ein selbstdualer Graph.

Radgraphen können in der Wolfram Language mit WheelGraph konstruiert werden. Vorberechnete Eigenschaften einer Reihe von Radgraphen sind über GraphData verfügbar.

WheelGraphCycles4WheelGraphCycles5

Die Anzahl der Graphzyklen im Radgraphen W_n ist gegeben durch n^2-3n+3, oder 7, 13, 21, 31, 43, 57, … (OEIS A002061) für n=4, 5, ….

In einem Radgraphen hat die Nabe den Grad n-1, und andere Knoten haben den Grad 3. Radgraphen sind 3-verbunden. W_4=K_4, wobei K_4 der vollständige Graph der Ordnung 4 ist. Die chromatische Zahl von W_n ist

 chi(W_n)={3 for n odd; 4 for n even.
(1)

Der Radgraph W_n hat das chromatische Polynom

 pi(x)=x.
(2)