Szczegóły publikacji

Opis bibliograficzny

Autor

• AGHPrzybyło Jakub

Słowa kluczowe

Dane bibliometryczne

ID BaDAP	119694
Data dodania do BaDAP	2019-03-25
Tekst źródłowy	URL
DOI	10.1016/j.disc.2018.10.033
Rok publikacji	2019
Typ publikacji	artykuł w czasopiśmie
Otwarty dostęp
Czasopismo/seria	Discrete Mathematics

Abstract

Let G = (V, E) be any graph without isolated edges. The well known 1-2-3 Conjecture asserts that the edges of C can be weighted with 1, 2, 3 so that adjacent vertices have distinct weighted degrees, i.e. the sums of their incident weights. It was independently conjectured that if G additionally has no isolated triangles, then it can be edge decomposed into two subgraphs G(1), G(2) which fulfil the 1-2-3 Conjecture with just weights 1,2, i.e. such that there exist weightings omega(i) : E(G(i)) -> {1, 2} so that for every uv is an element of E, if uv is an element of E(G(i)) then d(omega i)(u) not equal d(omega i)(v), where d(omega i)(v) denotes the sum of weights incident with v is an element of V in G(i) for i = 1, 2. We apply the probabilistic method to prove that the known weakening of this so-called Standard (2,2)-Conjecture holds for graphs with minimum degree large enough. Namely, we prove that if delta(G) >= 3660, then G can be decomposed into graphs G(1), G(2) for which weightings omega(i): E(G(i)) -> {1, 2} exist so that for every uv is an element of E, d(omega i)(u) not equal d(omega 1)(v) or d(omega 2)(u) not equal d(omega 2)(v). In fact we prove a stronger result, as one of the weightings is redundant, i.e. uses just weight 1. (C) 2018 Elsevier B.V. All rights reserved.

Publikacje, które mogą Cię zainteresować