Publication

On Simplices in Diameter Graphs in R-4

Andrei Kupavskii
2017
Journal Articles

Résumé

A graph G is a diameter graph in R-d if its vertex set is a finite subset in R-d of diameter 1 and edges join pairs of vertices a unit distance apart. It is shown that if a diameter graph G in R-4 contains the complete subgraph K on five vertices, then any triangle in G shares a vertex with K. The geometric interpretation of this statement is as follows. Given any regular unit simplex on five vertices and any regular unit triangle in R-4, then either the simplex and the triangle have a common vertex or the diameter of the union of their vertex sets is strictly greater than 1.

Source officielle

https://infoscience.epfl.ch/entities/publication/7061f3d1-db62-497a-a698-f7a593f391a6

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Andrei Kupavskii
2017
Journal Articles

Résumé

Source officielle

https://infoscience.epfl.ch/entities/publication/7061f3d1-db62-497a-a698-f7a593f391a6

À propos de ce résultat

Concepts associés (32)

Sommet (théorie des graphes)

vignette|Dans ce graphe, les sommets 4 et 5 sont voisins alors que les sommets 3 et 5 sont indépendants. Le degré du sommet 4 est égal à 3. Le sommet 6 est une feuille. En théorie des graphes, un sommet, aussi appelé nœud et plus rarement point, est l'unité fondamentale d'un graphe. Deux sommets sont voisins s'ils sont reliés par une arête. Deux sommets sont indépendants s'ils ne sont pas voisins. alt=A small example network with 8 vertices and 10 edges.|vignette|Réseau de huit sommets (dont un isolé) et 10 arêtes.

Figure de sommet

En géométrie, une figure de sommet d'un sommet donné d'un polytope est, de façon intuitive, l'ensemble des points directement reliés à ce sommet par une arête. Ceci s’applique également aux pavages infinis, ou pavages remplissant l’espace avec des cellules polytopiques. De façon plus précise, une figure de sommet pour un n-polytope est un (n-1)-polytope. Ainsi, une figure de sommet pour un polyèdre est une figure polygonale, et la figure de sommet pour un polychore est une figure polyèdrique.

Vertex cover

In graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices that includes at least one endpoint of every edge of the graph. In computer science, the problem of finding a minimum vertex cover is a classical optimization problem. It is NP-hard, so it cannot be solved by a polynomial-time algorithm if P ≠ NP. Moreover, it is hard to approximate – it cannot be approximated up to a factor smaller than 2 if the unique games conjecture is true. On the other hand, it has several simple 2-factor approximations.

Afficher plus

Publications associées (32)

Afficher plus

On Simplices in Diameter Graphs in R-4

Chattez avec Graph Search

The connection of the acyclic disconnection and feedback arc sets - On an open problem of Figueroa et al

The Power of Two Matrices in Spectral Algorithms for Community Recovery

On the boundedness of n-folds with κ(X) = n - 1