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.
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
5
votes
2
answers
715
views
Bound on graph domination number when min degree is 7
I have a graph $G$ whose minimum vertex degree is $\delta=7$.
I am seeking an upper bound on the domination number $\gamma(G)$
in terms of the number of vertices $n$ of $G$.
I found a paper by
Edwin C …
- 151k
8
votes
6
answers
965
views
Random planar, bipartite graphs
I have a need to generate random planar graphs none of which have an odd cycle,
i.e., bipartite graphs.
I know there is a substantial two-decade literature on random planar graphs, little with which I …
- 151k
53
votes
1
answer
6k
views
Why are there 1024 Hamiltonian cycles on an icosahedron?
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 vs. undirected!]
Wi …
- 151k
12
votes
1
answer
591
views
Characterizing graphs by their "walkers"
Let $G$ be a (large) graph and $W$ another (smaller) graph.
$W$ is what I call a walker.
Let me use "vertices" and "edges" for $G$ and
"nodes" and "arcs" for $W$.
$W$ has a distinguished node, its ce …
- 151k
7
votes
3
answers
808
views
When can the Cayley graph of the symmetries of an object have those symmetries?
Let $P$ be an object in $\mathbb{R}^n$ with symmetry group $G$.
Let $C$ be the a Cayley graph of $G$.
When can $C$ be embedded in $\mathbb{R}^m$ so that the embedded graph
has the same symmetry …
- 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
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
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
17
votes
3
answers
2k
views
Laplacians on graphs vs. Laplacians on Riemannian manifolds: $\lambda_2$?
A graph $G$ is connected if and only if
the second-largest eigenvalue $\lambda_2$ of
the Laplacian of $G$ is greater than zero.
(See, e.g.,
the Wikipedia article on algebraic connectivity.)
Is th …
- 151k
6
votes
5
answers
1k
views
Generate random graphs that satisfy the triangle inequality
I would like to generate random graphs that might be geometric graphs in some
(unknown) dimension. So I would like every triangle in the graph to satisfy the
triangle inequality on its (random) edge l …
- 151k
8
votes
3
answers
599
views
Decimating the infinite grid graph
Let $G$ be the graph whose nodes are the points of
$\mathbb{Z}^d$ in the nonnegative orthant (i.e., all
coordinates are $\ge 0$), with edges connecting each
pair of points separated by unit distance.
…
- 151k
24
votes
6
answers
3k
views
Shortest grid-graph paths with random diagonal shortcuts
Suppose you have a network of edges connecting
each integer lattice point
in the 2D square grid $[0,n]^2$
to each of its (at most) four neighbors, {N,S,E,W}.
Within each of the $n^2$ unit cells of thi …
- 151k
7
votes
1
answer
337
views
Maximal disarrangement of $n \times n$ numbers
This question is inspired by
Martin Erickson's
question,
"Labeling a Square Array."
I'll start by quoting Martin:
the $n^2$ cells of an $n \times n$ array are labeled with the integers
$1, \dots …
- 151k
20
votes
2
answers
1k
views
Erdős, Harary, Tutte's "dimension of graph": Progress in last 48 yrs?
I just ran across this delightful paper by an amazing triumvirate:
Paul Erdős, Frank Harary, and William Tutte. "On the dimension of a graph." Mathematika 12.118-122 (1965): 20.
(Cambridge link) …
- 151k