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 440
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.
4
votes
Accepted
Planar Graphs with #Vertices = #Faces
Unlike some other planar graphs, these ones always contain at least one triangular face and at least one vertex of degree $\le 3$. The reason for the first property is that, by Euler's formula, the nu …
- 18.6k
4
votes
Accepted
What is the relation between Treewidth and Order of graph?
The treewidth of an $n$-vertex graph is always at most $n-1$ (because it is defined as one less than the cardinality of the largest bag in an optimal tree decomposition, and each bag is a set of $n$ o …
- 18.6k
5
votes
Accepted
Which graphs are prime under the Cartesian product?
For connected graphs, they are the graphs in which every two edges are connected by a sequence of pairwise relations using one or both of the following two types of relation:
Edge $xy$ and $uv$ are …
- 18.6k
3
votes
Properties of bipartite graphs
No. For instance a 3x3 grid is a median graph (it has a unique median for every three vertices, a stronger version of your property 2 which does not require uniqueness) but it is not chordal bipartite …
- 18.6k
2
votes
Is there currently a known way to construct an injective mapping that transforms finite grap...
Map any $n$-vertex graph $G$ into a collection of $n$ points in $(n-1)$-dimensional space that are all at unit distance from each other, together with a line segment connecting two points whenever the …
- 18.6k
9
votes
Request for examples of 4-regular, non-planar, girth at least 5 graphs
If a planar graph has girth four or more, it can have at most $2n-4$ edges, but every 4-regular graph has exactly $2n$ edges, so every 4-regular graph with girth $\ge 4$ is nonplanar. That is, your re …
- 18.6k
4
votes
Accepted
vertex independent set and the maximal clique
If $G$ is an odd cycle (as commented above), the answer is no. If it's an $(n+1)$-clique, it meets your degree condition but not your condition on the clique number. And if it's neither a clique nor a …
- 18.6k
3
votes
Accepted
How to calculate the maximum number of rainbows for arbitrary graphs?
For arbitrary graphs, the problem is NP-complete. It includes as a special case the problem of coloring the edges of a 3-regular graph with three colors, so that each vertex is rainbow, which was show …
- 18.6k
3
votes
Complement of a Cayley graph
The complete graph on $|G|$ vertices is a Cayley graph for $S=G\setminus\{1_G\}$. Its complement, the graph without edges, is not a Cayley graph.
- 18.6k
4
votes
Accepted
7
votes
Accepted
Graph Theory: question regarding a class of digraph
Qiaochu Yuan has already provided an answer in terms of functions, but if you prefer to think graph-theoretically these things are known as directed pseudoforests.
- 18.6k
4
votes
Interesting families of sparse graphs?
Minimally rigid graphs in d dimensions. For d=2 these are the Laman graphs but I don't think any kind of clean combinatorial description of these graphs is known for higher dimensions.
- 18.6k
2
votes
Graphs with fractal properties?
Your idea of transforming nodes into sets of nodes sounds a lot like graph grammars — see e.g. this Wikipedia article.
- 18.6k
5
votes
Accepted
A graph connectivity problem (restated)
It appears to be NP-complete even when m=1: see The Complexity of the Matching-Cut Problem, Maurizio Patrignani and Maurizio Pizzonia, WG 2001, http://dx.doi.org/10.1007/3-540-45477-2_26
- 18.6k
10
votes
Recognition of graph families.
It's too big to fit into one table, but I believe what you want is the Information System on Graph Classes and their Inclusions. In particular, for each of over 1200 graph classes listed on this site, …
- 18.6k