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.
1
vote
1
answer
91
views
Probability process involving blocking paths of rooted tree
Consider a rooted tree $T$ and $n$ leaf nodes which are all at depth $R$. We would like to select a random subset $S$ of the edges of $T$, such that
(i) Every root-leaf path of $T$ contains at least o …
- 14.2k
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
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 …
- 19.1k
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 …
- 28k
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)$ …
- 1,821
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 …
- 103
5
votes
0
answers
572
views
When is polytope compatible with network flow?
A linear program is the problem of optimizing an linear objective function within some polytope $A$ over $\mathbf R^n$. My question is motivated by the question of when a linear programming problem ca …
- 747
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
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 …
CommunityBot
- 1
2
votes
0
answers
81
views
Subgraphs of bounded tree-width and preserving edges of original graph
Given a graph $G$, I would like to determine a method for randomly generating subgraphs $G'$ with the following properties:
Each edge of $G$ has at least some probability $p$ of going into $G'$
The …
- 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 …
- 131
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
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
2
votes
0
answers
138
views
$f$-vector of graph connectivity
For a connected graph $G$, let $N_i$ be the number of connected subgraphs of size $i$. The vector $\langle N_0, N_1, \dots \rangle$ is also known as the $f$-vector for the graph.
As a superset of a c …
- 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 …
- 37.7k