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 not deleted
user 384338
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.
6
votes
1
answer
509
views
Does every $4$-connected nonplanar graph contain a $K_5$-minor?
By Kuratowski's theorem, every nonplanar graph contains a (topological) minor of $K_5$ or $K_{3,3}$.
But I observed that every time I construct a $4$-connected nonplanar graph, it always contains not …
- 341
3
votes
0
answers
91
views
If the girth of a $2k$-regular graph $G$ is larger than the diameter of a tree $T$ with $k$ ...
I want to prove that ‘If the girth of a $2k$-regular graph $G$ is larger than the diameter of a $k$-edge tree $T$, then $G$ is covered by edge-disjoint copies of $T$.’
I tried several ways to solve th …
- 341
3
votes
2
answers
305
views
What kind of graph has more edges than its line graph?
The definition of a line graph is as follows:
Given a graph $G$, its line graph $L(G)$ is a graph such that
each vertex of $L(G)$ represents an edge of $G$.
two vertices of $L(G)$ are adjacent if an …
- 341
3
votes
1
answer
668
views
Connectivity and the minimum degree of bipartite graph
I want to find a condition on $\delta(G)$ (ex. $\delta(G) \geq an$) that guarantees $\kappa(G)=\delta(G)$ where $\kappa(G)$ is the vertex-connectivity of a bipartite graph $G$, and $\delta(G)$ is the …
- 341
2
votes
2
answers
527
views
Two independent spanning trees of $2$-connected graph
I want to prove the following statement:
Let $u$ be a vertex in a $2$-connected graph $G$. Then $G$ has two spanning trees such that for every vertex $v$, the $u,v$-paths in the trees are independent …
- 341
2
votes
1
answer
215
views
The lower bound of number of vertices covered by maximum matching in $3$-regular graph
Let $G$ be a $3$-regular graph (cubic graph) with order $n$.
From here, the lower bound of # of vertices covered by maximum matching in $G$ is $\frac{3}{4}n$.
And from here, the lower bound is $\frac{ …
- 341
2
votes
1
answer
383
views
Maximum number of leaf blocks in 3-regular (cubic) graph
The definition of block is
Block of $G$ is a maximal subgraph $G'$ of $G$ with no cut vertex of $G'$ itself.
Of course, there can exist many blocks in $G$.
In particular, isolated vertices, edges in …
- 341
1
vote
Two independent spanning trees of $2$-connected graph
Let's use a new concept oriented path in a cycle $C$ or an open ear $P_k$.
In $C$: Label the vertices in $C$ in clockwise direction by $u,v_1,\cdots,v_n$. Then the clockwise-oriented path of $C$ ($c_ …
- 341
1
vote
1
answer
173
views
$K_{k,m}$ is $k$-choosable if and only if $m<k^k$
This statement is proved by Vizing and Erdos & Rubin (page 30) independently.
But I cannot find Vizing's paper (It's too old) and Erdos & Rubin's paper only says 'It is easily proved'.
I think it is …
- 341
1
vote
1
answer
246
views
If $G$ and $H$ are $k$-critical, then applying Hajós construction to $G$ and $H$ makes $k$-c...
Here is the definition of Hajós construction.
Let $G$ and $H$ be two undirected graphs, $vw$ be an edge of $G$, and $xy$ be an edge of $H$. Then the Hajós construction forms a new graph that combines …
- 341
1
vote
1
answer
76
views
Pseudo-replication of a vertex in a perfect graph
Definition of 'replication of $v$' is
Suppose $v \in V(G)$. Replication of $v$ is constructing $G'$ by adding a new vertex $v'$ such that $N_{G'}(v')=N_G(v) \cup \{v\}$.
And the following statement …
- 341
1
vote
1
answer
380
views
An equitable edge-coloring of bipartite graphs
In this book (I found it from other references, and it was a nice book to study.), there is an exercise that proving the following two statements.
Every graph $G$ with $m$ edges and maximum degree $k …
- 341
1
vote
0
answers
88
views
Proving $R(n_1+1,n_2+1,\cdots,n_k+1) \leq{n_1+n_2+\cdots+n_k \choose n_1,n_2,\cdots,n_k}$
The following statement is a well-known lemma of Ramsey number.
$$R(m+1,n+1) \leq {m+n \choose m}$$
Now, I want to prove the improvement of the above statement:
$$R(n_1+1,n_2+1,\cdots,n_k+1) \leq{n_1+ …
- 341