Existe algum gráfico de círculo sem triângulo, sem estrela em estrela e com mais de n arestas?

Estou tentando encontrar um gráfico com essas propriedades para meus estudos, mas infelizmente não consigo encontrar esse gráfico.

Alguém sabe se existe esse gráfico ou por que é impossível existir?

graph-theory graph-classes Rafael Oliveira Lopes
fonte

Você pode explicar sua terminologia? O que é "sem estrelas" e o que é "gráfico circular"?

Yuval Filmus

Certo. =) Um gráfico circular é um gráfico (não direcionado) cujos vértices podem ser associados a acordes em um círculo, de modo que dois vértices sejam adjacentes se os acordes correspondentes se cruzarem. Aqui está uma imagem como exemplo (da Wikipedia): en.wikipedia.org/wiki/File:Circle_graph.svg E podemos dizer que um gráfico tem uma estrela-cutset quando você tem um vértice v, de forma a remover v e seus vizinhos (N [v]) do gráfico o desconecta.

Rafael Oliveira Lopes

O ISGCI possui definições de gráfico sem triângulo e círculo . Uma estrela-cutset é um subconjunto de vértices que separa o gráfico, de tal modo que um vértice em é adjacente a cada outro vértice em .

S

$S$

S

$S$

S

$S$

Jeffε

Este artigo pode ser relevante.

Jeffε

Respostas:

Suponha que é um gráfico de círculo sem triângulo e sem estrelas. Mostrarei que não contém vértices com grau maior que 2. Portanto, possui no máximo arestas. $G$ $G$ $G$ $n$

Considere-se uma representação do círculo de . Um conjunto de acordes é paralelo se nenhum deles se cruzar, mas houver uma linha cruzando todos os acordes. $C$ $G$

Propriedade 1 : não possui 3 acordes paralelos. $C$

Prova . Suponha que tenha 3 acordes paralelos. Conduza o vértice correspondente ao acorde do meio. Então, é um cutset. Isso prova a propriedade. $C$ $v$ $N[v]$

Por uma questão de contradição, suponha que tenha um vértice de grau pelo menos 3. Em seguida, o acorde correspondente a cruza outros 3 acordes. Como esses três acordes cruzam uma linha, eles são paralelos ou dois deles se cruzam. Devido à Propriedade 1, dois deles se cruzam, o que significa que seus vértices formam um triângulo com , o que contradiz ser livre de triângulo. $G$ $v$ $v$ $v$ $G$

Serge Gaspers
fonte

Eu não acho que a propriedade 1 seja verdadeira. Considere os acordes que formam os lados de um -gon regular , com o círculo um pouco maior para que ele contenha o -gon, mas não contenha outros cruzamentos desses lados.

n

$n$

n

$n$

David Eppstein

Ok, como corrigido, acho que isso funciona e é mais simples que a minha prova.

David Eppstein

Não, esse gráfico não existe. Para ver por que não, suponha que tenhamos um gráfico circular definido por um conjunto de acordes sem triângulo. Seja o número de vértices do gráfico circular (ou o número de acordes) e seja o número de arestas do gráfico (cruzamentos de dois acordes). Então, uma fácil indução do número de acordes mostra que a disposição dos acordes tem exatamente faces. No entanto, existem no máximo faces que tocam o círculo (menos se algumas faces tocam o círculo mais de uma vez); portanto, se , deve haver pelo menos duas faces internas do arranjo. Seja caminho mais curto no gráfico duplo do arranjo (um gráfico quadrado $n$ $m$ $m+n+1$ $2n$ $m>n$ $p$ ) de uma face para outra e seja qualquer acorde duplo com uma aresta de . Em seguida, o conjunto de estrelas induzido por separa alguns dos acordes que limitam a face em uma extremidade de de alguns dos acordes que limitam a face na outra extremidade. $c$ $p$ $c$ $p$

David Eppstein
fonte