Minimal Graphs with a Specified Code Map Image
Let $G$ be a graph and $e_1,\cdots ,e_n$ be $n$ distinct vertices. Let $\rho$ be the metric on $G$. The code map on vertices, corresponding to this list, is $c(x)=(\rho (x,e_1),\cdots ,\rho (x,e_n))$. This paper introduces a variation: begin with $V\subseteq\bbz^n$ for some $n$, and consider assignm...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Georgia Southern University
2018-08-01
|
| Series: | Theory and Applications of Graphs |
| Subjects: | |
| Online Access: | https://digitalcommons.georgiasouthern.edu/tag/vol5/iss2/4 |
| _version_ | 1819130780534702080 |
|---|---|
| author | Paul Feit |
| author_facet | Paul Feit |
| author_sort | Paul Feit |
| collection | DOAJ |
| description | Let $G$ be a graph and $e_1,\cdots ,e_n$ be $n$ distinct vertices. Let $\rho$ be the metric on $G$. The code map on vertices, corresponding to this list, is $c(x)=(\rho (x,e_1),\cdots ,\rho (x,e_n))$. This paper introduces a variation: begin with $V\subseteq\bbz^n$ for some $n$, and consider assignments of edges $E$ such that the identity function on $V$ is a code map for $G=(V,E)$. Refer to such a set $E$ as a {\em code-match.}
An earlier paper classified subsets of $V$ for which at least one code-match exists. We prove \begin{itemize} \item If there is a code-match $E$ for which $(V,E)$ is bipartite, than $(V,E)$ is bipartite for every code-match $E$. \item If there is a code-match $E$ for which $(V,E)$ is a tree, then $E$ is unique. \item There exists a code-match $E$ such that $(V,E)$ has a $(2^{n-1}+1)$-vertex-coloring. \end{itemize} |
| first_indexed | 2024-12-22T09:05:03Z |
| format | Article |
| id | doaj.art-51328260a6c94cda87a795ffb95e0987 |
| institution | Directory Open Access Journal |
| issn | 2470-9859 |
| language | English |
| last_indexed | 2024-12-22T09:05:03Z |
| publishDate | 2018-08-01 |
| publisher | Georgia Southern University |
| record_format | Article |
| series | Theory and Applications of Graphs |
| spelling | doaj.art-51328260a6c94cda87a795ffb95e09872022-12-21T18:31:36ZengGeorgia Southern UniversityTheory and Applications of Graphs2470-98592018-08-015210.20429/tag.2018.050204Minimal Graphs with a Specified Code Map ImagePaul FeitLet $G$ be a graph and $e_1,\cdots ,e_n$ be $n$ distinct vertices. Let $\rho$ be the metric on $G$. The code map on vertices, corresponding to this list, is $c(x)=(\rho (x,e_1),\cdots ,\rho (x,e_n))$. This paper introduces a variation: begin with $V\subseteq\bbz^n$ for some $n$, and consider assignments of edges $E$ such that the identity function on $V$ is a code map for $G=(V,E)$. Refer to such a set $E$ as a {\em code-match.} An earlier paper classified subsets of $V$ for which at least one code-match exists. We prove \begin{itemize} \item If there is a code-match $E$ for which $(V,E)$ is bipartite, than $(V,E)$ is bipartite for every code-match $E$. \item If there is a code-match $E$ for which $(V,E)$ is a tree, then $E$ is unique. \item There exists a code-match $E$ such that $(V,E)$ has a $(2^{n-1}+1)$-vertex-coloring. \end{itemize}https://digitalcommons.georgiasouthern.edu/tag/vol5/iss2/4Metric Dimension; Distance in Graph; Coloring; Trees |
| spellingShingle | Paul Feit Minimal Graphs with a Specified Code Map Image Theory and Applications of Graphs Metric Dimension; Distance in Graph; Coloring; Trees |
| title | Minimal Graphs with a Specified Code Map Image |
| title_full | Minimal Graphs with a Specified Code Map Image |
| title_fullStr | Minimal Graphs with a Specified Code Map Image |
| title_full_unstemmed | Minimal Graphs with a Specified Code Map Image |
| title_short | Minimal Graphs with a Specified Code Map Image |
| title_sort | minimal graphs with a specified code map image |
| topic | Metric Dimension; Distance in Graph; Coloring; Trees |
| url | https://digitalcommons.georgiasouthern.edu/tag/vol5/iss2/4 |
| work_keys_str_mv | AT paulfeit minimalgraphswithaspecifiedcodemapimage |