Geodesic
An extremal graph problem on a grid and an isoperimetric problem for polyominoes
Andrew Vince1
1Department of Mathematics University of Florida
The electronic journal of combinatorics, Tome 31 (2024) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

Let $G$ denote the infinite grid graph with vertex set $\{(a,b)\ : \, a,b \in \mathbb{Z}\}$ and edge set $\big \{ \{u,v\} : |u-v|=1 \;\text{or}\; |u-v| = \sqrt{2} \big \}.$ A question in landscape ecology, restated in graph theoretic terms, asks the following. What is the maximum number of edges in an induced subgraph of $G$ of order $n$? It was conjectured by Taliceo and Fleron that the maximum is $4n - \big \lceil \sqrt{28n-12} \, \big \rceil$. We prove the conjecture by formulating and solving a discrete version of the classical isoperimeteric problem.
DOI : 10.37236/12133
Classification : 05B50, 05C35, 05C10, 05C30, 52B60
Mots-clés : dual polyomino, isoperimetric functions

Andrew Vince  1

1 Department of Mathematics University of Florida 
@article{10_37236_12133,
     author = {Andrew Vince},
     title = {An extremal graph problem on a grid and an isoperimetric problem for polyominoes},
     journal = {The electronic journal of combinatorics},
     year = {2024},
     volume = {31},
     number = {2},
     doi = {10.37236/12133},
     zbl = {1536.05131},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/12133/}
}
TY  - JOUR
AU  - Andrew Vince
TI  - An extremal graph problem on a grid and an isoperimetric problem for polyominoes
JO  - The electronic journal of combinatorics
PY  - 2024
VL  - 31
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/12133/
DO  - 10.37236/12133
ID  - 10_37236_12133
ER  - 
%0 Journal Article
%A Andrew Vince
%T An extremal graph problem on a grid and an isoperimetric problem for polyominoes
%J The electronic journal of combinatorics
%D 2024
%V 31
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/12133/
%R 10.37236/12133
%F 10_37236_12133
Andrew Vince. An extremal graph problem on a grid and an isoperimetric problem for polyominoes. The electronic journal of combinatorics, Tome 31 (2024) no. 2. doi: 10.37236/12133

Cité par Sources :