# Tagged Questions

1answer
90 views

### simple cycle analog in 2D (with application in tiling)

We know that any closed cycle of a graph could be decomposed into sum of simple cycles. To translate this theorem into tiling of 1D (Wang tile). We know that any 1D periodic tiling could be ...
1answer
154 views

### Integral straight-line embeddings of planar graphs

Wikipedia says (in the article on Fáry's theorem), "Heiko Harborth raised the question of whether every planar graph has a straight line representation in which all edge lengths are integers. The ...
1answer
576 views

### Paul Erdős: Determine or estimate the number of maximal triangle-free graphs on n vertices

Among the collections of the open problems of Paul Erdős on the website of Professor Fan Chung, there is one called "number of triangle-free graphs". ...
1answer
639 views

### A Question on 1, 2 ,3 Conjecture

1, 2, 3 conjecture is well-known: If $G$ is a simple graph which is not $K_2$ then one can assign a number among $1, 2, 3$ to every edge such that if we label each vertex with the sum of the numbers ...
2answers
618 views

### Is the Steiner ratio Gilbert–Pollak conjecture still open?

Gilbert-Pollak conjecture on the Steiner ratio: Consider a set $P$ of $n$ points on the euclidean plane. A shortest network interconnecting $P$ must be a tree, which is called a Steiner minimum ...
0answers
319 views

### Graphs with graphic imbalance sequences

Let $G$ be simple undirected graph and $e=uv\in E(G)$. The imbalance of the edge $e$ is the value $imb(e)=|d(u)-d(v)|$. Let $M_{G}$ denotes the imbalance sequence (or more correctly, multiset of ...
1answer
263 views

### Maximal class of simple graphs of order $n$ with mutually distinct numbers of spanning trees

This problem in some ways related to this post. Let $A_n$ be the set of all integers $x$ such that there exist a connected simple graph of order $n$ having precisely $x$ spanning trees. Study the ...
2answers
765 views

### Minimal graphs with a prescribed number of spanning trees

As its long ago since Erdős died and mathoverflow is the second best alternative to him (for discussing personal problems), I'd like to start a fruitful discussion about the following problem ...
1answer
363 views

### Die-rolling Hamiltonian cycles

Let $R$ be a rectangular region of the integer lattice $\mathbb{Z}^2$, each of whose unit squares is labeled with a number in $\lbrace 1, 2, 3, 4, 5, 6 \rbrace$. Say that such a labeled $R$ is ...
2answers
2k views

### Is there a 7-regular graph on 50 vertices with girth 5? What about 57-regular on 3250 vertices?

The following problem is homework of a sort -- but homework I can't do! The following problem is in Problem 1.F in Van Lint and Wilson: Let $G$ be a graph where every vertex has degree $d$. ...
1answer
603 views

### Reconstruction Conjecture: Group theoretic formulation

As we read from wiki, informally, the reconstruction conjecture in graph theory says that graphs are determined uniquely by their subgraphs. Is there a group-theoretic formulation of this ...
4answers
6k views

### Do there exist chess positions that require exponentially many moves to reach?

By "chess" here I mean chess played on an $n\times n$ board with an unbounded number of (non-king) pieces. Some care is needed if you want to generalize some of the subtler rules of chess to an ...
0answers
749 views

### Optimal Monotone Families for the Discrete Isoperimetric Inequality

Background: the Discrete Isoperimetric Inequality Start with a set X={1,2,...,n} of n elements and the family $2^X$ of all subsets of X. For a real number p between zero and one, we consider a ...
1answer
655 views

### Is every matching of the hypercube graph extensible to a Hamiltonian cycle

Given that $Q_d$ is the hypercube graph of dimension $d$ then it is a known fact (not so trivial to prove though) that given a perfect matching $M$ of $Q_d$ ($d\geq 2$) it is possible to find another ...