Eleganckie etykiety na krawędziach

W teorii grafów etykietowanie z wdziękiem krawędzi jest rodzajem etykietowania grafów dla prostych , połączonych grafów , w których żadne dwie różne krawędzie nie łączą tych samych dwóch różnych wierzchołków i żadna krawędź nie łączy wierzchołka ze sobą.

Etykiety pełne wdzięku zostały po raz pierwszy wprowadzone przez Sheng-Ping Lo w jego przełomowym artykule.

Definicja

Mając graf G , oznaczamy zbiór krawędzi przez E ( G ) , a wierzchołki przez V ( G ) . Niech q będzie licznością E ( G ) , a p będzie licznością V ( G ) . Po podaniu etykiet krawędzi wierzchołek u grafu jest oznaczany sumą etykiet incydentnych z nim krawędzi, modulo p . Lub, w symbolach, indukowane etykietowanie na wierzchołku u jest podane przez

${\ Displaystyle V (u) = \ Sigma E (e) \ mod | V (G) |}$

gdzie V ( u ) jest etykietą wierzchołka, a E ( e ) jest przypisaną wartością krawędzi padającej na u .

Problem polega na znalezieniu takiego oznakowania krawędzi, aby wszystkie etykiety od 1 do q były użyte raz, a indukowane etykiety na wierzchołkach przebiegały od 0 do p – 1 . Innymi słowy, wynikowy zbiór etykiet krawędzi powinien wynosić {1, 2, …, q } i {0, 1, …, p – 1} dla wierzchołków.

O grafie G mówi się, że jest pełen gracji na krawędziach, jeśli dopuszcza etykietowanie pełne gracji na krawędziach.

Przykłady

Cykle

Pełen wdzięku napis C ₅

Rozważmy cykl z trzema wierzchołkami, C ₃ . To jest po prostu trójkąt. Można oznaczyć krawędzie 1, 2 i 3 i sprawdzić bezpośrednio, że wraz z indukowanym etykietowaniem na wierzchołkach daje to etykietowanie pełne wdzięku. Podobnie jak w przypadku ścieżek, C _m jest płynne na krawędziach, gdy m jest nieparzyste, a nie, gdy m jest parzyste.

Ścieżki

Rozważmy ścieżkę z dwoma wierzchołkami, P ₂ . Tutaj jedyną możliwością jest oznaczenie jedynej krawędzi w grafie 1. Indukowane etykietowanie na dwóch wierzchołkach to oba 1. Tak więc P ₂ nie jest pełne gracji krawędzi.

Dołączenie krawędzi i wierzchołka do P ₂ daje P ₃ , ścieżkę z trzema wierzchołkami. Oznacz wierzchołki przez v ₁ , v ₂ i v ₃ . Oznacz dwie krawędzie w następujący sposób: krawędź ( v ₁ , v ₂ ) jest oznaczona jako 1, a ( v ₂ , v ₃ ) oznaczona jako 2. Indukowane oznaczenia na v ₁ , v ₂ i v ₃ wynoszą wtedy 1, 0 i 2 odpowiednio. To jest etykietowanie pełne wdzięku, więc P ₃ jest pełne wdzięku.

Podobnie można sprawdzić, czy P ₄ nie jest wdzięczne na krawędziach.

Ogólnie rzecz biorąc, P _m jest pełne gracji na krawędziach, gdy m jest nieparzyste, i nie jest pełne gracji na krawędziach, gdy jest parzyste. Wynika to z warunku koniecznego gracji brzegowej.

Warunek konieczny

Lo podał warunek konieczny, aby graf z krawędziami q i wierzchołkami p był pełen wdzięku: q ( q + 1) musi być przystający do p ( p – 1) / 2 mod p . w symbolach:

${\ Displaystyle q (q + 1) \ równoważnik {\ Frac {p (p-1)} {2}} \ mod p.}$

Jest to określane jako stan Lo w literaturze. Wynika to z faktu, że suma etykiet wierzchołków jest dwukrotnie większa od sumy krawędzi, modulo p . Jest to przydatne do obalenia, że ​​graf jest pełen wdzięku na krawędziach. Na przykład, można zastosować to bezpośrednio do przykładów ścieżek i cykli podanych powyżej.

Dalsze wybrane wyniki

• Graf Petersena nie jest pełen wdzięku na krawędziach.
• Wykres gwiazdowy ( $węzeł$ centralny i m nóg o długości 1) jest pełen wdzięku na krawędziach, gdy m jest parzyste a nie, m jest nieparzyste .
• Wykres przyjaźni jest pełen wdzięku na $krawędziach, gdy$ m a nie, gdy jest parzyste.
• Regularne drzewa , (głębokość n z każdym węzłem innym niż liść emitującym $)$ wierzchołków są pełne gracji na krawędziach, gdy jest równe dla dowolnej wartości n , ale nie pełne gracji na krawędziach, gdy m to jest dziwne.
• Kompletny wykres na n wierzchołkach, jest pełen wdzięku na krawędziach, chyba że $n$ jest pojedynczo parzyste , ${\ displaystyle n = 2 \ mod$ .
• Graf drabinkowy nigdy nie jest pełen wdzięku na krawędziach.