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 46140
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.
3
votes
Accepted
Forced monochromatic pairs in graphs
Yes. Take the complete graph on $n+1$ vertices and delete one edge.
- 7,226
4
votes
Graph on $\mathbb{N}$ where almost every vertex is shy
In a star graph, all but one vertex is shy, so a simple construction is to build a star graph from $\{1,\ldots,4\}$, another from $\{5,\ldots,12\}$, etc., doubling the size each time.
- 7,226
2
votes
Accepted
Is there an algorithm to generate non-isomorphic Halin graphs?
There is a theorem due to Jordan which is useful for enumerating or generating trees: every tree has a centre or a bicentre. To enumerate/generate suitable bicentral trees, enumerate/generate suitable …
- 7,226
3
votes
Optimal schedule for a soccer tournament
Disclaimer: this is a partial answer which expands on some comments I've made on the question and on the earlier answers.
Bounds
Theorem: $\textrm{BESTMIN}(n) \le \lfloor \frac{n-1}{2}\rfloor$
Proof: …
- 7,226
3
votes
Accepted
Hamiltonian path in total graph
The edges incident to $v \in V$ form a clique in $T(G)$, so the Hamiltonian path $v_1, v_2, v_3, \ldots, v_n$ in $G$ can be lifted into a Hamiltonian path in $T(G)$ as follows:
Insert the edges to ge …
- 7,226
1
vote
integer network flow with symmetry
No. Consider the graph with vertices $\{s, a, a', b, t\}$ and edges $\{s\to a, s\to a', a\to b, a'\to b, b\to t\}$. If each edge has weight 1 then the max integer flow is not invariant under the only …
- 7,226
1
vote
Accepted
Counting Euler circuits through labelled trees where $v_1$ and $v_2$ have distance two
Wlog we can use $v_{n-2}$ and $v_{n-1}$ instead of $v_1$ and $v_2$. Then if we let $B_n \subset T_n$ be the set of labelled trees with edges $(v_{n-2}, v_n)$ and $(v_{n-1}, v_n)$, the count for $A_n$ …
- 7,226
7
votes
Accepted
Odd partition with extra properties
Multiply by the least common multiple $M$ of the denominators to get the equivalent problem:
The $a_i$ are positive integers.
$k$ is an odd number.
We can partition $A$ into two parts of equal sum.
I …
- 7,226
3
votes
Accepted
Path of length $n$ but no Hamilton cycle
Assuming you mean a graph with a Hamiltonian path but no Hamiltonian cycle,
The Petersen graph is a standard example.
Any pendant-free graph with a Hamiltonian path and a bridge is an easy example; e …
- 7,226
2
votes
Accepted
Completing a tree to a 2-connected outerplanar graph
Yes. Pick an arbitrary vertex to be the root. Consider the sequence of vertices $v_1, v_2, \ldots$ produced by a pre-order traversal of the rooted tree, adding edges $v_i - v_{i+1}$ where they don't a …
- 7,226
2
votes
Accepted
Combinatorial graph optimization problem on integer adjacency matrices
Consider $$M_{i,j} = \begin{cases} 1 & \textrm{if } i \equiv j \pmod 2 \\ N & \textrm{if } i \not\equiv j \pmod 2\end{cases}$$ where $N > 1$. Then
$$\min(M_{i,k}, M_{k,j}) = \begin{cases} 1 & \textrm{ …
- 7,226
1
vote
Number of order-relational different weighted $K_4$
The first question may be answered, as you yourself implied in comments, by using a linear programming solver. Applying GNU's lpsolve to the question of which permutations have solutions, I find that …
- 7,226
2
votes
About the maximum number of leaves adjacent to a vertex in a tree
Expanding on a comment upon OP's request:
To calculate the average over all unlabelled trees on $n$ vertices we can exploit the property that every finite tree has either a centroid or a bicentroid. T …
- 7,226
3
votes
Accepted
How to construct a hamilton-connected cubic graph? Is it possible?
Take a cycle of $2m$ elements, label the vertices around the cycle from $0$ to $2m-1$, and add diagonals $1 \to (2m-1)$, $2 \to (2m-2)$, $\cdots$, $(m-1) \to (m+1)$, and special case $0 \to m$.
By sym …
- 7,226
2
votes
Accepted
What is this invariant graph?
Rephrasing, given $G$ and $n$ you're looking for the smallest subset $V' \subseteq V$ of the vertices of $G$ such that the subgraph $G'$ induced by $V'$ has a vertex colouring $\phi$ on $n$ colours fo …
- 7,226