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 31310
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.
14
votes
4
answers
1k
views
Is the "Moebius Stairway" Graph Already Known?
It is a wellknown fact, that Moebius Ladder Graphs have $2n$ vertices, but nowhere could I find any hint of how to generalize them to Graphs with $2n+1$ vertices.
Last week I had the idea of giving up …
- 13.2k
11
votes
1
answer
390
views
Shortest Paths in the "Cantor Graph"
First, let me explain, what I understand by a "Cantor Graph":
it is an infinite, directed graph with self loops and countably many vertices labelled with the natural numbers; every ordered pair of …
- 13.2k
11
votes
2
answers
1k
views
Densest Graphs with Unique Perfect Matching
Given a graph $G$ with $n$ vertices, that has a perfect matching $M$, what is the maximal number of edges that $G$ can have without contradicting the uniqueness of $M$?
Are examples of such extremal …
- 13.2k
8
votes
0
answers
433
views
Is there an "Erlangen Program" for Graph Theory?
There are certain graph theoretic problems (especially optimization problems), whose solution-subgraph (i.e. the set of vertices and edges)), is invariant under certain modifications (especially modif …
- 13.2k
6
votes
1
answer
368
views
How does the complexity of calculating the Permanent imply the NP completeness of directed 3...
In their paper Two Approximation Algorithms for 3-Cycle Covers of Markus Bläser and Bodo Manthey it is stated that:
"...deciding whether an unweighted directed graph has a 3-cycle cover is already NP- …
- 13.2k
5
votes
1
answer
236
views
Do the Odd Cycles of a Graph Define a Matroid?
An Odd Cycle Transversal is a set of vertices that, when removed from a graph, renders it bipartite.
Question:
does the collection of "critical" sets of vertices, whose removal renders a graph bipart …
- 13.2k
5
votes
6
answers
435
views
Characterizing Convex Configurations of Quadrupels of Coplanar Points via Linear (In-)equali...
Given 4 points $A$, $B$, $C$ and $D$ in general position in the euclidean plane, is it possible to determine from the 6 distances $AB$, $BC$, $CD$, $AD$, $AC$ and, $BD$ alone, whether every point is a …
- 13.2k
5
votes
1
answer
181
views
Resource Constrained Routing with Refueling
What are good algorithms (resp. models) for calculating optimal or near optimal routes while taking into account fuel consumption, options for refueling and, limited tank capacity?
Especially modeling …
- 13.2k
4
votes
1
answer
244
views
Probability of a vertex being a "degree-celebrity" in a random graph
If $G(n,p)$ is a random graph of the Erdös-Rényi model,
what is the probability that $\mathrm{deg}(v)\gt\mathrm{deg}(u)\ \forall u\in\mathrm{adj}(v)$
Please feel free to relate answers to other m …
- 13.2k
4
votes
2
answers
416
views
What Kind of Graph is This?
I am currently developing TSP heuristics that aim at symmetrically reducing the original, complete and undirected graph.
The overarching rationale is that the reduction is done via a sequence of regul …
- 13.2k
4
votes
1
answer
75
views
Existence of optimal tours containing an 'extremal' edge
let $\mathcal{P}$ be a finite set of points in the euclidean plane in general position, and let $$\lbrace p_A,p_B,p_C,p_D\rbrace: \ \|p_C-p_A\|+\|p_D-p_B\|\ \gt \|p_i-p_h\|+\|p_k-p_j\|\quad\forall\ \ …
- 13.2k
4
votes
0
answers
143
views
Halin Graphs with Highest Number of Hamilton Cycles
Halin graphs contain a Hamilton cycle and have the interesting property, that, also in the case of arbitrary real edge weights, it is possible to report one of the shortest contained Hamilton cycles i …
- 13.2k
4
votes
1
answer
168
views
Finding minimum weight perfect matchings in sparse bipartite graphs
Question:
What can be recommended for finding optimal perfect matchings in large bipartite graphs with small vertex degree if the edge-weights are positive real values?
I am looking for algor …
- 13.2k
4
votes
2
answers
464
views
Geodesics in Graphs:Shortest Paths vs Going as Straight Ahead as Possible
According to Wikipedia http://en.wikipedia.org/wiki/Geodesic, a geodesic " is a generalization of the notion of a "straight line" to "curved spaces " and further " In the presence of an affine connect …
- 13.2k
4
votes
Accepted
Efficient algorithm for graph problem
If $v_1$ and $v_l$ are fixed then constructing a minimum weight breadth-first tree of height $l{-}1$ and finally optimally attach vertex $v_l$.
Iterating over all candidate pairs of $v_1$ and $v_l$ wo …
- 13.2k