Fix one edge $e$ of the graph (1-skeleton) of an icosahedron. By a computer search, I found that there are 1024 Hamiltonian cycles that include $e$. [But see edit below re directed …

Many graph properties can be described by listing a set of graphs that are forbidden as subgraphs. For example, a triangle-free graph is a graph which does not have $K_3$ (the co …

Suppose you have a 100-edge connected graph (e.g. an infrastructure network). You want to delete the edges of a spanning tree, any spanning tree you choose (e.g. to sell a connecte …

This question arose while I was trying to work out examples for the second question of this thread: Reconstruction Conjecture: Group theoretic formulation? In the beginning, I con …

I suspect that a topic such as this may have been considered before: if so, I hope that someone can point me to a reference on the subject. I have a graph G with an upper bound d …

Given a triangulation $T$ of a planar set point $S$, we would like to randomly generate a polygon (hamiltonian cycle) $P$. However, it has been proved that Hamiltonian Circuit Pro …

I do recreational math from time to time, and I was wondering about a couple of graph enumeration issues. First, is it possible to enumerate all simple graphs with a given degree …

Lets define edge-cycle in a graph $G$ as a path where the first and the last node are adjacent. (in contrast with the definition of cycle where first and last node are the same). …

Introduction Graphs are not only important combinatorial objects, but also related to many topological/algebraic structures. In this question I am going to talk about various grou …

Let me start with a question for which I know the answer. Consider a symmetric integral $n\times n$ matrix $A=(a_{ij})$ such that $a_{ii}=2$, and for $i\ne j$ one has $a_{ij}=0$ or …

Suppose you generate random chords of a circle, with endpoints selected uniformly over the circumference, rejecting any chord that crosses a previously generated chord. The disk is …

Hello, I do have a collection of trees (mind maps, actually) and want to formally describe this collection of trees. My first question: how can I describe a tree? Are there any …

In Stefan Geschke's recent question, one of the solutions observed that the graph consisting of a single infinite beaded chain, a $\mathbb{Z}$-chain where each integer is connected …

Frucht showed that every finite group is the automorphism group of a finite graph. The paper is here. The argument basically is that a group is the automorphism group of its (colo …

In a recent question of mine I asked whether every infinite group is (isomorphic to) the automorphism group of a graph. The finite case was done by Frucht in 1939. The first an …