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 24076
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.
15
votes
Always a planar-drawn cycle through $n$ points
Every shortest cycle through the $n$ points is noncrossing. This can be easily shown by contradiction: if two edges are crossing, they form the diagonals of a convex $4$-gon, and we can replace them b …
- 6,101
2
votes
Is this special line graph of a graph a known concept?
The graph $H$ is isomorphic to the intersection graph of $V\cup E$.
- 6,101
3
votes
Accepted
Can the bramble number and the strict bramble number of a graph be equal?
Indeed, for every connected graph $G$ with at least two vertices, we have $sBr(G)<Br(G)$. This follows from a theorem by Seymour and Thomas and its proof (Theorem 12.4.3 in Reinhard Diestel, Graph The …
- 6,101
1
vote
What kind of graph has more edges than its line graph?
Matchings: the line graph of a matching has no edges.
Paths: the line graph of every path of length $k\ge 1$ has $k-1$ edges.
Paths might be the only connected graphs with this property, which may be …
- 6,101
2
votes
Accepted
Edge-disjoint paths avoiding some subgraphs
This seems to be an NP-complete problem. It can be shown by reduction from
3-SAT, as follows.
For a given 3-SAT formula with $p$ variables and $m$ clauses, build a graph consisting of $2p$ internally …
- 6,101
4
votes
Algorithm to check if vertex belong to infinite path in Graph theory
If the graph $G$ can be specified by an algorithm, then the problem of deciding whether it has an infinite path is as hard as the halting problem (that is, algorithmically undecidable).
Let $U$ be a …
- 6,101
3
votes
If a graph embeds in the projective plane or the torus is there a bound on the number of edg...
Regarding Andrew D. King's interpretation: Djidjev and Vrto
showed that the crossing number of a graph with $n$ vertices and maximum degree $d$ embedded in a genus $g$ surface is $O(gdn)$, which impro …
- 6,101
2
votes
Accepted
Non-orientable genus of union of graphs
The non-orientable genus $\tilde{\rm{g}}$ is not additive: consider the union of $K_5$ and $K_7$. We have $\tilde{\rm{g}}(K_5)=1$, $\tilde{\rm{g}}(K_7)=3$ and $\tilde{\rm{g}}(K_5\cup K_7)=3$: embed $K …
- 6,101
11
votes
Accepted
Is every graph an isomorphic factor of some complete graph?
Q1: yes, this is a theorem by Wilson; see the first paragraph here: https://arxiv.org/abs/1604.07282
Edit: perhaps the book Decomposition of graphs by J. Bosak might be helpful (the preview on google …
- 6,101
3
votes
An upper bound for the number of non-isomorphic graphs having exactly $m$ edges and no isola...
A lower bound $A_m\ge (\Omega(m))!$ can be obtained as follows. Let $n$ be a positive integer and $\pi$ an arbitrary permutation of $\{1,2,\dots,n\}$. Construct a graph $G(\pi)=(V,E(\pi))$ as follows. …
- 6,101
4
votes
Accepted
Genus for specific family of graphs
Since the genus is additive over connected components, it is sufficient to find $g$ vertex-disjoint subdivisions of $K_{3,3}$, one in each copy of $C_{10}\times C_{10}$. This will show that the genus …
- 6,101
3
votes
Accepted
Bookthickness of covering space
The graph of the icosahedron is a 2-fold cover of $K_6$; this covering can be induced by the covering of the projective plane by the sphere. The graph of the icosahedron is planar and Hamiltonian, so …
- 6,101
11
votes
Accepted
Computational (conjecture) choices for a path
Let $S=\Sigma v_i$. If $S=0$, sort the vectors according to their angle along the unit circle. Then the corresponding closed path traces the boundary of a convex polygon.
In fact, the vectors $v_i$ ca …
- 6,101
4
votes
Adjacency matrix of tournament
The following two papers give the lower bound $n-1$ on the rank of $n\times n$ tournament matrices over fields of characteristic zero. Here a tournament matrix $M$ is a $\{0,1\}$-matrix, with zeros on …
- 6,101
4
votes
Is the "surface-minor" ordering of plane graphs a well-quasi-ordering?
This is a partial answer, for the case when the given sequence $G_1,G_2,\dots$ of plane graphs has unbounded treewidth. In such a case, for every $n$ there is an $i$ such that $G_i$ contains the $n\ti …
- 6,101