Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

The 1 , 2 , 3-Conjecture And 1 , 2-Conjecture For Sparse Graphs

100%

Cranston D. W., Jahanbekam S., West D. B.

Discussiones Mathematicae Graph Theory

2014

tom 34

nr 4

769-799

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.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Cranston D. W.

1 Jahanbekam S.

1 West D. B.

1 2014

Wyniki wyszukiwania

The 1 , 2 , 3-Conjecture And 1 , 2-Conjecture For Sparse Graphs