Sách Factorisation of Snarks

Thảo luận trong 'Sách Ngoại Ngữ' bắt đầu bởi Thúy Viết Bài, 5/12/13.

  1. Thúy Viết Bài

    Thành viên vàng

    Bài viết:
    198,891
    Được thích:
    173
    Điểm thành tích:
    0
    Xu:
    0Xu
    Abstract
    We develop a theory of factorisation of snarks — cubic graphs with edge-chroma-
    tic number 4 — based on the classical concept of the dot product. Our main concern
    are irreducible snarks, those where the removal of every nontrivial edge-cut yields a
    3-edge-colourable graph. We show that if an irreducible snark can be expressed as
    a dot product of two smaller snarks, then both of them are irreducible. This result
    constitutes the first step towards the proof of the following “unique-factorisation”
    theorem:
    Every irreducible snark G can be factorised into a collection {H1, . , Hn} of
    cyclically 5-connected irreducible snarks such that G can be reconstructed from them
    by iterated dot products. Moreover, such a collection is unique up to isomorphism
    and ordering of the factors regardless of the way in which the decomposition was
    performed.
    The result is best possible in the sense that it fails for snarks that are close
    to being irreducible but themselves are not irreducible. Besides this theorem, a
    number of other results are proved. For example, the unique-factorisation theorem
    is extended to the case of factorisation with respect to a preassigned subgraph K
    which is required to stay intact during the whole factorisation process. We show
    that if K has order at least 3, then the theorem holds, but is false when K has
    order 2.
     

    Các file đính kèm: