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 12481
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.
2
votes
0
answers
68
views
Is this infinite family of non-trivial snarks resulting from the first Celmins-Swart?
Non-trivial snark is cubic graph with chromatic index $4$, girth
at least $5$ and doesn't to contain three edges whose deletion results in a disconnected graph, each of whose components is nontrivial. …
- 25.4k
3
votes
1
answer
103
views
Let $S$ be the nonempty set of strongly regular graphs with given parameters. Must $S$ conta...
As the title says, let $S$ be the nonempty set of strongly regular graphs with given parameters. Must $S$ contain vertex transitive graph?
I suspect the most likely counterexample would be $|S|=1$.
- 25.4k
7
votes
Independence Number of Graphs
This is false.
Let $G$ be with edges $ [(0, 2), (0, 3), (0, 5), (1, 3), (1, 4), (1, 5), (2, 4), (2, 5), (3, 5), (4, 5)] $
and $H$ with edges $[(0, 2), (0, 3), (0, 4), (0, 5), (1, 2), (1, 3), (1, 4) …
- 25.4k
1
vote
What is the independence number of hamming graph?
Experiments suggest it might be $q^{d-1}$.
Here is data from sage:
d= 2 q= 2 alpha= 2 factor= 2 alpha - q^(d-1) 0
d= 2 q= 3 alpha= 3 factor= 3 alpha - q^(d-1) 0
d= 2 q= 4 alpha= 4 factor= 2^2 alp …
- 25.4k
4
votes
Accepted
Genus of a simple graph
Second try. I believe $K_{6,3}$ is a counterexample.
It is genus $1$ and contains $2$ edge disjoint $K_{3,3}$s sharing only
$3$ vertices.
Explicitly:
K_{6,3}=[(0, 6), (0, 7), (0, 8), (1, 6), (1, 7) …
- 25.4k
2
votes
0
answers
124
views
Maximizing the minimum outdegree of digraph without $m$ cycle
Let $G$ be a simple digraph on $n$ vertices without a directed cycle of length $m$
(it may have directed cycles of length less than $m$. The cycles need not be simple).
How large the minimum outde …
- 25.4k
7
votes
Accepted
A conjecture about Hamiltonian cycle
I think Gordon Royle and Joseph O'Rourke answer it here
A graph is uniquely hamiltonian if it has exactly one Hamilton cycle
Apparently, however, there are uniquely hamiltonian graphs with minimum de …
- 25.4k
2
votes
Is there any partition of a regular graph which in any part there exists a vertex with all i...
I think this is possible.
First note that it if the graph is disconnected it is trivial.
Consider two copies of this graph:
Vertices $4$ and $5$ are degree $3$ and all other are $4$.
Vertex $3$ …
- 25.4k
1
vote
0
answers
47
views
Complexity of computing the Tutte polynomial of multigraph when the Tutte polynomial of the ...
Let $G$ be multigraph with $l$ loops and $m$ multiple edges and $G'$ be the
underlying simple graph (loops and multiple edges removed).
Assume the Tutte polynomial of $G'$ is given.
Q1 What is th …
- 25.4k
5
votes
1
answer
218
views
Complexity of counting MAXCUT in planar graphs -- seemingly contradicting claims
Confusion is likely. Appears to me two papers give contradicting claims
about the complexity of counting MAXCUT in planar graphs.
Exact Max 2-SAT: Easier and Faster p. 6
However, counting the num …
- 25.4k
0
votes
0
answers
154
views
For which matrices deciding permutation similarity is polynomial?
Q1 For which matrices deciding permutation similarity is polynomial?
It is not easier than graph isomorphism (and very likely is equivalent to it).
If necessary, assume the entries are nonnegati …
- 25.4k
2
votes
1
answer
180
views
Graph classes where finding explicit coloring have certificate that it is minumum
Graph coloring doesn't have certificate that smaller coloring doesn't exist in general.
I am looking for graph classes where finding explicit coloring is not polynomial and have polynomially verifiab …
- 25.4k
5
votes
Accepted
Number of graphs on a given set of vertices with maximum degree of $2$
This is OEIS A003292 Number of 4-line partitions of n decreasing across rows.
a(n) is the number of unlabeled graphs on n nodes whose connected components are a path or a cycle. - Geoffrey Critzer …
- 25.4k
3
votes
Accepted
Can the Vertices of cubic graph be partitioned into and induced cycle and a forest?
I believe this is false.
EDIT
The previous counterexample was wrong, let me try again.
A program found counterexample on $10$ vertices and exhaustive search
confirmed it.
The edges are:
[(0, 3), …
- 25.4k
2
votes
1
answer
259
views
The edge chromatic number and pefectness of inflation of cubic graph
The inflation of graph $G$ is a graph $I(G)$
which is obtained by replacing each vertex $x$ by a complete graph
$K_{\deg(x)}$ and joining each edge to a different vertex of $K_{\deg(x)}$.
Let $G$ b …
- 25.4k