# Tagged Questions

**0**

votes

**0**answers

42 views

### Paths on Cartesian products of graphs satisfying linear constraints

Assume integers $d > r > 0$ and a connected graph $G$ with $d$ vertices. Every point on the $r$-fold Cartesian product of $G$ with itself, $G^{\square r}$, is equivalent to a dimension-$d$ ...

**10**

votes

**1**answer

257 views

### doubly-stochastic isomorphisms of graphs

A doubly stochastic matrix that commutes with the adjacency matrix of a graph is a doubly-stochastic automorphism of that graph (definition by Tinhofer 1986). Each (classical) automorphism of a graph ...

**0**

votes

**0**answers

42 views

### Edge versus vertex assignment in graphs and convex relaxtions

Consider a graph $G = (V,E)$. Let $x \in \{-1,1\}^V$ be a label assignment to vertices of the graph and $z \in \{-1,1\}^E$ be a label assignment to edges of the graph. We say that $z$ is compatible ...

**1**

vote

**2**answers

417 views

### Does Euler's formula imply bounds on the degree of vertices in a 3-polytopal graph?

A corollary of Euler's formula tells us that the edge-vertex graph of every convex 3-polyhedron must have a face with either 3, 4, or 5 edges, using an argument about the average degree of vertices.
...

**0**

votes

**1**answer

334 views

### The query concerning the Euler-Poincare formula’s generalizations

Euler's equation for polyhedral, Euler's polyhedral formula, V – E + F = 2, where V, E, and F, are the number of points, edges and faces, was discovered by Leonhard Euler in 1752. However, the basic ...

**1**

vote

**1**answer

177 views

### Weighted Polytope

I am curious if this kind of construction (or something similar) exists:
Consider a convex polytope $P$ and then consider the graph of the polytope $G(P)$ (1-skeleton). Suppose a weighting structure ...

**2**

votes

**3**answers

317 views

### Can we uniquely define a graph to have the topology of a polytope via proper edge length selection?

I'll ask you to consider a situation wherein one has a series of edges for a graph, $(e_1, e_2, ..., e_N) \in E$, each with a specifiable length $(l_1, l_2, ..., l_N) \in L$, and the goal is to insure ...

**14**

votes

**4**answers

1k views

### Can you determine whether a graph is the 1-skeleton of a polytope?

How do I test whether a given undirected graph is the 1-skeleton of a polytope?
How can I tell the dimension of a given 1-skeleton?