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.
22
votes
Accepted
Graphs with only disjoint perfect matchings
$m=3$ is indeed the maximum, and $K_4$ is the only example for this value of $m$.
Two perfect matchings form a disjoint union of cycles. If there is more than one cycle, then you may swap one of them …
- 23.7k
15
votes
Accepted
Graphs in which any two odd cycles have a common vertex
The claim on graphs without $K_5$ is a particular case of the (still open in general) Erdos--Lovasz Tihany conjecture. (Tihany is not a surname, but the name of a peninsula on Balaton lake in Hungary. …
- 23.7k
13
votes
Accepted
Can all unit-distance graphs have their vertices at algebraic integers?
$\let\eps\varepsilon$No. I will present a graph whose realization necessarily contains a pair of vertices at distance $1/2$. THis cannot happen if the vertices are algebraic integers.
Firstly, we not …
- 23.7k
13
votes
Accepted
Cancelling a graph join from a graph homomorphism
If $|K|=\infty$, then this is false, as a counterexample $G=K_2$, $H=K_1$, $K=K_\infty$ shows.
Let us prove that the claim is true if $K$ is finite (with no such assumption for $G$ and $H$). Inductio …
- 23.7k
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
7
votes
Accepted
Majority coloring for directed graphs
Let me answer Question 2. The answer is in negative: there exists an upper bound for majority coloring numbers of all tournaments. I will not care about the sharpness of the bound.
Let $G$ be a tourn …
- 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
7
votes
The maximal number of copies of a graph $T$ in an $H$-free graph
This was an answer to a previous version of the question, when $H$ was not claimed to be a tree.
It is well-known that a maximal number of edges in a $C_4$-free graph is $\Theta(n^{3/2})$ (since ever …
- 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 …
- 23.7k
6
votes
Accepted
Do graphs with $\omega(G) = \chi(G)$ grow "common" as $|V|$ grows large?
I would say that this limit is zero. Most of the graphs on $n$ vertices have $\sim n^2/4$ edges. For such graph, the expected number of complete subgraphs of size $k\sim2\log_2n$ is
$$
{n\choose k}\ …
- 23.7k
6
votes
Strongly connected directed graphs with large directed diameter and small undirected diameter?
The answer for Q1 is negative. Namely, even a strongly connected tournament may have large oriented diameter. Take the path $v_1\to v_2\to\dots\to v_n$ and connect $v_j\to v_i$ for all $i\leq j-2$.
- 23.7k
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
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 …
- 23.7k
6
votes
Smallest odd cycle in a non-bipartite graph
I care only about linear term in the answer, relaxing an additive constant. However, for $n=12k+11$ I show the tight answer.
An example I told in a comment was slightly suboptimal. An optimal one is …
- 23.7k
5
votes
Which paths in a graph are orthogonal to all cycles?
EDIT Take te multiset of all edges of $\gamma$; if it contains a pair of inverse edges, remove it, and repeat this while possible. If the resulting multiset is empty, then $c(\gamma)=0$, otherwise we …
- 23.7k