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 955
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
Accepted
5
votes
Accepted
A conjecture about odd path and odd cycle
False. As we want a counterexample, we naturally start with the Petersen graph, P. Note that for any vertex v of P and non-adjacent edge uw of P there is a Hamiltonian path from v to w that does not u …
- 19.1k
2
votes
the length of cycles in a $2$-connected simple gragh
Here is a proof for the simplest case, as you define it in your comment to Tony's answer.
In this simplest case you essentially have a 3-regular graph that has a Hamiltonian cycle and you ask whether …
- 19.1k
1
vote
A conjecture on longest paths in a bipartite+path graph
Let's relax your question as follows:
Suppose that the minimum degree requirement is only 2, and for the interior vertices of $P$ it is 3.
Also, $P$ needn't be induced, so let's only suppose that $V\s …
- 19.1k
3
votes
Accepted
Push function on simple undirected graphs
Yes. If you have an odd cycle, then you can reduce the size of the image by first pushing two different vertices of the current image to the cycle, and then push them to the same vertex. So a graph is …
- 19.1k
1
vote
Accepted
A bound on coefficient of independence polynomial
Yes. If you take the complement of your graph, then you get the clique density problem, which was solved recently: https://arxiv.org/abs/1212.2454
- 19.1k
6
votes
Accepted
What is the maximum of the ratio $\vartheta(G)/\alpha(G)$?
It is infinite, in fact much stronger versions are also true, see e.g., Theorem 1 here:
http://arxiv.org/abs/cs/0608021
(Shannon capacity is between $\alpha$ and $\vartheta$.)
- 19.1k
3
votes
Correspondence between spanning Trees and Even Subgraphs in a Graph
Well, I might be totally off again, but I think that for every spanning tree $T$ we get $H(T)=G$. As you have already written, obviously $E(G)-E(T)\subset E(H(T))$. For a tree edge, $e\in E(T)$, denot …
- 19.1k
5
votes
Non-unique 2-factorization of 2k-regular graphs
No and in fact your multigraph construction is the counterexample. Just replace each edge with an "almost 6-regular" graph, like $K_7$ minus one edge, uv, and connect u and v respectively to the endpo …
- 19.1k
4
votes
Accepted
Local complementation in undirected graphs
Warning. I just realized that my reduction is not good as if a node has two outputs, their will be new edges created between them, so we would need a more complicated gadget. I suspect this to be doa …
- 19.1k
3
votes
Does every graph $G$ contain a triangle-free subgraph $H$ such that $H \cup e$ contains exac...
This is false. Here is how to construct a counterexample.
Suppose $abc$ is a triangle in $G$.
Also suppose that there are many (at least two) vertices in $G$ whose only neighbors are $a,b,c$.
A simple …
- 19.1k
9
votes
Is every path with this property shorter than another path with the same endpoints?
A very natural special case is the following:
For any $v_i\in V_1$, there exists exactly one $v_j\in V_1\setminus \{v_i\}$ such that there is a $u\in V\setminus V_1$ such that $uv_i,uv_j\in E$.
This m …
- 19.1k
5
votes
Completing subcubic trees to cubic graphs
Yes. First make $T$ cubic in any way. In each step, while the graph has a cycle whose length is less than $g$, pick a shortest cycle $C$ and one edge $uv$ of it. There are at most $6\cdot 2^g$ vertice …
- 19.1k
5
votes
Accepted
Graph with Poisson Clock at each Vertex
Yes, my example is easy to modify after some thought, just take a thick enough layer for each level.
More precisely, let $f$ be a sufficiently fast growing function, and define the initial value on an …
- 19.1k
6
votes
Accepted
Regularizing graphs
It is always enough to add k+2 more vertices where k denotes the maximum degree. This is sharp as shown by the graph which is a cycle of length 5 plus two independent edges.
The proof is the following …
- 19.1k