Английская Википедия:Flower snark

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

In the mathematical field of graph theory, the flower snarks form an infinite family of snarks introduced by Rufus Isaacs in 1975.

As snarks, the flower snarks are connected, bridgeless cubic graphs with chromatic index equal to 4. The flower snarks are non-planar and non-hamiltonian. The flower snarks J₅ and J₇ have book thickness 3 and queue number 2.

Construction

The flower snark J_n can be constructed with the following process :

• Build n copies of the star graph on 4 vertices. Denote the central vertex of each star A_i and the outer vertices B_i, C_i and D_i. This results in a disconnected graph on 4n vertices with 3n edges (A_i – B_i, A_i – C_i and A_i – D_i for 1 ≤ i ≤ n).
• Construct the n-cycle (B₁... B_n). This adds n edges.
• Finally construct the 2n-cycle (C₁... C_nD₁... D_n). This adds 2n edges.

By construction, the Flower snark J_n is a cubic graph with 4n vertices and 6n edges. For it to have the required properties, n should be odd.

Special cases

The name flower snark is sometimes used for J₅, a flower snark with 20 vertices and 30 edges. It is one of 6 snarks on 20 vertices Шаблон:OEIS. The flower snark J₅ is hypohamiltonian.

J₃ is a trivial variation of the Petersen graph formed by replacing one of its vertices by a triangle. This graph is also known as the Tietze's graph. In order to avoid trivial cases, snarks are generally restricted to have girth at least 5. With that restriction, J₃ is not a snark.

Gallery

• The chromatic number of the flower snark J5 is 3.

  The chromatic number of the flower snark J₅ is 3.

• The chromatic index of the flower snark J5 is 4.

  The chromatic index of the flower snark J₅ is 4.

• The original representation of the flower snark J5.

  The original representation of the flower snark J₅.

• The Petersen graph as a graph minor of the flower snark J5

  The Petersen graph as a graph minor of the flower snark J₅