A Fundamental Theorem on Graph Operators
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910745953828864 |
|---|---|
| author | Gervacio, Severino V. |
| author_facet | Gervacio, Severino V. |
| contents | A graph operator is a function $Γ$ defined on some set of graphs such that whenever two graphs $G$ and $H$ are isomorphic, written $G\simeq H$, then $Γ(G)\simeq Γ(H)$. For a graph $G$ not in the domain of $Γ$, we put $Γ(G)=\emptyset$. Also, let us define $Γ^0(G)=G$, and for any integr $k\ge1$, $Γ^k(G)=Γ(Γ^{k-1}(G))$
We prove that if $Γ$ is a graph operator, then the sequence $\langle Γ^k(G)\rangle_{k=0}^\infty$ has only three possible types of behaviour. Either $Γ^k(G)=\emptyset$ for some integer $k>0$, or $\displaystyle\lim_{k\to\infty}|V(Γ^k(G))|=\infty$, or there exist integers $m\ge0$, $p>0$ such that the graphs $Γ^j(G)$ are non-isomorphic ($0\le j\le m)$, and $Γ^{n+p}\simeq Γ^n(G)$ for all integers $n\ge m$. We illustrate this using two new graph operators, namely, the path graph operator and the claw graph operator. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_11083 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Fundamental Theorem on Graph Operators Gervacio, Severino V. Combinatorics 05C62 A graph operator is a function $Γ$ defined on some set of graphs such that whenever two graphs $G$ and $H$ are isomorphic, written $G\simeq H$, then $Γ(G)\simeq Γ(H)$. For a graph $G$ not in the domain of $Γ$, we put $Γ(G)=\emptyset$. Also, let us define $Γ^0(G)=G$, and for any integr $k\ge1$, $Γ^k(G)=Γ(Γ^{k-1}(G))$ We prove that if $Γ$ is a graph operator, then the sequence $\langle Γ^k(G)\rangle_{k=0}^\infty$ has only three possible types of behaviour. Either $Γ^k(G)=\emptyset$ for some integer $k>0$, or $\displaystyle\lim_{k\to\infty}|V(Γ^k(G))|=\infty$, or there exist integers $m\ge0$, $p>0$ such that the graphs $Γ^j(G)$ are non-isomorphic ($0\le j\le m)$, and $Γ^{n+p}\simeq Γ^n(G)$ for all integers $n\ge m$. We illustrate this using two new graph operators, namely, the path graph operator and the claw graph operator. |
| title | A Fundamental Theorem on Graph Operators |
| topic | Combinatorics 05C62 |
| url | https://arxiv.org/abs/2412.11083 |