Metraipolis › archive › dc_6da5206fe50b

Proper $\{a,b\}$-edge-weightings of trees — arXiv:2608.08438

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.08438
License (as archived)
CC0-1.0
Archived
2026-10-19T09:08:53.661Z
SHA-256 of the archived text
63a2ca6931909fc029943ede22a77cd25def136afb6030fdef2c57f4cdea8514
Stable URL of this page
https://metraipolis.com/documento/dc_6da5206fe50b

How to cite

Proper $\{a,b\}$-edge-weightings of trees — arXiv:2608.08438 — arXiv (en), https://arxiv.org/abs/2608.08438 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_6da5206fe50b (Metraipolis archive dc_6da5206fe50b, sha256 63a2ca6931909fc029943ede22a77cd25def136afb6030fdef2c57f4cdea8514)
BibTeX
@misc{dc6da5206fe50b,
  title = {Proper $a,b$-edge-weightings of trees — arXiv:2608.08438},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.08438},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_6da5206fe50b; sha256 63a2ca6931909fc029943ede22a77cd25def136afb6030fdef2c57f4cdea8514},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.08438. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Let $a$ and $b$ be distinct real weights. An $\{a,b\}$-edge-weighting of a tree assigns one of these weights to each edge and is proper if adjacent vertices have different sums of incident edge weights. For every such pair, we give an explicit structural characterization of the trees that do not admit a proper $\{a,b\}$-edge-weighting. If $ab(a+b)\neq0$, then $K_2$ is the only tree without such a weighting. If $a+b=0$, then a tree has no proper $\{a,b\}$-edge-weighting exactly when every vertex has degree $1$ or $3$ and the subgraph induced by the degree-$3$ vertices has a perfect matching. For the remaining case $ab=0$, form the spanning forest consisting of the edges whose deletion leaves two odd-order components. A tree $T$ has no proper $\{a,b\}$-edge-weighting exactly when both bipartition classes have odd order and every component of this forest satisfies two conditions. First, every component satisfies the preceding degree-and-matching condition. Second, within each component, the degree of a vertex $v$ in the forest plus twice the number of incident edges $e$ outside the forest for which the component of $T-e$ not containing $v$ has an odd number of vertices from each bipartition class is independent of $v$. For every fixed pair of distinct real weights, the proofs yield a linear-time algorithm that decides whether a proper $\{a,b\}$-edge-weighting exists and constructs one when it does.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-11 in math.CO).
Categorie arXiv: Combinatorics (math.CO) ; Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2608.08438 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-19T09:05:33.558Z dalla pagina https://arxiv.org/catchup/math.CO/2026-08-11?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).