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 4362
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.
5
votes
1
answer
104
views
Is a connected graph uniquely determined by its weighted 2-step graph?
This is an extension of a previous question: https://math.stackexchange.com/questions/876336/is-a-graph-uniquely-determined-by-its-weighted-2-step-graph/876357#876357. In that question I asked about …
- 29.2k
5
votes
Connection between PageRank and Fiedler vector
The PageRank vector with seed $s$ and jumping constant $\alpha$ is by definition the solution to the equation
$$pr(s,\alpha) = \alpha s + (1-\alpha)pr(s,\alpha)W$$
where $W$ is the random walk matrix …
- 29.2k
14
votes
Surprising connection between linear algebra and graph theory
I think the basic point of contact between graph theory and linear algebra is the notion of a random walk. Given an initial probability distribution $p$ on the vertex set $V$ of a graph (though of as …
- 29.2k
3
votes
0
answers
471
views
What is the expected Cheeger constant of a random graph?
Recall that the Cheeger constant (AKA isoperimetric constant) of a graph $G$ is the infimum of $\frac{\partial S}{vol S}$ over all subsets $S$ of $G$ with volume no larger than $vol(G)/2$. I would li …
- 29.2k
5
votes
What is a continuous path?
It sounds to me like your inventions are related to persistent homology, developed by Weinberger, Carlsson, and others. There is an informative "What is..." article about this by Weinberger: http://w …
- 29.2k
14
votes
2
answers
382
views
What are some useful invariants for distinguishing between random graph models?
Quite a few probabilistic algorithms for generating random graphs exist in the literature, such as:
The Erdős-Rényi model
The Stochastic Block model
The Watts-Strogatz model
The Barabasi-Albert mode …
- 29.2k
2
votes
Connectivity of weighted graph and zero Laplacian eigenvalues
You can simply imitate the proof in the unweighted case. The Rayleigh quotient associated to the Laplacian is:
$$R_G(f) = \frac{\langle Lf, f \rangle}{\langle f, f \rangle} = \frac{\sum_{x \sim y} ( …
- 29.2k