All Questions
Tagged with planar-graphs extremal-graph-theory
20
questions
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
2
votes
1
answer
106
views
Proof that the maximum number of edges of a 1-planar graph is 4n - 8
The Wikipedia article about 1-planar graphs says that the maximum number of edges in such graphs is $4n - 8$
Every 1-planar graph with n vertices has at most 4n − 8 edges.[4] More strongly, each 1-...
- 155
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
0
votes
1
answer
48
views
Using Euler formula to prove maximum number of lines in planar graph without triangles
Im trying to prove a planar graph without triangles with $ n \ge 3$ points has at most $2n-4$ edges. I want to solve this using the Euler formula, $n+f=m+2$. I've come to the conclusion that $f\le$ $m/...
- 137
2
votes
1
answer
151
views
Maximum number of vertices with degree three in maximal bipartite planar graphs
A bipartite graph $G$ is a graph where each cycle has an even length. If $G$ can be drawn on the plane without any crossings of edges, $G$ is called planar. $G$ is called maximal planar bipartite if ...
- 2,474
5
votes
1
answer
342
views
Why does a 3-regular planar graph of diameter 3 have at most 12 vertices?
Today, I saw an interesting exercise on page 224 of the West textbook "Introduction to Graph Theory".
6.1.15. Construct a 3-regular planar graph of diameter 3 with 12 vertices. (Comment: T. ...
- 2,474
0
votes
0
answers
18
views
Maximal planar graphs with minimum independent sets
The lower bound is known to follow immediately from the Four Color Theorem.
Theorem 1. If $G$ is a planar graph with order $n$, then $\alpha(G) \geq \frac{n}{4}$.
The lower bound in Theorem 1 is sharp....
- 2,474
0
votes
0
answers
35
views
Question about "growing layers of a planar graphs"
Given a planar graph $G$ k nodes $S$ of $G$ construct "layers" $L_i$ for $i=0,1,...$ as follows $L_0=S$, having constructed layers $L_0,L_1,..,L_i$ layer $L_{i+1}$ consists of those nodes ...
- 468
1
vote
1
answer
171
views
Lower bound on the number of edges in a non-$k$-planar graph.
Just for fun!
This problem is a generalization of the question I came across in the following post:
Proof that a graph with at most n+2 edges is planar
That means that every non-planar graph (non-1-...
- 2,474
3
votes
1
answer
241
views
Why is the number of edges of a $C_5$-free planar graph with $n$ vertices at most $\frac{12n-33}{5}$ where $n\in\{11,12,13\}$?
Let us say that a graph is $C_5$-free if it does not contain any cycle $C_5$ as a subgraph (whether induced or not). We define $ex_{_\mathcal{P}}(n,C_5)$ to be the maximum number of edges possible in ...
- 2,474
0
votes
0
answers
201
views
What is the smallest number of vertices among planar graphs with vertex connectivity $1$ or $2$ of minimum degree $5$?
It is well-known that planar graphs have minimum degree at most 5. Furthermore, we know any planar graph with minimum degree exactly 5 has at least 12 vertices. The icosahedron graph is the unique 12-...
- 2,474
2
votes
1
answer
171
views
Maximum number of edges in a balanced graph with n points, without small cycles (say, of length 2, 3, 4)
Let's say we have $n$ points numbered from $1$ to $n$.
What is the maximum number of directed edges possible on a graph with these $n$ points:
without any cycle of length $\leq k$, for example ...
- 1,561
3
votes
1
answer
255
views
Largest Planar Subgraph of a Bipartite Graph
The maximum planar subgraph problem (i.e given a graph, find its subgraph which is planar and has the maximum number of edges) is NP hard and MaxSNP hard (as per wikipedia) and we do not have a ...
- 133
1
vote
0
answers
163
views
Can the vertices of a planar graph of min degree 3 be covered with edges of average weight ( sum of degrees) at most 14?
Consider a planar graph where every vertex is incident to at least 3 edges,
and assign to each edge a weight equal to the sum of the degrees of its endpoints.
The answer to Every simple planar graph ...
- 468