Czy jest jakiś wykres kołowy bez trójkątów i bez gwiazd, z więcej niż n krawędziami?

Próbuję znaleźć wykres z tymi właściwościami do moich badań, ale niestety nie mogę znaleźć takiego wykresu.

Czy ktoś wie, czy istnieje ten wykres lub dlaczego nie jest możliwe?

graph-theory graph-classes Rafael Oliveira Lopes
źródło

Czy możesz wyjaśnić swoją terminologię? Co to jest „zestaw bez gwiazd” i co to jest „wykres kołowy”?

Yuval Filmus

Pewnie. =) Wykres kołowy jest wykresem (bezkierunkowym), którego wierzchołki można powiązać z akordami w okręgu, tak że dwa wierzchołki sąsiadują ze sobą, jeśli odpowiednie akordy przecinają się. Oto obraz jako przykład (z Wikipedii): en.wikipedia.org/wiki/File:Circle_graph.svg I możemy powiedzieć, że wykres ma zestaw cięcia gwiazd, gdy masz wierzchołek v taki, że usunięcie v i jego sąsiadów (N [v]) z wykresu wyłącza go.

Rafael Oliveira Lopes

ISGCI ma definicje wykresu bez trójkąta i wykresu kołowego . Gwiazda cutset jest podzbiorem wierzchołków oddzielający wykresie tak, że jeden wierzchołek w znajduje się w sąsiedztwie każdej z pozostałych wierzchołków .

S

$S$

S

$S$

S

$S$

Jeffε

Ten artykuł może być odpowiedni.

Jeffε

Odpowiedzi:

Załóżmy, że to wykres kołowy niezawierający trójkątów i bez gwiazd. Pokażę, że nie zawiera wierzchołka o stopniu większym niż 2. Dlatego ma co najwyżej krawędzi. $G$ $G$ $G$ $n$

Rozważmy reprezentację okręgu z . Zestaw akordów jest równoległy, jeśli nie krzyżują się żadne dwa, ale linia przecina wszystkie akordy. $C$ $G$

Właściwość 1 : nie ma 3 równoległych akordów. $C$

Dowód . Załóżmy, że ma 3 równoległe akordy. Przeprowadź wierzchołek odpowiadający środkowemu akordowi . Zatem jest zbiorem. Dowodzi to własności. $C$ $v$ $N[v]$

Dla zachowania sprzeczności załóżmy, że ma wierzchołek stopnia co najmniej 3. Wtedy akord odpowiadający przecina 3 inne akordy. Ponieważ te 3 akordy przecinają jedną linię, są albo równoległe, albo dwa z nich przecinają się. Ze względu na Właściwość 1 dwa z nich przecinają się, co oznacza, że ich wierzchołki tworzą trójkąt z , co zaprzecza trójkąta. $G$ $v$ $v$ $v$ $G$

Serge Gaspers
źródło

Nie sądzę, aby proroctwo 1 było prawdziwe. Rozważ akordy tworzące boki zwykłego gona, z okręgiem nieco większym, aby zawierał gon, ale nie zawierał żadnych innych skrzyżowań tych boków.

n

$n$

n

$n$

David Eppstein

Ok, poprawione, myślę, że to działa i jest prostsze niż mój dowód.

David Eppstein

Nie, taki wykres nie istnieje. Aby zobaczyć, dlaczego nie, załóżmy, że mamy wykres kołowy zdefiniowany przez zestaw akordów bez trójkątów. Niech będzie liczbą wierzchołków wykresu kołowego (lub liczbą akordów), zaś będzie liczbą krawędzi wykresu (przecięcie dwóch akordów). Następnie łatwa indukcja liczby akordów pokazuje, że układ akordów ma dokładnie powierzchni. Istnieją jednak co najwyżej ścian, które dotykają okręgu (mniej, jeśli niektóre twarze dotykają koła więcej niż raz), więc jeśli to muszą być co najmniej dwie wewnętrzne ściany układu. Niech będzie dowolną najkrótszą ścieżką na podwójnym wykresie układu ( wykres kwadratowy $n$ $m$ $m+n+1$ $2n$ $m>n$ $p$ ) z jednej takiej powierzchni na drugą, i niech będzie dowolnym akordem podwójnym do krawędzi . Następnie zestaw gwiazd wycięty przez oddziela niektóre akordy ograniczające twarz na jednym końcu od niektórych akordów ograniczających twarz na drugim końcu. $c$ $p$ $c$ $p$

David Eppstein
źródło