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.
0
votes
1
answer
37
views
Cycle-Sculpturing with Minimal Vertex-Deletion
given a simple, finite and symmetric graph $G(V,E)$ with $n$ vertices and at least $n$ edges
Question:
how can the smallest set of vertices $W\subset V$ be calculated for which the graph induced by $ …
- 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
1
vote
Complexity of maximum weight-sum matching for cycle graphs
With inspiration from the comments I arrived at the following idea:
the maximum weight matching on the cycle is converted to a maximum weight matching on a path that is generated by splitting a vertex …
- 13.2k
1
vote
1
answer
54
views
Complexity of maximum weight-sum matching for cycle graphs
I need to determine a matching with maximal weight-sum for a cycle graph with positive, negative and zero edge-weights.
Question:
What is the fastest way of calculating such a matching?
Because of t …
- 13.2k
0
votes
0
answers
23
views
Building hypercubes from the bottom up
let $H^k$ denote a $k$-dimensional hypercube in a complete symmetric graph $G(V,E)$ without self-loops and parallel edges; let $|V|=2^n$ be the number of vertices.
setting
$\mathbb{H}^0 := V$, i.e. th …
- 13.2k
2
votes
1
answer
224
views
Name for generalization of trees to digraphs
One definition of tree in graph theory could be as follows:
A tree is a(n undirected) graph for which there is a unique (undirected) path between any pair of vertices.
This suggest a possible defini …
- 13.2k
0
votes
Minimally 2-vertex-connected graphs?
$K_3$ is the only graph with a triangle that contains a bivalent vertex, and is a minimally vertex 2-connected graph (MV2CG).
According to the two ears theorem every triangulated polygon with at least …
- 13.2k
1
vote
Minimally 2-vertex-connected graphs?
I conjecture that a a sufficient condition for a graph being minimally 2-vertex-connected is that
it is $2$-vertex-connected and if every vertex $u$ is adjacent to some vertex $v$ of degree $2$ and c …
- 13.2k
0
votes
0
answers
32
views
Enumeration of flat integral $K_4$
Question:
What is known about the enumeration of all $(a,b,c,d,e,f)\in\mathbb{N}^6_+: \\ \quad\operatorname{GCD}(a,b,c,d,e,f)=1\ \\ \land\ \exists \lbrace x_1,x_2,x_3,x_4\rbrace\subset\mathbb{E}^2:\ …
- 13.2k
2
votes
2
answers
202
views
Isometric embeddings of metric $K_{n+1}$ in $\mathbb{R}^n$
Question:
is it always possible to embed a complete, symmetric and metric graph $G$ with $n+1$ vertices isometrically in $\mathbb{R}^n$?
I'm convinced it must be true, but can't remember having seen …
- 13.2k
0
votes
Random sample of spanning trees
A pragmatic solution would be to randomly shuffle the set of edges and assgning them their index in that random sequence as their weight and finally calculate the Minimum-weight Spanning Tree of the t …
- 13.2k
2
votes
1
answer
124
views
Constructing optimal Hamilton cycles from optimal Hamilton paths
Question:
can the shortest Hamilton cycle in a complete symmetric graph with weighted edges be constructed from the shortest Hamilton path in the same graph by connecting its ends and then exchanging …
- 13.2k
0
votes
0
answers
89
views
Relation of minimum spanning trees to the shortest Hamiltonian path problem
Spanning trees can be decomposed into a minimal set of maximal path graphs, whose vertices have degree two exactly if they also have degree two in the spanning tree; lets call these paths tree paths.
…
- 13.2k
2
votes
$A^*$ algorithm to find shortest path when weights in my graph are the inverse of distance
The essential difference is that improvements to a shortest known connection between start and destination will most likely lead over intermediate points that lie outside a region that is not quite an …
- 13.2k
2
votes
2
answers
122
views
Existence of certain regular graphs
Question:
what can be said about the existence of $2k$ regular graphs, $1\lt k$ that have a $1$-factor and a $2$-factor?
Provided their existence, what is/are the smallest for $k$?
The graphs must b …
- 13.2k