# Tagged Questions

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$ ...
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 ...
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 ...
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. ...
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 ...
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 ...
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 ...