Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2402.14953 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914689633484800 |
|---|---|
| author | Bailey, Sean Brown, David Snyder, Michael Turner, Nicole |
| author_facet | Bailey, Sean Brown, David Snyder, Michael Turner, Nicole |
| contents | A dot-product representation of a graph is a mapping of its vertices to vectors of length $k$ so that vertices are adjacent if and only if the inner product (a.k.a. dot product) of their corresponding vertices exceeds some threshold. Minimizing dimension of the vector space into which the vectors must be mapped is a typical focus. We investigate this and structural characterizations of graphs whose dot product representations are mappings into the tropical semi-rings of min-plus and max-plus. We also observe that the minimum dimension required to represent a graph using a \emph{tropical representation} is equal to the better-known threshold dimension of the graph; that is, the minimum number of subgraphs that are threshold graphs whose union is the graph being represented. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_14953 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Dot Product Representations of Graphs Using Tropical Arithmetic Bailey, Sean Brown, David Snyder, Michael Turner, Nicole Combinatorics A dot-product representation of a graph is a mapping of its vertices to vectors of length $k$ so that vertices are adjacent if and only if the inner product (a.k.a. dot product) of their corresponding vertices exceeds some threshold. Minimizing dimension of the vector space into which the vectors must be mapped is a typical focus. We investigate this and structural characterizations of graphs whose dot product representations are mappings into the tropical semi-rings of min-plus and max-plus. We also observe that the minimum dimension required to represent a graph using a \emph{tropical representation} is equal to the better-known threshold dimension of the graph; that is, the minimum number of subgraphs that are threshold graphs whose union is the graph being represented. |
| title | Dot Product Representations of Graphs Using Tropical Arithmetic |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2402.14953 |