Total coloring and efficient domination applications to non-Cayley non-Schreier vertex-transitive graphs
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2020
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908782479540224 |
|---|---|
| author | Dejter, Italo J. |
| author_facet | Dejter, Italo J. |
| contents | Let $0<k\in\mathbb{Z}$. Let the star 2-set transposition graph $ST^2_k$ be the $(2k-1)$-regular graph whose vertices are the $2k$-strings on $k$ symbols, each symbol repeated twice, with its edges given each by the transposition of the initial entry of one such $2k$-string with any entry that contains a different symbol than that of the initial entry. The pancake 2-set transposition graph $PC^2_k$ has the same vertex set of $ST^2_k$ and its edges involving each the maximal product of concentric disjoint transpositions in any prefix of an endvertex string, including the external transposition being that of an edge of $ST^2_k$. For $1<k\in\mathbb{Z}$, we show that $ST^2_k$ and $PC^2_k$, among other intermediate transposition graphs, have total colorings via $2k-1$ colors. They, in turn, yield efficient dominating sets, or E-sets, of the vertex sets of $ST^2_k$ and $PC^2_k$, and partitions into into $2k-1$ such E-sets, generalizing Dejter-Serra work on E-sets in such graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2007_09736 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Total coloring and efficient domination applications to non-Cayley non-Schreier vertex-transitive graphs Dejter, Italo J. Combinatorics 05C15, 05C62, 05C70, 05C75, 05C90, 94B25, 94C15 Let $0<k\in\mathbb{Z}$. Let the star 2-set transposition graph $ST^2_k$ be the $(2k-1)$-regular graph whose vertices are the $2k$-strings on $k$ symbols, each symbol repeated twice, with its edges given each by the transposition of the initial entry of one such $2k$-string with any entry that contains a different symbol than that of the initial entry. The pancake 2-set transposition graph $PC^2_k$ has the same vertex set of $ST^2_k$ and its edges involving each the maximal product of concentric disjoint transpositions in any prefix of an endvertex string, including the external transposition being that of an edge of $ST^2_k$. For $1<k\in\mathbb{Z}$, we show that $ST^2_k$ and $PC^2_k$, among other intermediate transposition graphs, have total colorings via $2k-1$ colors. They, in turn, yield efficient dominating sets, or E-sets, of the vertex sets of $ST^2_k$ and $PC^2_k$, and partitions into into $2k-1$ such E-sets, generalizing Dejter-Serra work on E-sets in such graphs. |
| title | Total coloring and efficient domination applications to non-Cayley non-Schreier vertex-transitive graphs |
| topic | Combinatorics 05C15, 05C62, 05C70, 05C75, 05C90, 94B25, 94C15 |
| url | https://arxiv.org/abs/2007.09736 |