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 8008
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
Bondy and Simonovits Proof for Small Graphs
That particular theorem is a "for all large enough $n$..." type result so I don't think it says much for small $n$. I'm not sure what would count as an equivalent formulation but it is interesting to …
- 30.1k
3
votes
Minimal clique decompositions
Similar to Ben's answer is an octahedron which is $K_{2,2,2}$ and also $K_6$ minus a matching. There should be an enormous number of minimal covers for other complete multipartite graphs and for $K_{2 …
- 30.1k
1
vote
Odd circles and doubly covered edges
Consider a triangular prism with $6$ vertices and $9$ edges. You need to pick two vertices from each triangle and that also chooses both ends of another edge. That is a problem if you view it as two …
- 30.1k
4
votes
Accepted
What type of Hamming Graph is this?
Do you have all $k^n$ strings of length $n$ using your $k$ symbol alphabet or a selection such as all consecutive 30 letter strings found in the DNA of some individual. The former is a Hamming graph b …
- 30.1k
3
votes
Accepted
Generalized graph products in view of vertex-transitive graphs
For the second question Will's example is to the point. Another description: start with a $k$-gon ($k \gt 3$ an odd prime) and decide that the obvious cyclic group will act transitively on the final g …
- 30.1k
2
votes
Accepted
Symmetry preserving graph products
Revised answer (see previous version to make sense of comments):
The Petersen graph is a small wonderful and rather exceptional creature. It is not a paradigm.
Does this graph fit your construction …
- 30.1k
4
votes
graphs that are intervals
What do you know about graphs with this property? I don't know any terminology which would be widely recognized. There is much terminology which can be utilized. to create a name.
A graph with this …
- 30.1k
1
vote
Accepted
Matching in bipartite graphs
Is it a homework problem? (If so, it is a nice one and new to me.) So you need to rule out the existence of a set $A \subseteq X$ such that the set $B$ of all $y \in Y$ adjacent to some $a \in A$ has …
- 30.1k
5
votes
Accepted
Is the following graph well known?
They might have a name, I don't know. For the next few lines let us call each a Partial Permutation graph $PP(n,k)$ (assume $k<n$). They may not get as much respect because they are not distance trans …
1
vote
Efficient computation of a vertex-partition for graphs
As you note, for a bipartite graph you get either the bipartition or the trivial partition (according as the number of spanning trees is even or odd). Any edge whose removal (keeping its endpoints) di …
- 30.1k
1
vote
Lower bound on # spanning trees in a connected graph
I was going to guess something like what David found. But a reference certainly trumps a guess. Here is some heuristic reasoning. A connected graph of course has one spanning tree. You asked about us …
- 30.1k
3
votes
How to find central vertex in a graph?
The question should be more specific. It depends what you know about the graph .
For a tree you can erase all degree 1 vertices then repeat on the new graph and stop when there are just one or two.
…
- 30.1k
3
votes
Notation for a graph without any edges?
I suppose $n\cdot K_1$ assuming of course that $n \ge 1$. In the event that there are also no vertices it is sometimes called the Null Graph although F. Harary, F. and R. Read in "Is the Null Graph a …
- 30.1k
4
votes
4-regular graph with every edge lying in a unique 4-cycle
There should be lots of these, even with the second condition. So many that I can't imagine a classification. I'll call a $4$-cycle a square.
One construction is as follows: Start with an appropriate …
- 30.1k
1
vote
Accepted
Counting and constructing some special planar graphs
Consider this family of graphs which is very far from optimal but gives much more than you request: Let $n=3m+r$ and take a path of length $k=2m+r$ with vertices numbered in the obvious way and a pend …
- 30.1k