All Questions
Tagged with planar-graphs combinatorics
127
questions
4
votes
1
answer
62
views
Every binary tree with $n$ leaves has a subtree with $k$ leaves where $\frac{n}{3} \leq k \leq \frac{2n}{3}$.
I want to show the following:
Every binary tree with $n$ leaves has a subtree with $k$ leaves where $\frac{n}{3} \leq k \leq \frac{2n}{3}$.
My approach:
First thing I did was to draw a binary tree and ...
- 609
1
vote
1
answer
31
views
Graph operations that preserve the number of spanning trees
I am not working on graph theory, so my question may be a little bit vague.
Given a graph (directed or undirected), are there any operations (adding/contracting/removing/sliding edges, gluing with ...
- 309
0
votes
0
answers
17
views
maximum number of edges in a planar graph on 11 vertces with no 5 cycle [duplicate]
It can be checked systematically that the result
ex$_P (n,C_5 )$ ≤ $(12n−33)/5$ holds for n ∈ {11, 12, 13} (this turns out to be not as onerous as
it might at first appear!)
How to compute maximum ...
- 11
0
votes
0
answers
21
views
Computing maximum of a ratio defined on the grid graph
Consider an $n \times n$ grid graph $G$. Define the following quantity
\begin{equation}
m(G) = \text{max}\bigg\{\frac{|E|_{H'}}{|V|_{H'}},~ H' \subseteq G, ~~|V|_{H'} > 0 \bigg\},
\end{equation}
...
- 545
-2
votes
1
answer
61
views
How many different undirected, planar, connected graphs are there where every edge is in a 3-cycle? [closed]
I am interested in undirected, planar, connected graphs where every edge is in a 3-cycle. If there are 4 vertices then, up to isomorphism, there are two such graphs.
How many are there for 5 ...
- 437
0
votes
1
answer
42
views
The interior of polygon with n sides and decomposed 7 triangles, 4 squares was found to be a planar representation of a graph with 11 ver. Determine n
The interior of a polygon with n sides and decomposed into 7 triangles and 4 squares was found to be a planar representation of a graph with 11 vertices. Determine n
I tried drawing various figures ...
- 5
0
votes
1
answer
43
views
Find the maximum number of edges in a planar subgraph of G
Kuratowski's theorem states that a graph G is non-planar if and only if G has either $K_5$ or $K_{3,3}$ as a minor.
Clearly this graph contains two $K_5$ minors, so our maximum non planar subgraph ...
- 115
0
votes
0
answers
26
views
Bounds on chromatic number in terms of chromatic numbers of subgraphs.
Suppose we have a graph G of the form $G = G1 \cup G2$, and graphs G1 and G2 are defined by $V(G1) = V(G2)$. How can we describe the dynamics of the chromatic number of G in relation to the chromatic ...
- 115
1
vote
0
answers
132
views
How many trees with $n$ vertices correspond to the vector $(g_1,g_2,g_3,g_4)$, where the $g_i$ are the number of vertices of degree $i$?
Let there be a tree with $n$ vertices. How to count the number of trees corresponding to the set $(g_1,g_2,g_3,g_4)$, where $g_i$ is the number of vertices of degree $i$? For example, with $n=8$ we ...
user1253213
1
vote
1
answer
62
views
Bicolored triangulations of $S^2$ with certain conditions on degrees of vertices
Finite sets $B,W\subset\mathbb N^2$ are given. Suppose $G=(V,E)$ is a triangulation of a two-dimensional sphere so that $V=V_b\sqcup V_w$. We say that $G$ is a $(B,W)$-triangulation if $(\deg_bv,\...
- 235
0
votes
0
answers
29
views
Percentage of acute triangles [duplicate]
There are 100 dots in a surface. A math lover draw all the triangles possible such that the vertices of the triangle will be those dots. X is the maximum percentage of acute triangles in those ...
- 11
2
votes
1
answer
42
views
Inductive proof for statement about product of weights in intro to dimer model
I was reading this review by Kenyon on the dimer model, and there's a lemma at the beginning that I'm struggling to prove.
Here's the set-up. We have a finite 2D square lattice graph, bounded by a ...
- 31
3
votes
0
answers
60
views
Bound number of loopless multigraphs
Let $d_1,\dots,d_n\geq 0$ be integers and let $G_{d_1,\dots,d_n}$ denote the set of loopless multigraphs with this degree sequence. I want to prove the following bound on the number of such ...
- 1,465
3
votes
2
answers
182
views
Is this degree sequence planar?
For the degree sequence [6,6,4,4,4,4,2,2,2,2]. Then this graph has $f = 10$ by euler's formula. Let $T$ be the number of triangles. Then the inequalities $2e = 36 \geq 3T + 4(10 - T)$ shows that $T \...
- 651
1
vote
1
answer
52
views
Find shortest/longest face cycle across all combinatorial embeddings of a planar graph
Does anyone know any related topic about this problem?
Given a planar graph $G$. Let $C_f=\{C:\text{circuit } C \text{ is a face in some planar embedding}\}$. Find $C \in C_f$ with miximum(minimum) ...
- 21