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 2233
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
Is this special line graph of a graph a known concept?
Your graph is a subgraph of the total graph of $G$. Both graphs have the same vertex set, and each edge in your graph is an edge in the total graph, but yours is missing edges for all the vertex-vert …
- 32.1k
4
votes
Accepted
Degrees and common neighbors
No. And they can in fact be arbitrarily far apart. To see this let $G$ be two disjoint copies of $K_n$, and let $H$ be $K_{n,n}$ minus the edges of a perfect matching. Let $\varphi$ be a map that s …
- 32.1k
2
votes
Accepted
Connected homogeneous graphs
Homogeneous is usually called vertex transitive. Not all connected regular graphs are vertex transitive. For example, the Frucht graph is a 3-regular connected graph that is not vertex transitive (i …
- 32.1k
1
vote
Accepted
Lower bound for number of vertices in graph with certain forbidden minor
There is such a graph with $k+2$ vertices for all $k \geq 4$. To see this, first assume that $k$ is even. Let $G$ be $K_{k+2}$ minus the edges of a perfect matching. Note that every vertex of $G$ h …
- 32.1k
1
vote
Turan's theorem for connected graphs?
This is not an answer, but it became a bit too long for a comment.
If we let $\tau(n,k)$ be the number of edges in the complement of the Turan graph $T(n,k)$, then the minimum number of edges a con …
- 32.1k
3
votes
Accepted
Hamiltonian path in graphs of diameter and minimal degree $2$
No. Glue a bunch of triangles together at the same vertex. For a $2$-connected example, take the previous example and add a universal vertex.
For an example that is $n$-connected take $K_{n, n+2}$ …
- 32.1k
1
vote
Accepted
the length of cycles in a $2$-connected simple gragh
Here is a quick reduction. Hopefully someone else can finish it off. Since $G$ is 2-connected, it has an ear-decomposition starting with the cycle $C$. Next, when building the ear-decomposition, fo …
- 32.1k
4
votes
Topological Irreducible graphs for the projective plane
Here is an expansion of my answer in the comments. A graph $G$ is irreducible for a surface $\Sigma$, if $G$ does not embed in $\Sigma$, but for every proper subgraph $H$ of $G$, $H$ does embed in $\ …
- 32.1k
1
vote
Accepted
Gallai's lemma from Tutte's theorem?
Gallai's Lemma certainly follows from the somewhat more general Tutte–Berge formula, which easily follows from Tutte's theorem.
Let $G$ be a connected graph such that $\nu(G-u)=\nu(G)$ for all $u \ …
- 32.1k
2
votes
Graphs where every two vertices have odd number of mutual neighbours
Maybe I'm missing something, but I'm not sure that the third condition actually generates what I'll call odd graphs. For example, if I let $A$ be the graph consisting of a single vertex and $B$ be th …
- 32.1k
2
votes
Complete vertex invariants
I think the main reason why they have not attracted much attention is due to vertex-transitive graphs. In the case that $G$ is vertex-transitive, then $V(G)$ consists of a single conjugacy class. Th …
- 32.1k
2
votes
Proving edge connectivity
I don't think your argument quite works. In particular, you can't really conclude anything about the lengths of your paths. Here's a sketch of a proof using Menger's Theorem. By way of contradictio …
- 32.1k
3
votes
Accepted
on counting of special case of trees on a graph
I'll answer a question raised in the comments:
Problem: Count the number of induced trees of size $k$.
According to this paper by Erdös, Saks and Sos, it is NP-complete to decide given a graph $G$ a …
- 32.1k
2
votes
Graphs having unique hamiltonian paths between exactly 4 pair of vertices
This answer elaborates on Willie Wong's comment and also provides another class of examples. Start with a clique $K_n$, pick two vertices $u, v \in K_n$, and glue two triangles onto $K_n$ at $u$ and …
- 32.1k
3
votes
Combinatorial Proof of Weak Perfect Graph Theorem.
Lovász' original 1972 proof of the (weak) perfect graph theorem was completely combinatorial. The proof can be found in Diestel's book Graph Theory, which you can peruse for free online here. It is …
- 32.1k