Skip to main content
removed capitals from title
Link
YCor
  • 63.9k
  • 5
  • 187
  • 286

Number of $5^{-}$-neighbors of Highhigh-degree Verticesvertices in Maximal Planar Graphsmaximal planar graphs

added 1 character in body
Source Link
CCC
  • 51
  • 2

We call a vertex with a degree no more than $k$ a $k^{-}$-vertex and a $k^{+}$-vertex if it has a degree at least $k$. By the discharging method, the researchers in graph theory obtained a series of results on the neighboring relationship between vertices with low degrees and high degrees in a planar graph. Please refer to DOI: https://doi.org/10.1016/j.disc.2016.11.022 for more details. I shall list some results for example here:

  1. Every planar graph contains a $5^{-}$-vertex with at most two $12^{+}$-vertices;neighbors;
  2. [Balogh, Kochol, Pluhar, Yu] Every planar graph has a $5^{-}$-vertex with at most two $11^{+}$-neighbors;

Note that $11$ is best possible for this type of neighboring lemma in a planar graph. The graph formed from an icosahedron by adding a new vertex inside each face and making it adjacent to all vertices on the boundary of that fact can serve as an illustration for this claim since each $3$-vertex has three $10$-neighbours. Also note that since adding edges won't give any vertex fewer high neighbors, the proofs of such lemmas are always made on maximal planar graphs.

Here comes my question. I'm trying to obtain an upper bound of the number of low-degree vertices in a maximal planar graph. For this purpose, I tried to get the relationship between the number of high-degree vertices and the number of low-degree vertices. I wonder if there is any result in the form of lemmas I listed above to discuss the number of low-degree neighbors, more specifically $5^{-}$-neighbors, of a high-degree vertex in a maximal planar graph or simply a planar graph?

We call a vertex with a degree no more than $k$ a $k^{-}$-vertex and a $k^{+}$-vertex if it has a degree at least $k$. By the discharging method, the researchers in graph theory obtained a series of results on the neighboring relationship between vertices with low degrees and high degrees in a planar graph. Please refer to DOI: https://doi.org/10.1016/j.disc.2016.11.022 for more details. I shall list some results for example here:

  1. Every planar graph contains a $5^{-}$-vertex with at most two $12^{+}$-vertices;
  2. [Balogh, Kochol, Pluhar, Yu] Every planar graph has a $5^{-}$-vertex with at most two $11^{+}$-neighbors;

Note that $11$ is best possible for this type of neighboring lemma in a planar graph. The graph formed from an icosahedron by adding a new vertex inside each face and making it adjacent to all vertices on the boundary of that fact can serve as an illustration for this claim since each $3$-vertex has three $10$-neighbours. Also note that since adding edges won't give any vertex fewer high neighbors, the proofs of such lemmas are always made on maximal planar graphs.

Here comes my question. I'm trying to obtain an upper bound of the number of low-degree vertices in a maximal planar graph. For this purpose, I tried to get the relationship between the number of high-degree vertices and the number of low-degree vertices. I wonder if there is any result in the form of lemmas I listed above to discuss the number of low-degree neighbors, more specifically $5^{-}$-neighbors, of a high-degree vertex in a maximal planar graph or simply a planar graph?

We call a vertex with a degree no more than $k$ a $k^{-}$-vertex and a $k^{+}$-vertex if it has a degree at least $k$. By the discharging method, the researchers in graph theory obtained a series of results on the neighboring relationship between vertices with low degrees and high degrees in a planar graph. Please refer to DOI: https://doi.org/10.1016/j.disc.2016.11.022 for more details. I shall list some results for example here:

  1. Every planar graph contains a $5^{-}$-vertex with at most two $12^{+}$-neighbors;
  2. [Balogh, Kochol, Pluhar, Yu] Every planar graph has a $5^{-}$-vertex with at most two $11^{+}$-neighbors;

Note that $11$ is best possible for this type of neighboring lemma in a planar graph. The graph formed from an icosahedron by adding a new vertex inside each face and making it adjacent to all vertices on the boundary of that fact can serve as an illustration for this claim since each $3$-vertex has three $10$-neighbours. Also note that since adding edges won't give any vertex fewer high neighbors, the proofs of such lemmas are always made on maximal planar graphs.

Here comes my question. I'm trying to obtain an upper bound of the number of low-degree vertices in a maximal planar graph. For this purpose, I tried to get the relationship between the number of high-degree vertices and the number of low-degree vertices. I wonder if there is any result in the form of lemmas I listed above to discuss the number of low-degree neighbors, more specifically $5^{-}$-neighbors, of a high-degree vertex in a maximal planar graph or simply a planar graph?

Source Link
CCC
  • 51
  • 2

Number of $5^{-}$-neighbors of High-degree Vertices in Maximal Planar Graphs

We call a vertex with a degree no more than $k$ a $k^{-}$-vertex and a $k^{+}$-vertex if it has a degree at least $k$. By the discharging method, the researchers in graph theory obtained a series of results on the neighboring relationship between vertices with low degrees and high degrees in a planar graph. Please refer to DOI: https://doi.org/10.1016/j.disc.2016.11.022 for more details. I shall list some results for example here:

  1. Every planar graph contains a $5^{-}$-vertex with at most two $12^{+}$-vertices;
  2. [Balogh, Kochol, Pluhar, Yu] Every planar graph has a $5^{-}$-vertex with at most two $11^{+}$-neighbors;

Note that $11$ is best possible for this type of neighboring lemma in a planar graph. The graph formed from an icosahedron by adding a new vertex inside each face and making it adjacent to all vertices on the boundary of that fact can serve as an illustration for this claim since each $3$-vertex has three $10$-neighbours. Also note that since adding edges won't give any vertex fewer high neighbors, the proofs of such lemmas are always made on maximal planar graphs.

Here comes my question. I'm trying to obtain an upper bound of the number of low-degree vertices in a maximal planar graph. For this purpose, I tried to get the relationship between the number of high-degree vertices and the number of low-degree vertices. I wonder if there is any result in the form of lemmas I listed above to discuss the number of low-degree neighbors, more specifically $5^{-}$-neighbors, of a high-degree vertex in a maximal planar graph or simply a planar graph?