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.
15
votes
Accepted
Always a planar-drawn cycle through $n$ points
Yes. Let $A$ be a vertex of a convex hull. Draw rays $AP_1,\dots,AP_{n-1}$ to other points, let them go in this order counted counterclockwise. Then $AP_1P_2\dots P_{n-1}A$ is what you need.
- 109k
3
votes
Accepted
Cycle-intersecting subsets
No. And this is not about cycles at all.
Take minimal cycle-intersecting subset. If it has at least two vertices from any cycle, remove any vertex from it and get a smaller cycle-intersecting subset. …
- 109k
2
votes
Accepted
Minimum Edge Density given a particular condition
It is well-known, but I do not know where did it appear for the first time.
The answer is $f(2k)=k^2$ for $n=2k$ and $f(2k+1)=k(k+1)$ for $n=2k+1$. Examples are bipartite graphs $K_{k,k}$ and $K_{k,k …
- 109k
4
votes
Accepted
"Common-neighbor-regular" graphs
I claim that for $k>1$ any such graph is regular, in this case we get a well-known problem (subproblem of describing strongly regular graphs), which does not seem to be solved completely. Case $k=1$ i …
- 109k
3
votes
Accepted
Total chromatic number and total clique number
Counterexamples are, for example, complete graphs with even number $2k$ of vertices. If we manage to color such a graph with $2k$ colors, then all vertices have different colors, and from each vertex …
- 109k
6
votes
Independence Number of Graphs
Surely no. Instead of specific example, let me give general speculations. If this were true, then $\alpha(G)=\alpha(H)$ would imply $\alpha(G\boxtimes G)=\alpha(H\boxtimes H)$, and hence for all stron …
- 109k
3
votes
Accepted
Maximum minimal degree $\delta(G)$ for connected, non-Hamiltonian $G$
No, a graph with $\delta(G)\geqslant (k-1)/2$ has Hamiltonian path by Dirac's theorem. But for $\delta(G)=(k-2)/2$ this is already not always so, see $K_{m,m+2}$.
- 109k
1
vote
How to show that $G$ is of class two ?or how to show $x_1(G)=\Delta(G)+1$?
If order means a number $2k+1$ of vertices, we simply note that each color has at most $k$ edges, so $d=\Delta(H)$ colors have at most $dk$ edges, thus at least $d/2=|E|-dk$ edges must be removed from …
- 109k
1
vote
Accepted
How to prove that doubly regular tournaments are regular?
Let $v$ be any vertex, $U$ be a set of its out-neighbours. The restriction of your tournament to $U$ is $j$-out-regular, thus $|U|=2j+1$.
- 109k
3
votes
Accepted
Lower bound on diameter of trivalent graphs
If diameter equals $d$, the total number $n$ of vertices does not exceed $1+3+3\cdot 2+\dots+3\cdot 2^{d-1}=3\cdot 2^d-2$, this gives you a lower estimate on $d$ which is less or more sharp.
- 109k
1
vote
Example of: K-regular graph with girth K, for a given K
In this paper http://onlinelibrary.wiley.com/doi/10.1002/jgt.3190070210/abstract even more strict theorem is proved. If I remember well, the example you are asking about belongs to Tutte.
- 109k
6
votes
Accepted
Finding the subgraph with the largest diameter
Equivalently, we want to find the longest induced path. According to Wikipedia, it is NP-hard to find it:
It is NP-complete to determine, for a graph G and parameter k, whether the graph has an induc …
- 109k
2
votes
Accepted
On the formal definition of mesh or region for a planar graph
If the graph is already drawn on the plane, the regions are connected components of the set complement of the union of the curves presenting the edges. Sometimes you may define the regions combinatori …
- 109k
4
votes
Accepted
Regularization of arbitrary graphs
Yes. First of all, for any vertex $v\in V$ we draw the edges to $\Delta(G)-\deg(v)$ new vertices so that the degree of $v$ becomes equal to $\Delta(G)$. Now all degrees are equal either to $\Delta(G)$ …
- 109k
4
votes
Accepted
How to prove that the modal number(s) of outgoing edges cannot exceed 2?
The sum of outdegrees is at most $n$. Thus if certain value $d\geqslant 3$ appears, say, $k>0$ times, the value 0 must appear at least $(d-1)k>k$ times, and do $d$ is not modal.
- 109k