Der starke chromatische Index kompletter Halin-Grafen

Die starke Kantenfärbung eines Grafen G ist eine Zuordnung von Farben zu den Kanten von G, so dass zwei verschiedene Kanten unterschiedlich gefärbt sind, wenn sie an einer gemeinsamen Kante inzident sind oder einen Endpunkt teilen. Der starke chromatische Index eines Grafen G, bezeichnet als χs′(G), ist die minimale Anzahl von Farben, die für eine starke Kantenfärbung von G benötigt werden. In diesem Papier beweisen wir die folgenden zwei Theoreme: (1) Wenn G=T∪C ein kompletter Halin-Graf mit Δ=4 ist, der benachbarte Scheitelpunkte maximaler Ordnung enthält, dann gilt χs′(G)≤χs′(T)+1=2Δ. Insbesondere gilt, wenn T ein regulärer Baum ist, χs′(G)=χs′(T)+1=2Δ. (2) Wenn G=T∪C ein kompletter Halin-Graf mit Δ≥5 und G≠Wn ist, dann gilt χs′(G)=χs′(T)=2Δ−1, wenn T ein regulärer Baum ist. Wir erweitern die Ergebnisse zur starken Kantenfärbung für vollständige kubische reguläre Halin-Grafen, die von W.C. Shiu und W.K. Tam untersucht wurden, und verbessern die obere Grenze für den starken chromatischen Index allgemeinener Halin-Grafen, die von Wei Yang und Baoyindureng Wu festgestellt wurde.