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 4312
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.
4
votes
The max-clique chromatic number of a graph
If $\chi(G)$ is finite, and all maximal cliques have size at least 3, you may take a graph coloring and unite two colors. This gives a proper coloring of the maximal cliques hypergraph with strictly l …
- 109k
4
votes
Counting with trees
Well, and for what it worth an elementary proof. Let $\mathcal{F}_k$ denote the set of forests with $k$ trees, vertex set $\{1,2,\ldots,n+1\}$, and one labelled root in every component. Define the wei …
- 109k
5
votes
Counting with trees
Another way to find the value of the sum
$$
S:=\sum_{T} \prod_{i=1}^{n+1} d_i(T)!
$$
using Cayley formula
$$
\sum_{T} x_1^{d_1(T)}x_2^{d_2(T)}\cdots x_{n+1}^{d_{n+1}(T)} = x_1x_2\cdots x_{n+1} (x_1+x …
- 109k
3
votes
Accepted
Petersen graph does not have a nowhere-zero 4-flow
Here is Tutte polynomial of Petersen graph
$$x^9 + 6x^8 + 21x^7 + 56x^6 + 12x^5y + y^6 + 114x^5 + 70x^4y
+ 30x^3y^2 + 15x^2y^3 + 10xy^4 + 9y^5 + 170x^4 + 170x^3y
+ 105x^2y^2 + 65xy^3 + 35y^4 + 180x^3 …
- 109k
5
votes
Accepted
Countable graph with $2^{\aleph_0}$ non-isomorphic induced minors
Yes, even for induced subgraphs (which are in particular induced minors). For Rado universal countable graph (a.k.a. Erdős—Renyi countable random graph), every countable graph is its induced subgraph. …
- 109k
8
votes
Accepted
*Friendly* coloring of a digraph
Carsten Thomassen (1983) proved that a digraph with minimal out-degree at least 3 has two vertex-disjoint cycles, call them $C_1$, $C_2$ and color black and white respectively. Then proceed as follows …
- 12.9k
4
votes
Topology of directed graph $G$ with non-singular adjacency matrix
Well, if $V=\{1,\ldots,n\}$, $(a_{ij})_{1\leqslant i,j\leqslant n}$ is the adjacency matrix, and it is non-singular, then its determinant (considered as a sum over permutations) has a non-zero term $\ …
- 109k
5
votes
Accepted
Graph on $\mathbb{N}$ where almost every vertex is shy
All vertices can be shy. You may add edges to your graph recursively, on $n$-th step fixing all edges from $1,2,\ldots,n$ and possibly some other (finitely many) edges, so that $1,2,\ldots,n$ already …
- 109k
19
votes
Accepted
Universal graph
I think that the answer is negative.
Assume that such graph $G$ on the vertex set $\{v_1,v_2,\ldots\}$ exists. We construct our not-embeddable graph $H$ on $\{1,2,\ldots\}$ by steps. On the $i$-th ste …
- 109k
4
votes
Accepted
Subset of the vertices in a tournament
Not always. I claim that for large $n$ a random tournament on $n$ vertices satisfies your property with probability tending to 0.
We use the following
Lemma. Consider a random tournament on $m$ vertic …
- 109k
5
votes
Accepted
Existence of adjacent $a, b$ in a general bipartite graph (with a special degree condition) ...
Let each vertex $b\in B$ have a can of jam of weight 1, and share it with all neighbours from $A$ equally. There should be a vertex $a\in A$ which got at least $|B|/|A|$ of jam, she got at least $|B|/ …
- 109k
2
votes
Accepted
Prove $G$ is regular if $d(u, v)$ is $x$ for adjacent $u$ and $v$ and is $y \ge 2$ otherwise
I use the notations $V$ for the set of vertices, $E$ for the set of edges, $E(U)$ for the set of edges with both endpoints in $U\subset V$; $E(U_1,U_2)$ for the set of edges with one endpoint in $U_1$ …
- 109k
7
votes
Accepted
Random spanning trees probability problem
Here is a proof that the variance of $d_T(v)$ does not exceed $\frac14(\deg v-1)$.
For every edge $e\in E$ take a variable $x_e$ and consider the polynomial $$P:=\sum_T \prod_{e\in T} x_e,$$
where the …
- 109k
5
votes
Accepted
Arboricity and average degree
Denote $A(G)=A$. Let $H$ be the subgraph for which $\lceil \frac{|E_H|}{|V_H|-1}\rceil=A$. Write $e$ for $|E_H|$, $v$ for $|V_H|$. We have $e/(v-1)>A-1$, thus $e>(v-1)(A-1)$. On the other hand, $e\leq …
- 109k
2
votes
Accepted
Minimal dominating sets in flat graphs
For flat graphs, dominating sets satisfy Zorn's condition: the intersection of a chain of dominating sets $D:=\cap D_\alpha$ is dominating. Indeed, for any vertex $v$ the finite set $\{v\cup N(v)\}$ h …
- 109k