Is every 1-skeleton of a 4-tope Steinitzian?

Call a graph “polyhedral” if it is simple, planar, and 3-connected. For example, the 1-dimensional skeleton of every 3-dimensional convex polytope, regarded as a graph, is polyhedral. By a theoreom of Steinitz, polyhedral graphs are exactly the graphs which appear as 1-skeleta of 3-dimensional convex polytopes. Call a graph “Steinitzian” if it has a spanning … Read more

The degree/diameter problem for even girth graphs starting with upper bound

I posted this on stackexchange but due to a lack of response there I am posting here. Let G be a graph with girth g, minimal degree δ, maximal degree Δ, and diameter D. Define n0(g,δ):={1+δ+δ(δ−1)+⋯+δ(δ−1)g−32, if g is odd2+2(δ−1)+⋯+2(δ−1)g2−1, if g is even.. Suppose the girth g is odd. It can be shown that the number of vertices of G … Read more

Finding closest set of K disjoint hyperspheres to a point in $\mathbb{R}^n$ with uniform radius

I am interested in the following problem: in $\mathbb{R}^n$, we have $N$ overlapping hyperspheres all with the same radius. Given a point $p$ in $\mathbb{R}^n$, the objective is to find the $K$ non overlapping hyperspheres whose centers are the closest to $p$ under the Euclidean metric (although I’m eventually interested in exploring other metrics as … Read more

Edit distance vs. canonical adjacency matrix distance

Let G and G′ be two simple random graphs on the same set of nodes. Let dedit be the edit distance between G and G′. Let A and A′ be the adjacency matrices of the graphs G and G′ that result from the canonical labeling algorithm Nauty. Moreover, let dmatrix=12‖. What is the difference (in … Read more

A relaxation of proper coloring

I am wondering if the following relaxation of proper coloring appears somewhere. I have tried some searching and have found a few relaxations of proper coloring, but none the coincides with what I have below. Let G=(V,E) be a graph (or H=(V,E) a hypergraph). Let E=A1⊎A2⊎⋯⊎Al be a partition. I am looking at coloring of … Read more

Finiteness for 2-dimensional contractible complexes

While thinking about graph-complex and related operadic stuff, I found a quite interesting (at least for me) question. However, I’m a novice in the algebraic topology, so I’m unable to resolve it by myself. Definition Let us call a (pure) n-dimensional polyhedral complex the topological space glued from a finite number of n-dimensional (convex) polyhedra … Read more

Minimal algebraic degree of symmetric unit distance embedding of Heawood graph

I’m looking at embeddings of the Heawood graph in the plane as unit distance graph. Apparently the first such embedding was given by Gerbracht, 2009 and has algebraic (over the rationals) coordinates of maximum degree $79$ . I thought it would be nice to have an embedding that also realizes at least one of the … Read more

A color interpolation lemma

I need the following “color interpolation lemma”. Actually I know a way to prove it, but I’m not very satisfied with that proof. Lemma. Let $G=(V,E)$ be a (properly) colored graph with colors $1, \dots, n$, and let $V = V_1 \cup \dots \cup V_n$ be the corresponding partition of the vertices. Let $\mu$ be … Read more

Counting loops in degree: 1 or 2?

Here’s what seems to be an annoying technicality when dealing with loops in graphs. In the literature on expander graphs (and surely not only), it seems to be the convention that a loop at vertex v in an undirected graph contributes 1 to the degree, and 1 to the corresponding diagonal entry in the adjacency … Read more

How can I determine if this decomposition of K33,33K_{33,33} comes from an alpha-labelling?

The graph depicted below, when cyclically rotated, gives a decomposition of K33,33. It has 22 vertices, 33 edges, and is 3-regular (i.e., cubic). It was found by my computer. We can verify the decomposition claim by checking that each edge length occurs exactly once. It is therefore possible that this decomposition is equivalent to an … Read more