Decomposition of snarks

There are several methods for constructing snarks (cubic graphs with chromatic index 4). We study the reverse process of splitting a snark into smaller snarks which compose it. We also introduce the notion of a “prime” snark.     

Generation and properties of snarks

For many of the unsolved problems concerning cycles and matchings in graphs it is known that it is sufficient to prove them for snarks, the class of non-trivial 3-regular graphs which cannot be 3-edge coloured.     

Decompositions and reductions of snarks

According to M. Gardner [“Mathematical Games: Snarks, Boojums, and Other Conjectures Related to the Four-Color-Map Theorem,” Scientific American, vol. 234 (1976), pp. 126–130], a snark is a nontrivial cubic graph whose edges cannot be properly colored by three colors. The problem of what “nontrivial” means is implicitly or explicitly present in most papers on snarks, and is the main motivation of the present paper. Our approach to the discussion is based on the following observation. If G is a snark with a k-edge-cut producing components G₁ and G₂, then either one of G₁ and G₂ is not 3-edge-colorable, or by adding a “small” number of vertices to either component one can obtain snarks G₁ and G₂ whose order does not exceed that of G. The two situations lead to a definition of a k-reduction and k-decomposition of G. Snarks that for m < k do not admit m-reductions, m-decompositions, or both are k-irreducible, k-indecomposable, and k-simple, respectively. The irreducibility, indecomposability, and simplicity provide natural measures of nontriviality of snarks closely related to cyclic connectivity. The present paper is devoted to a detailed investigation of these invariants. The results give a complete characterization of irreducible snarks and characterizations of k-simple snarks for k ≤ 6. A number of problems that have arisen in this research conclude the paper. © 1996 John Wiley & Sons, Inc.     

A boojum and other snarks

A snark is an extremally disconnected, rigid space in which every nowhere dense set is closed. We give many snarks, inluding (under CH) a boojum — a hereditarily Lindelöf, hereditarily extremally disconnected, nonseparable snark.     

On embeddings of snarks in the torus

A condition on cubic graphs G₁ and G₂ is presented, which implies that a dot product G₁·G₂ exists, which has an embedding in the torus. Using this condition we prove that for every positive integer n a dot product of n copies of the Petersen graph exists, which can be embedded in the torus. This disproves a conjecture of Watkins and Tinsley and answers a question by Mohar.     

Fuzzy关系的α广义分解

在[0,1]格上讨论了Fuzzy关系α广义可分解问题,证明了[0,1]格上的任一Fuzzy关系R都是α广义可分解的,且给出了R的α广义分解解集.     

The circular chromatic index of Goldberg snarks

We determine the exact values of the circular chromatic index of the Goldberg snarks, and of a related family, the twisted Goldberg snarks.     

The total-chromatic number of some families of snarks

The total-chromatic numberχ_T(G) is the least number of colours needed to colour the vertices and edges of a graph G such that no incident or adjacent elements (vertices or edges) receive the same colour. It is known that the problem of determining the total-chromatic number is NP-hard, and it remains NP-hard even for cubic bipartite graphs. Snarks are simple connected bridgeless cubic graphs that are not 3-edge-colourable. In this paper, we show that the total-chromatic number is 4 for three infinite families of snarks, namely, the Flower Snarks, the Goldberg Snarks, and the Twisted Goldberg Snarks. This result reinforces the conjecture that all snarks have total-chromatic number 4. Moreover, we give recursive procedures to construct a total-colouring that uses 4 colours in each case.     

The \mathcal{VU} -decomposition to the proper convex function

Based on the $\mathcal{VU}$ -theory of the finite-value convex function, this paper gives the $\mathcal{VU}$ -theory of the proper convex function. We give three equivalent definitions of the space decomposition. Also, we get the $\mathcal{U}$ -Lagrangian function and its corresponding properties. Furthermore, we apply this method to the nonlinear programming. And we obtain its algorithm and convergence theorem.     

A C5-decomposition of the λ-fold line graph of the complete graph

In 1996, Cox and Rodger [Cycle systems of the line graph of the complete graph, J. Graph Theory 21 (1996) 173–182] raised the following question: For what values of $m$ and $n$ does there exist an $m$-cycle decomposition of $L\left(K_n\right)?$ In this paper, the above question is answered for $m=5.$ In fact, it is shown that $L\left(K_n\right)\left(\lambda \right),$ the $\lambda$-fold line graph of the complete graph $K_n,$ has a $C_5$-decomposition if and only if $5\mid \lambda \left(\genfrac{}{}{0ex}{}{n}{2}\right)(n?2)$ and $n\ge 4.$     

A survey on snarks and new results: Products,reducibility and a computer search

In this paper we survey recent results and problems of both theoretical and algorithmic character on the construction of snarks—non-trivial cubic graphs of class two, of cyclic edge-connectivity at least 4 and with girth ≥ 5. We next study the process, also considered by Cameron, Chetwynd, Watkins, Isaacs, Nedela, and Sˇkoviera, of splitting a snark into smaller snarks which compose it. This motivates an attempt to classify snarks by recognizing irreducible and prime snarks and proving that all snarks can be constructed from them. As a consequence of these splitting operations, it follows that any snark (other than the Petersen graph) of order ≤ 26 can be built as either a dot product or a square product of two smaller snarks. Using a new computer algorithm we have confirmed the computations of Brinkmann and Steffen on the classification of all snarks of order less than 30. Our results recover the well-known classification of snarks of order not exceeding 22. Finally, we prove that any snark G of order ≤ 26 is almost Hamiltonian, in the sense that G has at least one vertex v for which G \ v is Hamiltonian. © 1998 John Wiley & Sons, Inc. J Graph Theory 28: 57–86, 1998     

Contractible subgraphs, Thomassen’s conjecture and the dominating cycle conjecture for snarks

We show that the conjectures by Matthews and Sumner (every 4-connected claw-free graph is Hamiltonian), by Thomassen (every 4-connected line graph is Hamiltonian) and by Fleischner (every cyclically 4-edge-connected cubic graph has either a 3-edge-coloring or a dominating cycle), which are known to be equivalent, are equivalent to the statement that every snark (i.e. a cyclically 4-edge-connected cubic graph of girth at least five that is not 3-edge-colorable) has a dominating cycle.We use a refinement of the contractibility technique which was introduced by Ryjá?ek and Schelp in 2003 as a common generalization and strengthening of the reduction techniques by Catlin and Veldman and of the closure concept introduced by Ryjá?ek in 1997.