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 questions 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.
43
votes
3
answers
2k
views
History of the four-colour problem
It is stated in many places that the first published reference to the four-colour problem (aka the four-color problem) was an anonymous article in The Athenæum of April 14, 1860, attributed to de Morg …
- 37.7k
22
votes
2
answers
2k
views
Largest graphs of girth at least 6
Let $e_6(n)$ be the greatest number of edges in a simple graph with $n$ vertices and girth at least 6.
Let $G_6(n)$ be the set of simple graphs of order $n$ with girth at least 6 and $e_6(n)$ edges.
…
- 37.7k
21
votes
1
answer
1k
views
A strange sum over bipartite graphs
While mucking around with some generating functions related to enumeration of regular bipartite graphs, I stumbled across the following cutie. I wonder if anyone has seen it before, and/or if anyone …
- 37.7k
18
votes
4
answers
2k
views
Complexity of equitable partitions
We are talking about undirected simple graphs and partitions of their vertex sets into disjoint non-empty cells. Such a partition is equitable if for any two vertices $v,w$ in the same cell, and any …
- 37.7k
17
votes
0
answers
505
views
Maximum automorphism group for a 3-connected cubic graph
The following arose as a side issue in a project on graph reconstruction.
Problem: Let $a(n)$ be the greatest order of the automorphism group of a 3-connected cubic graph with $n$ vertices. Find a g …
- 37.7k
11
votes
0
answers
309
views
How many n/2-cycles can a cubic graph have
Given a simple cubic graph with $n$ vertices (which implies that $n$ is even), what is a good upper bound on the number of cycles of length $n/2$ it can have?
A random cubic graph has $\Theta((4/3)^n …
- 37.7k
10
votes
1
answer
410
views
Network flows with capacities on pairs of edges
Take a standard network flow problem: a directed graph with nonnegative capacities on each edge, a source $s$, a sink $t$. We all know how to find the maximum flow from $s$ to $t$.
Now add edge-pair …
- 37.7k
10
votes
1
answer
581
views
Maximal subgroups of a certain finite 2-group
The following came up in a problem on reconstruction of digraphs. I determined enough about the answer to satisfy the application completely, but still I am curious to know what the complete solution …
- 37.7k
8
votes
2
answers
1k
views
Spanning trees of plane graphs containing an edge of every face
I feel sure this must be known, but can I find it??
Which connected plane graphs (graphs drawn in the plane without crossings) have a spanning tree such that at least one edge of each face is in the …
- 37.7k
8
votes
0
answers
160
views
Hamiltonian paths in the prime sum graph
The following is a generalization of this old question .
Let $n\ge 2$, $[n]=\{1,\ldots,n\}$. For which distinct $a,b\in[n]$ is it possible to list $[n]$ in some order $x_1,\ldots,x_n$ such that $x_1=a …
- 37.7k
8
votes
1
answer
728
views
6-regular bipartite graphs with no 8-cycles
I'm looking for simple 6-regular bipartite graphs with no 8-cycles, as small as possible. It doesn't matter if there are 4-cycles or 6-cycles, provided there are no 8-cycles. Such graphs must exist …
- 37.7k
7
votes
0
answers
181
views
How quickly can we test if a graph is distance-regular?
A (simple, finite, connected) graph $G$ is distance regular if there exist integers $b_i,c_i,i=0,...,D$ such that for any two vertices $x,y$ in $G$ and distance $i=d(x,y)$, there are exactly $c_i$ nei …
- 37.7k
6
votes
2
answers
431
views
Measurable maximal independent set in infinite graph of bounded degree
We have a graph $G$. The vertices of $G$ are a measurable subset of $\mathbb{R}^n$ for some $n$. The degree of each vertex is bounded by some absolute finite constant $K$.
Q1. Does $G$ have a maxim …
- 37.7k
6
votes
0
answers
69
views
Digraph weak connectivity in $O(V)$ space and $O(V+E)$ time
A digraph is called weakly connected if its underlying undirected graph is connected.
You are given a digraph $G$ with $V$ vertices and $E$ edges as a read-only data structure consisting of lists of …
- 37.7k
5
votes
1
answer
118
views
Existence of regular factors in dense graphs
All graphs here are finite and simple.
A $d$-factor of a graph is a spanning regular subgraph of degree $d$.
Where can I find theorems of this nature, for constants $a,b,c\gt 0$: If $G$ is a graph w …
- 37.7k