Publication

On Simplices in Diameter Graphs in R-4

Andrei Kupavskii
2017
Journal Articles

Abstract

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.

Official source

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

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Andrei Kupavskii
2017
Journal Articles

Abstract

Official source

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

About this result

Related concepts (32)

Vertex (graph theory)

In discrete mathematics, and more specifically in graph theory, a vertex (plural vertices) or node is the fundamental unit of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges (unordered pairs of vertices), while a directed graph consists of a set of vertices and a set of arcs (ordered pairs of vertices). In a diagram of a graph, a vertex is usually represented by a circle with a label, and an edge is represented by a line or arrow extending from one vertex to another.

Vertex figure

In geometry, a vertex figure, broadly speaking, is the figure exposed when a corner of a polyhedron or polytope is sliced off. Take some corner or vertex of a polyhedron. Mark a point somewhere along each connected edge. Draw lines across the connected faces, joining adjacent points around the face. When done, these lines form a complete circuit, i.e. a polygon, around the vertex. This polygon is the vertex figure. More precise formal definitions can vary quite widely, according to circumstance.

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.

Related publications (32)

On Simplices in Diameter Graphs in R-4

Chat with 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