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 not deleted
user 3401
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.
7
votes
Accepted
Asymptotic Geodesic Flow on Planar Graphs
You can't do better. Lipton and Tarjan's planar separator theorem says that any $n$-node planar graph $G=(V,E)$ contains a set $S$ of $O(\sqrt{n})$ vertices whose removal separates the graph into comp …
- 4,922
4
votes
Notation for a graph without any edges?
I don't think there is standard notation for this. If you've already fixed a notation for complement (say a superscript c) then you could use $K_n^c$. But I don't think standard notation exists for th …
- 4,922
15
votes
Proving that every graph is an induced subgraph of an r-regular graph
Use induction on $r-\delta$, where $\delta=\delta(G)$ is the smallest degree of any vertex in $G$.
If $r-\delta=0$, then you are done.
If $r-\delta > 0$ then create two disjoint copies of $G$, say …
- 4,922
1
vote
edges minus vertices
My answer comes from the random graphs community. In the book Random Graphs, the quantity "edges minus vertices" is called the excess, which is quite standard terminology at least in random graphs.
In …
- 4,922
1
vote
How to estimate the growth of the probability that $G(n, M)$ contains a $k$-clique
You might take a look at Chapter VII of Bollobas. In particular,
Theorem VII.1.7 -- which is simple enough that he doesn't bother providing a proof -- states that the expected number of $k$-cliques i …
- 4,922
5
votes
Accepted
Cover time and intersection time of random walks
In Proposition 5 of Chapter 14 of the unpublished book on Markov chains by Aldous and Fill, they show that for continuous time reversible Markov chains,
\[
I \le \max\{ \mathbb{E}_i T_j, i,j \in V\}, …
- 4,922
9
votes
Accepted
Similarity of weighted graphs
If you view the weights as edge lengths then you can view each graph as a metric space, and then use the Gromov-Hausdorff distance between the two metric spaces. This may not be at all suitable for yo …
- 4,922
10
votes
What are some good examples of non-monotone graph properties?
One whole family comes from considering properties that are monotone for connected graphs but can change when the connectivity changes. For example: the diameter of a graph -- defined to be the maximu …
- 4,922
7
votes
Accepted
Differences of near diagonal Ramsey numbers.
Edit: Erdős got three things wrong. First of all, it wasn't Faudree, Shelp, and Rousseau, it was Faudree, Shelp, and Burr. Second, it wasn't "recently", it was in the future (with respect to the qu …
- 4,922
3
votes
The critical value of percolation on Cayley graphs.
In a paper called Critical Percolation on any Nonamenable Group Has no Infinite Clusters, Benjamini, Lyons, Peres, and Schramm show that ... critical percolation on any nonamenable group has no infini …
- 4,922
3
votes
Accepted
Number of Geodesic Paths Passing Through a Vertex in an Expander Graph
My short answer: I think not much is known. But: here is the state of the art on related problems, as far as I am aware.
Aldous and Bhamidi consider the following model. Place independent exponentia …
- 4,922
6
votes
Does graph asymmetry imply all eigenvalues of the graph Laplacian are simple?
Take two asymmetric $d$-regular graphs $H_1,H_2$, and let $G$ be their disjoint union. Then $d$ will be a repeated eigenvalue.
If you want $G$ connected, take the complement of the graph obtained by …
- 4,922
2
votes
Accepted
Critical probability for Erdos-Renyi digraphs to be strongly connected
This is basically the main result of a paper by Ilona Palásti:
On the strong connectedness of directed random graphs. Studia Sci.
Math. Hungar. 1 (1966), 205–214.
Here's the MathSciNet summar …
- 4,922
2
votes
Accepted
Is there a simple inductive procedure for generating labeled trees uniformly at random, with...
This is an interesting question. For any fixed positive integer $d \geq 2$, write $T_d^{\infty}$
for the complete infinite rooted $d$-ary tree (by this I mean every node has exactly $d$ children). Lu …
- 4,922
17
votes
Accepted
Properties of Some Random Graphs
Yes, this model has been studied. You should look at Chapter 9 of Janson, Luczak and Rucinski's Random Graphs book, and in particular at Corollary 9.44. This corollary is in fact a rather well-known t …
- 4,922