Maximal planar graphs that embed as centers
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913215341920256 |
|---|---|
| author | Preez, Brandon Du |
| author_facet | Preez, Brandon Du |
| contents | A maximal planar graph is a graph which can be embedded in the plane such that every face of the graph is a triangle. The center of a graph is the subgraph induced by the vertices of minimum eccentricity. We introduce the notion of quasi-eccentric vertices, and use this to characterize maximal planar graphs that are the center of some planar graph. We also present some easier to check only necessary / only sufficient conditions for planar and maximal planar graphs to be the center of a planar graph. Finally, we use the aforementioned characterization to prove that all maximal planar graphs of order at most 8 are the center of some planar graph -- and this bound is sharp. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_16831 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Maximal planar graphs that embed as centers Preez, Brandon Du Combinatorics Discrete Mathematics 05C12 (Primary) 05C10 (Secondary) A maximal planar graph is a graph which can be embedded in the plane such that every face of the graph is a triangle. The center of a graph is the subgraph induced by the vertices of minimum eccentricity. We introduce the notion of quasi-eccentric vertices, and use this to characterize maximal planar graphs that are the center of some planar graph. We also present some easier to check only necessary / only sufficient conditions for planar and maximal planar graphs to be the center of a planar graph. Finally, we use the aforementioned characterization to prove that all maximal planar graphs of order at most 8 are the center of some planar graph -- and this bound is sharp. |
| title | Maximal planar graphs that embed as centers |
| topic | Combinatorics Discrete Mathematics 05C12 (Primary) 05C10 (Secondary) |
| url | https://arxiv.org/abs/2401.16831 |