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 2384
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.
5
votes
Spanning trees of $k$-edge-connected graphs
The problem of determining the minimum number of spanning trees in a connected graph on $n$ vertices and $m$ edges was first asked by Boesch, Satyanarayana and Suffel in Least reliable networks and th …
- 85.6k
2
votes
Minimum covering in cubic graphs
A subset of vertices $S$ in a graph $G$ is called a dominating set if every vertex in $G$ is in $S$ or is connected to a vertex in $S$. The size of the smallest dominating set in a graph is called the …
- 85.6k
2
votes
Accepted
Cycle double covering of cubic graphs
No. In a minimal counterexample of the cycle double cover conjecture, removing an edge creates no bridges. The reason is simple. If such an edge existed, then contracting it would yield a smaller coun …
- 85.6k
7
votes
Accepted
Name the class of graphs G s.t. every two graphs that can be created by removing one edge fr...
If all the edge-deleted subgraphs of a finite graph are isomorphic then the graph is edge-transitive. Here is a possible reference, though you might want to look at this survey on pseudosimilarity. (P …
- 85.6k
10
votes
Wanted: a graph $G$ without bridges, whose square is not hamiltonian
You can find an example of a bridgeless graph with cut points, whose square is not hamiltonian in this paper of Fleischner and Kronk. (I know the paper is in German, but the figure of the graph is on …
- 85.6k
2
votes
Accepted
Is there a planar network whose path give a TNN matrix whose entries are Eulerian numbers?
There is a Bratelli diagram which satisfies this. Consider $\mathbb N^2$ as a graph where the edges are given by k parallel directed edges from $(n,k)$ to $(n+1,k)$, and $n-k+1$ parallel directed edge …
- 85.6k
9
votes
Girth 5 graphs with diameter 2
No infinite family exists. In fact all graphs with diameter $d$ and girth $2d+1$ have to be regular, and thus are Moore graphs. This was proved in
R. Singleton, "There is no irregular Moore graph", A …
- 85.6k
8
votes
Regular tournaments
For $n=1$ you have the rock-paper-scissors tournament, and for $n=2$ it's the rock-paper-scissor-lizard-Spock tournament :). Already for $n=3$ there are three nonisomorphic tournaments which satisfy y …
- 85.6k
7
votes
Accepted
Closeness graph of a topological space
There is no topology on 4 elements whose closeness graph is the $4$-cycle.
(Proof: Let's call the elements $\{A,B,C,D\}$. Define a directed graph with these elements as vertices and a directed edge $ …
- 85.6k
1
vote
Accepted
Finding a sufficiently large complete bipartite subgraph using matrix counting
This is essentially the Zarankiewicz problem, a well known and hard problem in extremal combinatorics.
There is an upper bound to the quantity you call $F_k$, given by the Kővári–Sós–Turán theorem me …
- 85.6k
6
votes
Accepted
Edge density of triangle-free graphs
Turan's theorem says that this limit exists and is equal to $\frac{1}{2}$. The graphs that achieve this are the complete bipartite graphs. Moreover, the theorem gives the answer for the more general q …
- 85.6k
2
votes
How to construct a graph with arbitrarily large girth and large chromatic number?
Two explicit constructions as certain Cayley graphs of $\operatorname{PGL}(\mathbb F_q)$ and $\operatorname{PSL}(\mathbb F_q)$ are detailed in chapters 3 and 4 of the book "Elementary Number Theory, G …
- 85.6k
11
votes
Accepted
Is the number of vertices bounded for fixed max degree and fixed diameter?
A graph of maximum degree $\leq \Delta$, and diameter $\leq d$ can have at most
$1+\Delta\sum_{i=0}^{d-1} (\Delta-1)^i$ vertices. The graphs which attain this bound are called Moore graphs.
- 85.6k
8
votes
Automorphisms of a certain digraph defined on the set of primes? [Edited]
I would expect this digraph to have a lot of automorphisms, but I cannot prove it unconditionally.
First, notice that $2$ is the only prime with no incoming edges. The primes which have incoming edge …
- 85.6k
8
votes
Accepted
Coloring tensor products of graphs
The only way that two vertices $(u,v)$ and $(u',v')$ end up getting the same color is if $f(u)=f(u')$. But then there is no edge between $u$ and $u'$ in $G$ so there is no edge between $(u,v)$ and $(u …
- 85.6k