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 158328
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
2
answers
163
views
Graphs vs matrices (when $0$ weight edges are allowed) [closed]
EDIT:
I have asked for closing this question, and posted an improved version on math.se.
I hope this is ok.
It is often claimed, including by myself for the last 20 years, that matrices are equivale …
- 1,444
1
vote
Accepted
Notation for H is isomorphic to a subgraph of G
Inspired by the $\simeq$ notation for isomorphic structures, I would suggest $\lesssim$, $\prec$, $\precsim$, or this symbol.
The pair of symbols $\prec$ and $\precsim$ have the advantage of providing …
- 1,444
3
votes
1
answer
156
views
Planar graphs - more or less
A graph is planar if it can be drawn on the plane in such a way that its edges do not cross each other.
A graph is $k$-planar if it can be drawn on the plane in such a way that each of its edges is cr …
- 1,444
0
votes
Accepted
Fast uniform generation of random graphs with given degree sequences - any implementation?
The implementation by Nick Wormald and colleagues is available from his webpage.
- 1,444
1
vote
Primacy of arcs/arrows over vertices/objects
Notice that graphs model relations, and that many courses (at least mine!) emphasize the fact that, by studying graphs, one focuses on relations between objects, instead of objects themselves.
For ins …
- 1,444
4
votes
2
answers
200
views
Fast uniform generation of random graphs with given degree sequences - any implementation?
The paper below presents a linear-time algorithm for uniform generation of random graphs with given degree sequences [1].
This is very interesting in practice, but I found no implementation. However, …
- 1,444
4
votes
Seven Bridges of Königsberg for hypergraphs
Imagine a virus spreads between individuals when they are in the same room. Then, consider the hypergraph where each hyperedge is the set of individuals who happened to be together in a same room. It …
- 1,444
4
votes
Accepted
Random graphs defined by a set of tiles
The question you ask is, in my opinion, extremely important: decomposing a graph into a (small) set of small graphs (the tiles or ego-centered sub-graphs, for instance), and then characterizing how th …
- 1,444
7
votes
Is there a term for a subgraph which includes all the edges of a graph?
If the subgraph includes all edges of the original graph, then it also includes all its vertices, except maybe some with degree $0$.
The minimal such subgraph is the graph in which all $0$-degree vert …
- 1,444
4
votes
Smallest $3$-regular graph with a unique perfect matching
Regarding your second even better question, I warmly suggest the Brendan McKay page on combinatorial objects, that gives many kinds of graph examples.
- 1,444
3
votes
Centrality measures in a network with negative correlations
These measures are in general designed for unweighted graphs, and extending them to weighted graphs already is non-trivial. Extending them to signed weighted graph is even more difficult.
For instance …
- 1,444
2
votes
The distance distribution of graphs
I see several reasons why degree distributions may be preferred to distance distributions.
First, degrees are more robust than distances, in the following sense: adding or removing one or a few links …
- 1,444
1
vote
Degree sequences after vertex removals
Several works study the degree sequence obtained when vertices are removed from random graphs with given degree sequence. Vertices are generally removed by decreasing order of degrees, or uniformly at …
- 1,444
3
votes
1
answer
240
views
Temporal generalization of graphs: density vs $n$ and $m$?
In short: we generalize graphs to the temporal case, but fail to fully preserve the usual relation between density, number of vertices, and number of edges; how to make better?
Context.
We propose a …
- 1,444
5
votes
3
answers
794
views
Probability of an edge in a random graph
Consider a vertex set $V$ and a degree sequence $(d_v)_{v\in V}$. I want to know the probability that an edge exists between two given vertices $u$ and $v$ in a random graph with this degree sequence. …
- 1,444