EUVIMEDEUVIMED entdecken
Crossref

Total Weight Choosability of Trees

Gerard Jennhwa Chang, Guan-Huei Duh, Tsai-Lien Wong, Xuding Zhu

SIAM Journal on Discrete Mathematics · 2017-01 · 31 (2) · 669-686

DOI: 10.1137/15m100763x ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Discrete Mathematics, online erschienen am 04.04.2017. Verfasst von Gerard Jennhwa Chang und 3 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 16 Literaturangaben. Gefördert von: NSC, National Natural Science Foundation of China.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

A total-weighting of a graph $G=(V,E)$ is a mapping $f$ which assigns to each element $y\in V\cup E$ a real number $f(y)$ as the weight of $y$. A total-weighting $f$ of $G$ is proper if the coloring $\phi_{f}$ of the vertices of $G$ defined as $\phi_{f}(v)=f(v)+\sum_{e\in E(v)}f(e)$ is a proper coloring of $G$, i.e., $\phi_{f}(v)\ne\phi_{f}(u)$ for any edge $uv$, where $E(v)$ is the set of edges of $G$ incident to $v$. For positive integers $k$ and $k'$, a graph $G$ is called $(k,k')$-total-weight-choosable if whenever each vertex $v$ is given $k$ permissible weights and each edge $e$ is given $k'$ permissible weights, there is a proper total-weighting $f$ of $G$ which uses only permissible weights on each element $y\in V\cup E$. It is known that every tree is (2,2)-total-weight-choosable and every tree other than $K_2$ is (1,3)-total-weight-choosable. However, the problem of determining which trees are (1,2)-total-weight-choosable remained open. This paper solves this problem and characterizes all (1,2)-total-weight-choosable trees. Based on this characterization, we give an algorithm that determines in linear time whether a given tree is (1,2)-total-weight-choosable.

Förderung

  • NSC
  • National Natural Science Foundation of China

Zitieren

APA

Chang, G. J., Duh, G., Wong, T., & Zhu, X. (2017). Total Weight Choosability of Trees. SIAM Journal on Discrete Mathematics, 31(2), 669-686. https://doi.org/10.1137/15m100763x

Vancouver

Chang GJ, Duh G, Wong T, Zhu X. Total Weight Choosability of Trees. SIAM Journal on Discrete Mathematics. 2017;31(2):669-686. doi:10.1137/15m100763x

BibTeX
@article{Chang2017,
  author = {Chang, Gerard Jennhwa and Duh, Guan-Huei and Wong, Tsai-Lien and Zhu, Xuding},
  title = {Total Weight Choosability of Trees},
  journal = {SIAM Journal on Discrete Mathematics},
  year = {2017},
  volume = {31},
  number = {2},
  pages = {669--686},
  doi = {10.1137/15m100763x}
}
Kostenlos starten →