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 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.
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
4
votes
Strongly connected DAG from any connected undirected graph?
The answer to both questions is negative, if one wants to have an acyclic digraph that is strongly connected, in the sense that any two nodes have a directed path between them in one direction or the …
- 236k
5
votes
Representing repeated structure in graphs
Once you have found the smallest description of a graph (in your favored scheme), then a philosophically minded person will say, Yes, but how about the smallest description-of-a-description of a graph …
- 236k
1
vote
Functions and graphs
It's not true even for $n=1$. Consider the graph with two nodes, $a$ and $b$, with edges as follows:
$a\to a$
$a\to b$
$b\to b$
Thus, $a$ has exactly two out-arrows, $b$ has exactly two in-arrow …
- 236k
3
votes
Why are some tilings introduced as geometrical objects, not graphs?
Some very interesting types of tiling problems have a trivial graph. For example, the Wang tiling problem uses square tiles, which are labeled on the sides, and the rule for the tiling is that the lab …
- 236k
4
votes
Isn't a graph to be considered isomorphic to its complement, actually?
Perhaps what Hans means is simply that any graph has exactly the same information as the complement graph, because if we know completely where there are no edges, then we also know completely where ar …
- 236k
5
votes
Accepted
Graph properties and infinite FOL sentences
Let me suppose for simplicity at first that we are speaking here just of countable graphs. There are continuum many isomorphism types of countable graphs, and any collection of such isomorphism types …
- 236k
9
votes
Accepted
Characterization of transitive closure graphs
There are a few problems with what you wrote.
First, you probably want $TC(\{X\})$ rather than $TC(X)$, since you want $X$ to be an element, not just a subset, since it is the node corresponding t …
- 236k
1
vote
Infinite graphs with finitely discriminable vertices
(Please se the edit history for my previous answer.)
I believe the interesting question here is whether we can
assign to each node in a countable directed graph $G$ a
finite induced pointed subgraph …
- 236k
30
votes
Accepted
Human checkable proof of the Four Color Theorem?
This is too long for a comment, so I am placing it here.
In this article of the Notices of the AMS, Gonthier describes a full formal proof of the four-color theorem, which makes explicit every logica …
- 236k
31
votes
3
answers
2k
views
Is the Rado graph a Cayley graph? If so, what is the group like? (And other questions...)
The countable random graph, also known as the Rado graph, is characterized as the unique countable graph in which every two disjoint finite sets $A$ and $B$ of vertices admit a vertex $p$ connected to …
- 236k
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
5
votes
Minimal labeling of a directed acyclic graph
Perhaps it is helpful to mention that an equivalent formulation of your question concerns partial orders rather than graphs.
Namely, if $(V,E)$ is a directed acylic graph, then your reachability rela …
- 236k
2
votes
Accepted
Name for "lower/upper bounds" of arbitrary relations?
If your relation is at all order-like, then I would recommend just staying with the upper/lower bound terminology. And unless I misunderstand you, the example you describe is actually a (strict) parti …
- 236k
8
votes
Accepted
A distinguishing node property in trees?
I have a counterexample. It is not enough just to count leaves, since this doesn't take into account the number of possible ways to arrive at those leaves.
Consider the graph below.
A - B - C - …
- 236k