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 35626
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
Diameter of random segment intersection graph?
Here is a way of thinking. It may turn out to be misleading, but it may also suggest a
way to think properly about this problem.
Lets take a random instance of a matching and reconstruct it edge by …
- 2,158
3
votes
Accepted
Can we find 3 disjoint directed Hamiltonian cycles in the cube?
It looks like the titled question (d=3) is not directly answered: I will hint at how to
show the answer is no.
At each vertex, there are two ways that the decomposition can go. I like
to call them b …
- 2,158
2
votes
Random graphs with boundary in a game (Tsuro)
I would not be surprised if the probability was near the probabilty for a random matching between the points of a given set forming a special submatching. For a board holding k by k many tiles, this …
- 2,158
4
votes
The diameter of a certain graph on the positive integers
Maybe this will work.
Given positive integers a and b, choose c large enough so that c^2 > a+b.
also, choose c so that c^2 -a -b is odd and factors as (e+d)(e-d).
Then a has an edge with c^2 - a, b h …
- 2,158
5
votes
What are the applications of hypergraphs?
Ford, Green, Konyagin, Maynard, and Tao - Long gaps between primes mentions a hypergraph covering theorem
of Pippenger and Spencer. This theorem is generalized and used in a
sieving method to find l …
1
vote
4-regular graph with every edge lying in a unique 4-cycle
Consider two labeled squares, vertices on one labeled from the abcd alphabet, the other labeled
from 1234. We are going to identify one or more pairs of vertices while maintaining the constraint
that …
- 2,158
3
votes
Wait time to grid network disconnection with failing edges
Instead of answering the question, I will suggest some modifications
that should make the model easier to analyze.
I will denote the number of vertices as v, and the number of edges as
dv for the d-d …
- 2,158
1
vote
Coloring vertices in a cubic lattice graph and counting edges between vertices of identical ...
This is more a collection of potentially useful ideas and intuitions, with no guarantee of
correctness and no proof.
If you take a coloring and tweak it by switching the colors on two vertices of opp …
- 2,158
0
votes
Graphs with dangling edges
There exist partial algebras ( having nontotal basic operations ), multi-typed structures,
hypergraphs, and various flavors of categories, so why not partial multigraphs?
Unfortunately, your descri …
- 2,158
1
vote
Accepted
How many edges can you put in a graph such that every edge belongs to a minimal $k$-cycle?
Here is a rough analysis to start things off. k=3 corresponds to a complete graph, and
k=4 to a complete bipartite graph with the vertex set split as evenly as possible. (I don't
see an easy proof of …
- 2,158
1
vote
Estimate size of graph by taking random walks
Unless you use some exhaustive criterion for stopping, such as Anton Petrunin's suggestion
of deleting vertices while maintaining connectivity and not stopping until all vertices are gone,
I do not se …
- 2,158
2
votes
Reference Request for: Finding Large Bipartite Subgraphs via Destruction of Odd Cycles in Gr...
Not a reference, but you might enjoy tinkering with this.
Decide for your graph on two parameters C and M. For each of C-many trials,
two-color the vertices. In each trial, look at the vertices v w …
- 2,158
5
votes
Accepted
Relationship between triangle free graphs and their minimum degree
In addition to the literature mentioned in the other answers, one can try some
arguments based on counting.
Let $u$ and $v$ be two of $n$ vertices in a triangle-free graph, and further assume they
ar …
- 2,158
1
vote
Counting the number of rooted trees given the distance distribution at each level
Even with a distinguished root and insisting that all isomorphisms respect this
distinguished root, this will be a challenging enumeration.
For $k \leq 2$ the problem is straightforward: The count is …
- 2,158