Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2410.07019 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912065277394944 |
|---|---|
| author | Wang, Runze |
| author_facet | Wang, Runze |
| contents | We introduce the \emph{ID-index} of a finite simple connected graph. For a graph $G=(V,\ E)$ with diameter $d$, we let $f:V\longrightarrow \mathbb{R}$ assign \emph{ranks} to the vertices, then under $f$, each vertex $v$ gets a \emph{string}, which is a $d$-vector with the $i$-th coordinate being the sum of the ranks of the vertices that are of distance $i$ from $v$. The \emph{ID-index} of $G$, denoted by $IDI(G)$, is defined to be the minimum number $k$ for which there is an $f$ with $|f(V)|=k$, such that each vertex gets a distinct string under $f$. We present some relations between ID-graphs, which were defined by Chartrand, Kono, and Zhang, and their ID-indices; give a lower bound on the ID-index of a graph; and determine the ID-indices of paths, grids, cycles, prisms, complete graphs, some complete multipartite graphs, and some caterpillars. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_07019 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Graph identification index Wang, Runze Combinatorics We introduce the \emph{ID-index} of a finite simple connected graph. For a graph $G=(V,\ E)$ with diameter $d$, we let $f:V\longrightarrow \mathbb{R}$ assign \emph{ranks} to the vertices, then under $f$, each vertex $v$ gets a \emph{string}, which is a $d$-vector with the $i$-th coordinate being the sum of the ranks of the vertices that are of distance $i$ from $v$. The \emph{ID-index} of $G$, denoted by $IDI(G)$, is defined to be the minimum number $k$ for which there is an $f$ with $|f(V)|=k$, such that each vertex gets a distinct string under $f$. We present some relations between ID-graphs, which were defined by Chartrand, Kono, and Zhang, and their ID-indices; give a lower bound on the ID-index of a graph; and determine the ID-indices of paths, grids, cycles, prisms, complete graphs, some complete multipartite graphs, and some caterpillars. |
| title | Graph identification index |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2410.07019 |