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 17581
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.
10
votes
Accepted
Counting with trees
Let me complete Sam Hopkins' answer.
The expression on the left is
$$
\Psi\left(\sum_{i_1+\dots+i_{n+1}=n-1}{n-1\choose i_1,\dots,i_{n+1}}\prod_j x_j^{i_j+1}\right)\\
=\sum_{i_1+\dots+i_{n+1}=n-1} …
- 23.7k
3
votes
Clique number and a special partition
Set $U_i=\{a_{1i},a_{2i},a_{3i}\}$ for $i=1,2,3,4$, and let $a_{ki}$ be connected to $a_{\ell j}$ iff $k\neq \ell$ and $i\neq j$ (in other words, this is the tensor product of $K_3$ and $K_4$). Then a …
- 23.7k
2
votes
Accepted
Acyclic partition of edges in tournaments
Edited again --- now I realized what second question was, and luckily enough the construction works in order to answer it in the negative.
Set $V=\mathbb Z/15\mathbb Z$; let the arcs be of the form $i …
- 23.7k
4
votes
Accepted
Lower bound for the size of a family of sets
Assume that $m=k^2$. Set $A_1’=\{p_1,\dots,p_k\}$, $A_2’=\{q_1,\dots, q_k\}$, and put $B_{i,j}’=A_1’\cup A_2’\setminus \{p_i,q_j\}$ (so there are $k^2$ sets of the form $B_{i,j}’$). Then $|\mathcal F’ …
- 23.7k
1
vote
Accepted
Existence of a short path in a convex graph drawing
What if we double one vertex in $K_4$, as in the picture?
- 23.7k
0
votes
Isometric path cover number of the 2 dimensional grid graph
Assume you have $a$ increasing paths (where both coordinates non-strictly increase) and $b$ decreasing ones. We may assume that all of them start and finish at the vertices of the square.
Now perform …
- 23.7k
2
votes
Graphs admitting an 1-Lipschitz map from edge mid-points to vertices
I assume that $p$ should map each edge to one of its endpoints. Under this assumption, any vertex projection $p\colon E\to V$ corresponds to orientation of all edges (edge $e$ is oriented towards $p(e …
- 23.7k
6
votes
Accepted
Pair matching between divisors less and more than $\sqrt{N}$
Here is a proof that $M(n)>0$.
Denote $[\alpha]=\{0,1,\dots,\alpha\}$. All divisors of $n$ correspond, in a natural way, to the points in a parallelepiped $P=[\alpha_1]\times\dots\times [\alpha_k]$. F …
- 5,429
6
votes
Do graphs with an odd number of walks of length $\ell$ between any two vertices exist?
Here is a combinatorial argument; surely, it can also be rewritten in an algebraic way using the adjacency matrices.
As usual, $N(v)$ denotes the set of vertices adjacent with $v$. We also denote by …
- 23.7k
2
votes
Counting number of special subset of vertices in a tree
Let us prove the desired bound $2(n-3)^2$ for the number of unordered odd pairs by induction on $n$, base case being $n=4$.
Suppose that $n\geq 5$. Take a leaf $a$ with a unique neighbour $b$; let $\d …
- 23.7k
2
votes
Conjecture on minimum size of graph
Let us prove that any graph with $\chi_1(G)>n$ has at least $2n^2$ edges (with no assumptions on $\chi(G)$). This provides a sharp estimate (and the method also shows how to construct an optimal graph …
- 23.7k
7
votes
Accepted
Determinant of walk matrix for a skew-symmetric matrix of even order
Surely, there is nothing special in the all-ones vector: the claim holds for any integer-valued $e$.
Notice that
$$
\det W^TW
=\det\bigl[e^T (-1)^iS^{i+j}e\bigr],
$$
Since $S$ is skew-symmetric, w …
- 52.4k
5
votes
Accepted
If $G$ is an infinite graph where $v_{i,j}$ is joined with $v_{k,i+j}$ for all $k,i,j$ then ...
The chromatic number is indeed infinite.
Assume that there is a proper coloring in finitely many colors. Denote by $S_i$ the set of colors of the vertices having the form $v_{k,i}$ (for some $k$). The …
- 23.7k
4
votes
Accepted
Chromatic number of a family of graphs
The concept you introduce is called a cooperative coloring. Check out, e.g., this paper. Theorem 1 (with a reference to another paper) claims a negative answer to your question; but there is other inf …
- 23.7k
7
votes
Accepted
Is there a bijective proof of an identity enumerating independent sets in cycles?
It seems that I’ve seen this question here before, but I am not sure whether it had a bijective answer. Anyway, here you are.
Enumerate the vertices in two copies of $C_m$ as $1,2,\dots,m$ and $1’,2’, …
- 23.7k