Construção de gráficos em que cada par de vértices tem um único vizinho comum

19

Seja um gráfico simples em vértices sem vértice do grau . Suponha que, para quaisquer dois vértices de , exista um vértice exclusivo adjacente a ambos. É um exercício de A Course in Combinatorics , van Lint e Wilson, para provar que esse gráfico é regular.Gn(n>3)n-1 1G

Minha pergunta, no entanto, é se gráficos que satisfazem as restrições dadas existem. Ao discutir o exercício original durante uma sessão de solução de problemas, alguém perguntou se poderíamos criar um exemplo de gráfico em que cada par de vértices tem um vizinho comum único e não há vértices globais. Também não conseguimos apresentar um exemplo ou procedimento concreto para a construção, nem estabelecemos uma prova de que nenhum gráfico possui essas propriedades.

Alguma sugestão?

Nota: para provar que esse gráfico é regular, ele se mostra bastante direto, a idéia aproximada é emparelhar os vizinhos de cada par de vértices usando os critérios único-comum-vizinho para estabelecer o fato de que cada par de os vértices têm o mesmo grau e, em seguida, um argumento de transitividade, com a ajuda da restrição de não-global-vértice, nos dá que o gráfico é regular.

Neeldhara
fonte

Respostas:

17

Se você se livrar da condição "sem vértice de grau ", os gráficos com a propriedade de que todos os dois vértices têm exatamente um vizinho comum são exatamente os gráficos de amizade (um conjunto de triângulos colados em um vértice comum); como o artigo vinculado descreve, esse é um teorema de Erdős, Rényi e Sós. Mas, obviamente, todos esses gráficos têm um vértice de grau n - 1 ; o único regular é um triângulo. Portanto, a resposta para sua pergunta é que não existe um gráfico com a propriedade vizinha comum e sem um vértice grau n - 1 .n-1 1n-1 1n-1 1

David Eppstein
fonte
Por que obrigado - isso é excelente. Também explica toda a dificuldade que estávamos enfrentando na construção desses gráficos sem o vértice global!
Neeldhara 29/08