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 9896
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.
0
votes
1
answer
132
views
Extremal problem: #paths of length l as function of number of edges
Suppose that $G$ is a simple, undirected graph with $n$ vertices and $m$ edges. Conjecture: The total number of vertex paths of length $l$ is at most
$$
n (2 m/n)^{l-1}
$$
The heuristic basis for t …
- 3,475
1
vote
0
answers
121
views
Number of edges in graph in terms of reliability
Consider a connected graph $G$ with min-cut $c$. Suppose the edges fail (are removed) independently with probability $p$. Then $U(p)$, the probability that $G$ becomes disconnected, is at least $p^c$. …
- 3,475
3
votes
Expressing a graph property with counting quantifiers
If A and B are cycles of length m, n, then the duplicator can win the k-long Ehrenfeucht-Fraisse game iff m, n > 2^(k-1).
Basically, whatever player I moves in A, player II choose an arbitrary elemen …
- 3,475
4
votes
1
answer
1k
views
Spanning trees of $k$-edge-connected graphs
What are the best lower bounds available on the number of spanning trees for a $k$-edge-connected graph with $m$ edges and $n$ vertices?
There is a simple argument, based on induction on # spanning f …
- 3,475
3
votes
2
answers
363
views
Bounds on spanning tree for sparse graphs
In mathoverflow posting 43081, the question was raised of bounding the number of spanning trees of a graph in terms of $m, n$, the number of edges and vertices. I am interested in the case when $m$ i …
- 3,475
3
votes
4
answers
283
views
Spanning trees of $H \cup e$ in terms of $H$
Suppose we have a connected graph $H$ with $m$ edges and $n$ vertices, and we add an edge to it. How can one bound the number of spanning trees of $H \cup e$ in terms of $H$?
The following formula s …
- 3,475
2
votes
2
answers
2k
views
Bounds on number of simple paths in graph
Given an undirected graph $G$ and vertices $s, t$, are there any upper bounds on the number of simple paths from $s$ to $t$?
Can these bounds be improved if you know
1) The distance from $s$ to $t$
…
- 3,475
2
votes
1
answer
203
views
Least reliable graph when edge-connectivity is odd
Among all graphs with $n$ vertices and edge-connectivity exactly $c$ (so the size of the minimum edge cut is $c$), there is a well-known result of Lomonsov and Poleskkii that the cycle graph, which co …
- 3,475
3
votes
0
answers
223
views
Bounds on number of small minimal cut-sets in graph?
David Karger developed an algorithm for estimating graph reliability; a key lemma in this algorithm is that if a graph has minimal cut-set size $c$, then the number of cut-sets of size
$\alpha c$ is $ …
- 3,475
12
votes
3
answers
3k
views
Number of spanning trees which contain a given edge
Suppose I have a connected graph $G$ and a fixed edge $e = \langle u, v \rangle \in G$, and I want to count the number of spanning trees that involve $e$. I really only want to estimate the fraction o …
- 3,475
12
votes
3
answers
3k
views
Lower bound on # spanning trees in a connected graph
Are there are any good lower bounds for the number of spanning trees for a connected graph $G$ in terms of (for example) number of edges $E$ or number of vertices $V$ ?
Are improved bounds available …
- 3,475
2
votes
1
answer
174
views
Bounds on chromatic index
Let $H$ be a hypergraph of maximum vertex-degree $\Delta$. (That is, for all vertices $x$, we have $| \{ e \in H \mid x \in e \} | \leq \Delta$) Are there any bounds on the chromatic index $\chi_e(H)$ …
- 3,475
2
votes
1
answer
94
views
A bound on coefficient of independence polynomial
Let $G$ be a graph with $m$ edges and $n$ vertices. For a fixed integer $s \leq n$, what lower bound can be shown on the number of independent sets with $s$ vertices?
Letting $d$ denote the average d …
- 3,475
1
vote
Finite graphs that realize all types over $n$-element sets
I would like to add to Stefan's statement. The sentence $\Theta$ which expresses "G is $n$-saturated" is true of almost all finite graphs. The interpretation of this limit is that, as the size $|G| = …
- 3,475
2
votes
0
answers
97
views
An extremal sum for hypergraph degrees
Consider a rank-$r$ hypergraph $H = (V,E)$. I would a lower-bound of the following form:
$$
\sum_{e \in E} \frac{ \sum_{v \in e} \text{deg}(v) }{\max_{v \in e} \text{deg}(v)} \geq c \sum_{v \in V} \te …
- 3,475