Intersection Graphs of Maximal Sub-polygons of k-Lizards
Abstract We introduce k-maximal sub-polygon graphs (k-MSP graphs), the intersection graphs of maximal polygons contained in a polygon with sides parallel to a regular 2k-gon. We prove that all complete graphs are k-MSP graphs for all...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Japan
2023
|
| Online Access: | https://hdl.handle.net/1721.1/150974 |
| Summary: | Abstract
We introduce k-maximal sub-polygon graphs (k-MSP graphs), the intersection graphs of maximal polygons contained in a polygon with sides parallel to a regular 2k-gon. We prove that all complete graphs are k-MSP graphs for all
$$k>1$$
k
>
1
; trees are 2-MSP graphs; trees are k-MSP graphs for
$$k>2$$
k
>
2
if and only if they are caterpillars; and n-cycles are not k-MSP graphs for
$$n>3$$
n
>
3
and
$$k>1$$
k
>
1
. We derive bounds for which j-cycles appear as induced subgraphs of k-MSP graphs. As our main result, we construct examples of graphs which are k-MSP graphs and not j-MSP graphs for all
$$k>1$$
k
>
1
,
$$j>1$$
j
>
1
,
$$k \ne j$$
k
≠
j
. |
|---|