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

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

Hadwiger’s conjecture in the language of graph homomorphisms

Consider the following statement: (S): If G is not a complete graph, then there is a minor M of G such that M≇, and there is a graph homomorphism f:G\to M. Hadwiger’s conjecture states that for every finite simple undirected graph G, the complete graph K_{\chi(G)} is a minor of G. Since colorings G are … Read more