Wykresy, na których wszystkie najkrótsze ścieżki są unikalne

Szukam nieukierunkowanych, nieważonych połączonych wykresów , w których dla każdej pary u , v ∈ V istnieje unikalna ścieżka u → v, która realizuje odległość d ( u , v ) .$G=(V,E)$$u,v \in V$$u \rightarrow v$$d(u,v)$

Czy ta klasa grafów jest dobrze znana? Jakie inne właściwości ma? Na przykład każde drzewo jest tego rodzaju, a także każdy wykres bez równego cyklu. Istnieją jednak wykresy zawierające nawet takie cykle.

Zgodnie z systemem informacyjnym dotyczącym klas grafów i ich inkluzji wykresy te są badane pod nazwą „ grafy geodezyjne ”.

Takie wykresy są rzeczywiście geodezyjne. Wykres jest bigeodetyczny, jeśli istnieją co najwyżej dwie najkrótsze ścieżki między dowolną parą wierzchołków. Ogólnie wykres jest geodezyjny, jeśli istnieje co najwyżej k najkrótszych ścieżek między dowolną parą wierzchołków.$k$$k$

Innym przykładem wykresu geodezyjnego jest wykres blokowy. Wykres jest wykresem blokowym, jeśli można go zbudować z drzewa, zastępując każdą krawędź kliką. Odpowiednio jest to znane jako wykres akordowy bez diamentów. Diament to minus krawędź. Na przykład patrz Twierdzenie 1.1 w Le, Van Bang i Nguyen Ngoc Tuy. „Kwadrat wykresu blokowego”. Discrete Mathematics 310.4 (2010): 734–741.$K_4$