Total Weight Choosability of Trees
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.
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}
}
EUVIMED