Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with graph-theory
Search options questions only
not deleted
user 6094
Questions about the branch of combinatorics called graph theory (not to be used for questions concerning the graph of a function). This tag can be further specialized via using it in combination with more specialized tags such as extremal-graph-theory, spectral-graph-theory, algebraic-graph-theory, topological-graph-theory, random-graphs, graph-colorings and several others.
22
votes
2
answers
895
views
Is every 1-million-connected graph rigid in 3D?
It is an old result that every $6$-connected graph is rigid in $\mathbb{R}^2$:
Lovász, László, and Yechiam Yemini. "On generic rigidity in the plane." SIAM Journal on Algebraic Discrete Methods 3, no …
- 151k
8
votes
2
answers
591
views
Orthogonal Hamiltonian cycles in (n x n x n) grids
Let $C_n$ be a cubical $n \times n \times n$ subset of the integer lattice,
so consisting of $n^3$ vertices.
I am interested in special Hamiltonian cycles in $C_n$, special in the
sense that (a) each …
- 151k
5
votes
0
answers
130
views
Equitable 4-colorings of planar triangulations
In an
equitable coloring
of a graph $G$, the number of vertices in each color class differ
by at most $1$.
For example, left below is not an equitable coloring, while the
right graph is equitably colo …
- 151k
16
votes
4
answers
1k
views
Squaring a square and discrete Ricci flow
Is this a theorem?
Every $3$-connected planar graph $G$ may be represented as
a tiling of a square by squares,
one square per node of $G$, with nodes connected in $G$
corresponding to tangent squares …
- 151k
3
votes
0
answers
159
views
Rubber-band graph embedding under gravity
Let $G$ be a simple $3$-connected plane graph with the vertices of
its outer face pinned to the $xy$-plane.
View each edge as an ideal rubber band, and each internal
node given a weight proportional t …
- 151k
2
votes
1
answer
144
views
Distance queries to reconstruct an unknown graph
Let $G$ be a finite, simple, connected, undirected graph on $n$ vertices.
Suppose your goal is to determine $G$ uniquely
via queries.
Each query choses a $v_i$, and returns the shortest distances (num …
- 151k
2
votes
0
answers
224
views
Graphs with the same Laplacian eigenvalues
Let $L$ be the
Laplacian matrix
for a simple graph $G$ of $n$ vertices,
and $\lambda_0,\ldots,\lambda_{n-1}$ its $n$ eigenvalues.
Q.
What is the cardinality of the class of $n$-vertex graphs $ …
- 151k
3
votes
1
answer
373
views
Diagonal shortcuts to minimize all-pairs shortest-paths in grid graph
Augment the grid graph $G$ on lattice points $[1,n]^2$, which
connects each point to its four distance-$1$ vertical and horizontal neighbors.
Augment $G$ to $G'$ by adding in one of the two $\sqrt{2}$ …
- 151k
7
votes
0
answers
87
views
Universal point sets for 1-plane graphs
It is a notorious open problem to find a smallest set of $N$ points that
permit any $n$-vertex planar graph to be drawn in the plane without
crossings, using only those $N$ points as vertices, and str …
- 151k
3
votes
0
answers
222
views
Reconstructing plane graphs from degree- and face-sequences
Let $G$ be a plane $3$-connected graph; so it partitions the plane
into regions bounded by faces.
Let $\mathrm{deg}_v$ be the sequence of vertex degrees of $G$,
and $\mathrm{deg}_f$ be the sequence of …
- 151k
13
votes
2
answers
2k
views
Counting Hamiltonian cycles in $n \times n$ square grid
I wonder if anyone has counted these curves, either exactly or asymptotically?
Let $S_n$ be an $n \times n$ subset of $\mathbb{Z}^2$ consisting of $n^2$
lattice points: a lattice square.
Define a re …
- 151k
6
votes
4
answers
546
views
(Non)uniqueness of the common-factor graph
Let $S=\{x_1,\ldots,x_k\}$ be a set of $k$ distinct natural numbers,
a subset of $\{1,\ldots,n\} = \mathbb{N}_{\le n}$.
Define the common-factor graph $G(S)$ as the (undirected) graph with
a node for …
- 151k
10
votes
2
answers
415
views
Graph planarization via rewiring
Let $G$ be a nonplanar graph (undirected) of $n$ nodes and $e$ edges, with
$e \le 3n-6$.
Define a rewiring move as replacing edge $(a,b)$ with edge $(a,c)$.
The result must be a simple graph (no loops …
- 151k
14
votes
2
answers
2k
views
A random walk on an infinite graph is recurrent iff ...?
Q. Is there a master theorem that can be used to determine whether or not
a simple random walk (choose a random neighboring vertex as the next step)
on a given infinite graph
leads to recurr …
- 151k
8
votes
4
answers
338
views
Iteration cycles of Z_n weights in path graphs: Why cycles of length 182 for a 6-node path?
Assign to the $n$ nodes of a path graph vertex weights
forming a permutation of $(0,\ldots,n{-}1)$.
Now iterate the following update repeatedly:
Each node sums the weights of its neighbors, and that n …
- 151k