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 9025
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
Is there any vertex-transitive non-Cayley graph with 24 vertices and valency 5?
Yes, there is one, see this paper.
You can fetch it from Gordon Royle's collection.
- 37.7k
7
votes
Accepted
Reference Request: Graph Edge Density
For cycles of odd length, the only extremal graphs for large $n$ are complete bipartite graphs with the sides as equal as possible. For smaller $n$ there can be other extremal graphs. The complete sto …
- 37.7k
6
votes
Accepted
Is there any digraph data set that gives all directed graphs satisfying certain requirements?
There are 154108311168 tournaments on 12 vertices and you can make them with the tool gentourng that comes with nauty.
The number of connected digraphs on 10 vertices is more than 10^20, which is im …
- 37.7k
7
votes
Accepted
Maximal acyclic subgraph
Arbitrarily label the vertices $1,\ldots,n$. Choose all edges $a\to b$ such that $b\gt a$. This is acyclic and exactly half the directed edges in the graph, which is obviously the best possible.
If …
- 37.7k
3
votes
a necessary condition for a nonempty graph being a line graph
No. The graphs you define are called "quasi-line graphs" and are a larger class than line graphs. If you search for "quasi-line graph" you will find a lot of literature on them.
The simplest counte …
- 37.7k
4
votes
Accepted
Directed Minimal Cuts in a DAG
Take two full binary trees, one directed towards the root and one away from the root. Identify the leaves of the two trees, so that the two roots become the source and sink of a DAG. If the number of …
- 37.7k
4
votes
Accepted
Are there 2-connected regular graphs whose maximum matching leaves 3 vertices uncovered?
Take an even number $r\ge 4$. Take $r$ copies of a 3-connected graph $G$ which has odd order and is regular of degree $r$. Add two new vertices $x$ and $y$. For each copy of $G$, remove one edge an …
- 37.7k
11
votes
Accepted
Bound on the number of minimal vertex covers of a graph
The union of $k$ triangles has $3^k$ minimum vertex covers. You can easily find connected examples.
- 37.7k
14
votes
Accepted
Genus of a graph
No. The two subgraphs can share the surface more efficiently than that. Take a graph $G$ with genus $g\ge 1$ and duplicate each edge. If you don't like double edges, subdivide them with new vertices …
- 37.7k
2
votes
Looking for monochromatic cycles in an edge-coloured clique
A lot of data regarding specific instances of this problem can be found in Radziszowski's survey, see the part "survey" starting on page 36.
- 37.7k
3
votes
Degree of faces in a regular graph
It makes a huge difference what restrictions are imposed. Without any restriction on connectivity or edge type, you can put every edge on a single face (a path of double edges with a loop at each end …
- 37.7k
2
votes
What graph invariants are fast to compute?
Maybe there is a problem with processing of digraphs in sage. nauty takes 0.07 seconds to canonically label each of the graphs $(17;1,3)$ and $(17;3,1)$. They are indeed isomorphic. This translates t …
- 37.7k
0
votes
Question about the balance of a signed graph construction
The only connected graphs whose balance is independent of the edge ordering are trees and polygons.
Obviously trees have this property.
A connected graph which is neither a tree nor a polygon contai …
- 37.7k
3
votes
What graph parameters are determined by parameters for strongly regular graph
The number of cycles of length 3,4,5 are determined. If the girth is 4, the number of 6-cycles is determined too.
- 37.7k
1
vote
Resticted number of edges, optimal connected graph
http://en.wikipedia.org/wiki/Degree_diameter_problem
- 37.7k