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