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

9

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?

Rafael Oliveira Lopes
fonte
3
Você pode explicar sua terminologia? O que é "sem estrelas" e o que é "gráfico circular"?
Yuval Filmus
11
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
11
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 SSSS
Jeffε
Este artigo pode ser relevante.
Jeffε

Respostas:

11

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 nGGGn

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.GCG

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.v N [ v ]CvN[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.v v v GGvvvG

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. nnn
David Eppstein
Ok, como corrigido, acho que isso funciona e é mais simples que a minha prova.
David Eppstein
8

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 quadradom m + n + 1 2 n m > n p cnmm+n+12nm>np) 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.cc ppcp

David Eppstein
fonte