# All Questions

Tagged with graph-theory mg.metric-geometry

72
questions

**1**

vote

**2**answers

117 views

### Maping of subcubes of a $(d+k)$-hypercube onto subcubes of $d$-hypercube

Denote by $Q_n$ the n-dimensional hypercube. A vertex of $Q_n$ is represented by a vector of $n$ $\{0,1\}$-bits. An edge corresponding to two vertices whose vectors differ in one coordinate is ...

**1**

vote

**1**answer

90 views

### How many nodes does a ball of radius $r$ in the Johnson graph $J(n,k)$ contain?

1) How many nodes does a ball of radius $r$ in the Johnson graph $J(n,k)$ contain (Volume)?
2) How many nodes $v$ does a ball with center $x$ of radius $r$ in the Johnson graph $J(n,k)$ contain such ...

**1**

vote

**1**answer

89 views

### Embedding a graph in $\mathbb{R}^3$ with partial geometric information

I have a connected, sparse, graph (a molecule to be specific) and I'm interested in associating 3D coordinates with the vertices. Here's the kicker: I already have coordinates for none/some/all ...

**5**

votes

**0**answers

109 views

### Which cubic graphs can be orthogonally embedded in $\mathbb R^3$?

By an orthogonal embedding of a finite simple graph I mean an embedding in $\mathbb R^3$ such that each edge is parallel to one of the three axis. To avoid trivialities, let's require that (the ...

**15**

votes

**1**answer

305 views

### Can the graph of a symmetric polytope have more symmetries than the polytope itself?

I consider convex polytopes $P\subseteq\Bbb R^d$ (convex hull of finitely many points) which are arc-transitive, i.e. where the automorphism group acts transitively on the 1-flags (incident vertex-...

**3**

votes

**1**answer

199 views

### Separating points of shifts of a finite set in the plane

Let $A\subset \mathbb{R^2}$ be a finite set such that $|A|=k^2$. Let $x_i\in \mathbb{R^2}$, $i=1,2,3,4$, be four points in the plane in general position (no three lie on any line).
Let us form the ...

**1**

vote

**1**answer

104 views

### Characterizing 1-ended graphs

I just came across the notion of ends of a space, and I wonder if the following are equivalent for $G$ a locally finite connected graph:
There exists an infinite path $v_1,v_2,\dots$ in $G$ which ...

**1**

vote

**1**answer

102 views

### Minimizing maximum distance by adding shortcuts in grid graph

My problem is to find places to put k number of shortcut edges with weight 0 to minimize maximum distance in grid graph where all edges are weighted 1!
I found a related topic to my question ...

**9**

votes

**3**answers

797 views

### Does there exist a notion of discrete riemannian metric on graph?

I would like to know if there is any notion of a discrete Riemannian metric on graphs. C. Mercat has worked on discrete Riemann Surfaces, but that's not exactly what I am working on.
To be more ...

**3**

votes

**2**answers

920 views

### Is there a lower bound for the computational complexity of the traveling salesman problem?

A (non-mathematician) acquaintance of mine recently proposed to me a polynomial-time algorithm for solving the traveling salesman problem. While I was able to point out a flaw in his approach, it did ...

**2**

votes

**0**answers

41 views

### 2-Complexes which are coarse-grained graphs

A polygonal complex $K$ is said to be 2-dimensional if the topological space it defines is a surface (boundaries are allowed). It is said to be $C$-quasi-1-dimensional (for some $C>0$) if there ...

**2**

votes

**1**answer

483 views

### Train intersection problem with unequal speeds

As shown in this question, it is trivial to schedule trains running either north-south or east-west in a square city along randomly placed (vertical and horizontal) tracks and ensure that two trains ...

**2**

votes

**1**answer

124 views

### Covering a circle with small balls centered at nodes on a tiling

In $\mathbb{R}$, we have $n$ finite sets, namely $\{A_1,A_2,\dots, A_n\}$. From them, we define a tiling:
$$
T := \{x\in \mathbb{R}^n: \forall i \in \{1,2,\dots,n\}, ~x_i\in A_i\} = \prod_{i=1}^nA_i
$$...

**3**

votes

**1**answer

601 views

### Finding the farthest point from a set of other points

I have a set of nodes in a very large graph which I call Cluster Points. I also have for each point in the graph, the distance from each point in the Cluster point set.
For example: ...

**5**

votes

**2**answers

448 views

### Another graph characteristic

This question concerns a method of drawing graphs and a graph characteristic about which I want to learn more.
Consider a connected directed graph with at least one node with in-degree 0 and one node ...