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 4600
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.
1
vote
Can someone please help me understand the concept of twins?
You can use this: if $u\ne x$, $$dist(u,x)=1+\min\{dist(w,x):uw\in E\}.$$
- 24.8k
1
vote
0
answers
77
views
Path that meets every other path
In a directed graph $G$, what do we call a path, a sequence of edges $$(v_0,v_1),(v_1,v_2),\dots,(v_{n-1},v_n)$$ of length $n$, that intersects every other path of the same length $$(w_0,w_1),(w_1,w_2 …
- 5,429
2
votes
Another graph characteristic
I don't know that your characteristic has been explicitly studied before, nor would I be surprised if it has, but it fits into a more general setting as follows.
The directed graph distance $d(a,b)$ …
- 24.8k
3
votes
Accepted
Identifying two non-adjacent vertices and the effect on the Hadwiger number
Identify two opposite vertices of the cycle graph $C_4$. This reduces the Hadwiger number from 3 to 2.
- 24.8k
5
votes
Is there a standard term for this graph/set theoretic concept?
In philosophy, this would be called family resemblance -- if $E_i\cap E_j\ne\emptyset$ and $E_j\cap E_k\ne\emptyset$ then $E_i$ and $E_k$ have a family resemblance.
That is, perhaps I have no common …
- 24.8k
3
votes
Accepted
Sum-graph over an infinite set
No, let $S=2\mathbb N$, the set of even numbers.
Then $2\mathbb N$ and $2\mathbb N+1$ (the set of odd nunbers) are two distinct connected components of $G_S$. (Also, they are both complete subgraphs …
- 24.8k
4
votes
Accepted
Removing subtrees
Yes. In fact you can take the tree corresponding to all sequences $ x$ of 0s and 1s such that the fraction of 1s is no more than 2/3.
- 24.8k
1
vote
Accepted
How to infer missing nodes from a path?
Algorithm
create the two-nearest-neighbors graph $N_2$ using the first data set. That is, let each station be connected to the two closest stations.
for a path in the second data set, assume that th …
- 24.8k
1
vote
About planar graphs?
No, it has the wrong graph genus.
http://mathworld.wolfram.com/GraphGenus.html
- 24.8k
1
vote
Natural constructions (not depending on parameters)
I guess somehow we should rule out spurious ways to depend on parameter, such as
"a graph is $k$-cliqueish if either $k=1$ and the graph is connected,
or $k\ge 2$ and the graph has a clique of s …
- 24.8k
2
votes
How dense is the set of asymmetric graphs?
There are some references and some more information in the entry on the number of asymmetric graphs on n nodes in the OEIS (Online Encyclopedia of Integer Sequences):
F. Harary and E. M. Palmer, Grap …
- 24.8k
5
votes
Accepted
Path cardinality for random $(a+b)$-ary infinite trees
Yes, $T(a,b)$ has continuum cardinality when $a+b>1$... with positive probability. Of course there is also positive probability that $T(a,b)$ has no infinite paths, if $a<1$ and $b<1$.
$T(1,0)$ h …
- 24.8k