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 answers only
not deleted
user 1946
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.
7
votes
Accepted
What determines internalization of graph-structures into the set world?
The answer is yes for equinumerosity (provided...), but no for graphs.
Equinumerosity. KM is commonly taken to include the axiom of choice and furthermore the axiom of global choice, and this makes th …
- 236k
3
votes
Does $(\omega, E)$ with the cycle condition have an $\omega$-path?
No. Draw edges from $0$ and $1$ to all numbers $n>1$. Now any two nodes lies on a cycle of length $4$. But there is no injective $\omega$-walk, since every edge touches either $0$ or $1$, and indeed e …
- 236k
25
votes
Non-definability of graph 3-colorability in first-order logic
Here is one way to do it.
2-colorability case. First let's warm up with the 2-colorability case. Notice that odd-length cycles are not 2-colorable, since the colors have to alternate as you go around …
- 236k
8
votes
Seymour's second neighborhood conjecture for infinite graphs
Allow me to make an observation concerning what I find to be an interesting angle on the question in the context without the axiom of choice, where there are competing conceptions of what it means to …
- 236k
9
votes
Accepted
A notion of thinness for subsets of $\omega$, using chromatic number
The two notions are incomparable.
To see that the first notion does not imply the second, let's construct a set $S$ with asymptotic density $0$, but with infinite chromatic number. We place infinitely …
- 236k
3
votes
Accepted
Is following function a metric on the set of isomorphism classes of graphs with countably ma...
To prove that this is a metric, consider the following theorem.
Theorem. If the second player can survive for $n$ steps in the $(\Gamma_1,\Gamma_2)$ game, and for $m$ steps in the $(\Gamma_2,\Gamma_3 …
- 236k
58
votes
Accepted
Does knight behave like a king in his infinite odyssey?
Consider the following open knight's tour on a $5\times 5$ board, starting at position $1$ and then touring the $5\times 5$ board in the indicated move order. The final position is $25$, from which th …
- 236k
5
votes
Graph of functions sharing a point
Gerhard has pointed out that your sharing-a-point graph is not universal for uncountable graphs, since any uncountable collection of functions on $\omega$ must have many of them sharing a point. So th …
- 236k
134
votes
What is a chess piece mathematically?
In terms of mathematical analysis and combinatorial game theory,
the essence of any game is captured by its game tree, the tree
whose nodes represent the current game state, and to make a move in
the …
- 236k
6
votes
Mutually non-isomorphic connected graphs on $\kappa$ points
The general fact is that every mathematical structure of size $\kappa$, in a language of size at most $\kappa$, can be coded as a (connected, undirected, simple) graph of size $\kappa$. What I mean is …
- 236k
4
votes
Applications of infinite graph theory
A model of set theory $\langle M,\in\rangle$ is a certain kind of directed graph. So graph theory has the capacity to serve as a foundation of mathematics, having a copy of virtually any conceivable m …
- 236k
8
votes
Number of trees with n nodes and m leaves
I think this is what you want:
OEIS: the triangle of trees with n nodes and k leaves
(You should draw the sequence as a triangle as below to get the 2-dimensional information.)
…
- 2,493
31
votes
Which graphs are Cayley graphs?
I've managed to answer a few of the latter questions, and please look below for a solution in the finite-degree case.
Theorem. There is an uncountable graph $\Gamma$ that is not a Cayley graph in …
- 1,161
3
votes
Accepted
Minimal coverings by maximal cliques
Nice question. The answer is no, not necessarily.
Theorem. There is a graph $G$ such that there is no minimal vertex
covering of it by maximal cliques. Indeed, in every vertex covering
$\cal C$ of $G …
- 236k
3
votes
Does the shortest distance between two cities of a Traveling Salesman Problem always appear ...
The answer is no.
Consider five cities, with $(a,b), (b,c), (c,d), (d,e)$ each having cost $2$, and $(b,d)$ cost $1$, but all other edges much more expensive. The shortest path visiting every city i …
- 236k