Temat: 1-2-3 Conjecture - Katalog OPAC zbiorów

Skocz do pozycji: 1.

Tytuł:: The 1,2,3-Conjecture and 1,2-Conjecture for sparse graphs
Autorzy:: Cranston, Daniel W.
Jahanbekam, Sogol
West, Douglas B.
Powiązania:: https://bibliotekanauki.pl/articles/30148718.pdf
Data publikacji:: 2014-11-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: reducible configuration
discharging method
1, 2, 3-Conjecture
1, 2-Conjecture
Opis:: The 1, 2, 3-Conjecture states that the edges of a graph without isolated edges can be labeled from {1, 2, 3} so that the sums of labels at adjacent vertices are distinct. The 1, 2-Conjecture states that if vertices also receive labels and the vertex label is added to the sum of its incident edge labels, then adjacent vertices can be distinguished using only {1, 2}. We show that various configurations cannot occur in minimal counterexamples to these conjectures. Discharging then confirms the conjectures for graphs with maximum average degree less than 8/3. The conjectures are already confirmed for larger families, but the structure theorems and reducibility results are of independent interest.
Źródło:: Discussiones Mathematicae Graph Theory; 2014, 34, 4; 769-799
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 2.

Tytuł:: An Oriented Version of the 1-2-3 Conjecture
Autorzy:: Baudon, Olivier
Bensmail, Julien
Sopena, Éric
Powiązania:: https://bibliotekanauki.pl/articles/31339138.pdf
Data publikacji:: 2015-02-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: oriented graph
neighbour-sum-distinguishing arc-weighting
complexity
1-2-3 Conjecture
Opis:: The well-known 1-2-3 Conjecture addressed by Karoński, Luczak and Thomason asks whether the edges of every undirected graph $G$ with no isolated edge can be assigned weights from {1, 2, 3} so that the sum of incident weights at each vertex yields a proper vertex-colouring of $G$. In this work, we consider a similar problem for oriented graphs. We show that the arcs of every oriented graph $\overrightarrow{G}$ can be assigned weights from {1, 2, 3} so that every two adjacent vertices of $\overrightarrow{G}$ receive distinct sums of outgoing weights. This result is tight in the sense that some oriented graphs do not admit such an assignment using the weights from {1, 2} only. We finally prove that deciding whether two weights are sufficient for a given oriented graph is an $\mathsf{NP}$-complete problem. These results also hold for product or list versions of this problem.
Źródło:: Discussiones Mathematicae Graph Theory; 2015, 35, 1; 141-156
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 3.

Tytuł:: On {a, b}-Edge-Weightings of Bipartite Graphs with Odd a, b
Autorzy:: Bensmail, Julien
Inerney, Fionn Mc
Lyngsie, Kasper Szabo
Powiązania:: https://bibliotekanauki.pl/articles/32361745.pdf
Data publikacji:: 2022-02-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: neighbour-sum-distinguishing edge-weightings
bipartite graphs
odd weights
1-2-3 Conjecture
Opis:: For any S ⊂ ℤ we say that a graph G has the S-property if there exists an S-edge-weighting w : E(G) → S such that for any pair of adjacent vertices u, v we have ∑_e∈E(v) w(e) ≠ ∑_e∈E(u) w(e), where E(v) and E(u) are the sets of edges incident to v and u, respectively. This work focuses on {a, a+2}-edge-weightings where a ∈ ℤ is odd. We show that a 2-connected bipartite graph has the {a, a+2}-property if and only if it is not a so-called odd multi-cactus. In the case of trees, we show that only one case is pathological. That is, we show that all trees have the {a, a+2}-property for odd a ≠ −1, while there is an easy characterization of trees without the {−1, 1}-property.
Źródło:: Discussiones Mathematicae Graph Theory; 2022, 42, 1; 159-185
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Informacja