A 5-cycle cluster is a connected subgraph of a cubic graph, where each edge belongs to some 5-cycle. It turns out, that 5-cycle clusters provide a very useful and eficient tool for the structural analysis of cubic graphs, mostly with respect to colourings problems. In this work, we develop necessary theory regarding 5-cycle clusters and describe algorithms for generating 5-cycle clusters and analysing them in cubic graphs. Finally, we present applications of our methods in the structural analysis of all snarks, that is cubic graphs with no 3-edge colouring, up to order 36 and in generation of uniquely 3-edge-colourable cubic graphs.
[
Although the essential property of snarks is the used for structural analysis of cubic graphs, especially absence of their 3-edge-colouring, many authors put snarks and uniquely 3-edge-colourable cubic graphs. stronger requirements on snarks to avoid some “triv- Firstly in Section 2, we describe an algorithm using which ial” cases. Typical nontriviality criteria consist of higher we generated all 5-cycle clusters up to order 20. Then girth, that is the length of a shortest cycle, and cyclic in Section 3 we analyse structural and colouring propedge-connectivity, where a cubic graph is cyclically erties of small 5-cycle clusters with emphasis on those -edge-connected if contains no edge-cut consisting of contained in the Petersen graph. In Section 4 we describe fewer than edges that separates two cycles of . Ac- algorithms for finding and identifying 5-cycle clusters cording to perhaps the most common requirements, we in a given cubic graph. Finally, in Section 5, we present call a snark nontrivial if it is cyclically 4-edge-connected applications of our results. and has girth at least 5. At the end of this section, we clarify some notions we
Beside the absence of a 3-edge-colouring, the number shall use. By a graph we always mean a graph without of all possible 3-edge-colourings for a given cubic graph is loops and parallel edges. The distance between the veralso studied. Cubic graphs that have up to a permutation tices and in a graph , denoted by dist(, ) is the of colours only one 3-edge-colouring, also called uniquely length (that is number of edges) of a shortest --path. 3-edge-colourable, are connected to a potential minimum The distance of two edges and is defined as a minimal counterexample for the cycle double cover conjecture value of dist(, ) where and are some end points of and , respectively.
ITAT’22: Information technologies – Applications and Theory, September 23–27, 2022, Zuberec, Slovakia j$ozemf.arzaajnki@k @dcfsm.fpmhp.uhn.uibnaib.sak.s(kJ.(JR.aMjnaízká);k); 2. Generation of 5-cycle clusters skoviera@dcs.fmph.uniba.sk (M. Škoviera)
© 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Firstly, since we want to analyse 5-cycle clusters in cubic CPWrEooUrckReshdoinpgs IhStpN:/c1e6u1r3-w-0s.o7r3g ACttEribUutRion W4.0oInrtekrnsahtioonpal (PCCroBYce4.0e).dings (CEUR-WS.org) graphs, we need to know all possible 5-cycle clusters up to a certain order and, eventually, also certain girth.
We developed an algorithm to generate all such 5-cycle clusters.
Here, the union of graphs 1 ∪ 2 is the graph with vertex set () = (1) ∪ (2) and edge set () = (1) ∪ (2). If we consider each 5-cycle as a graph, then we can express every 5-cycle cluster as a union of some 5-cycles.
Proposition 1. Let = ⋃︀1≤ ≤ be a 5-cycle cluster with girth consisting of 5-cycles 1, 2, . . . , for some ≥ 2. Then there exists ∈ {1, 2, . . . , } such that ′ = ⋃︀1≤ ≤ , ̸= is a 5-cycle cluster with girth at least and, if ′ ̸= , can be obtained form ′ by (i) adding a --path of length 5 − for some degree 2 vertices and in ′ that are connected by a path of length ∈ {1, 2, 3, 4}; or (ii) adding an edge and a --path of length 2 for some degree 2 vertices , , , and of ′ such that , ∈ (′); or (iii) adding edges and for some degree 2 vertices , , , and of ′ such that ∈ (′), and and are connected by a path of length 2.
Algorithm 1: Algorithm for generating all 5cycle clusters with girth at least up to order input : , output : A set of all pairwise non-isomorphic clusters of 5-cycles up to order with girth at least ← priority queue containing only 5; ← {} ; while is not empty do ← .(); foreach {, } ⊆ 2 do foreach ∈ {1, 2, 3, 4}, there is a --path of length do if = 4 ∧ ∈/ () then
= ∪ {} else ← ∪ {1, 12, . . . , 3− 4− , 4− }; try_adding(); if ∈ {1, 2} then foreach {, } ⊆ 2 − { , } do if = 1 then try_adding(
∪ {, , }); try_adding( ∪ {, , });
Consider the graph on the vertex set () = {1, 2, . . . , }, where the cycles and are connected by an edge if and only if and share an edge in . Since is a 5-cycle cluster, is connected and also, contains a vertex that is not an articulation if = 2 then (for instance, an end of a longest path). Thus the sub- try_adding( ∪ {, }); graph ′ = ⋃︀1≤ ≤ , ̸= is also connected, hence it is a 5-cycle cluster. Clearly, the girth of ′ cannot decrease with respect to . In the end, a straightforward case analysis of the edges of that are not contained Procedure try_adding() in ′ leads to cases (i), (ii) and (iii). if |if| ≤ con∧taignirstnho(is)om≥orpthhicencopy of
Based on Proposition 1, we developed Algorithm 1 that then
generates all 5-cycle clusters starting from the 5-cycle .add();
by recursively adding paths according to cases (i), (ii) .add();
and (iii). We store the generated 5-cycle clusters in a set
together with their canonical representation sparse6
provided by nauty [
Using Algorithm 1 we generated all 91, 827 5-cycle introduced in [
In this section, we describe most commonly used 5-cycle clusters and their colouring properties. For this purpose, it is useful to allow dangling edges, that is edges incident with only one vertex. From now on, we will consider that each vertex of a 5-cycle cluster is incident with three
A multipole consists of a vertex set ( ) and an edge
set ( ). Each edge has two ends which may, or may
not, be incident with a vertex. An edge whose ends are
incident with two distinct vertices is called a link. If only
one end of an edge is incident with a vertex, then the
edge is a dangling edge or semiedge. Other types of edges follows, we present a complete list of all 5-cycle clusters
do not appear in this paper. The set of all semiedges is contained in the Petersen graph which, as we verified,
denoted by ( ). The order | | of a multipole is also coincides with a list of all colour-open 5-cycle
clusthe number of its vertices. Note that we only consider ters up to order 10. This set of 5-cycle clusters is also
cubic multipoles where each vertex is incident with three considered in [
It is often convenient to partition the set ( ) into pairwise disjoint sets 1, 2 . . . , called connectors. Pentagon A multipole with connectors 1, 2, . . . , such that || = for ∈ {1, 2, . . . , } is denoted by The pentagon P is the smallest 5-cycle cluster. It consists (1, 2, . . . , ) and called a (1, 2, . . . , )-pole, of a single cycle of length 5 together with 5 dangling or simply a 1-pole if = 1. edges which in the order corresponding to the 5-cycle
A colouring of a multipole is a mapping which as- form its unique connector (see Figure 1). It can be consigns to each edge a non-zero element from the Klein structed from the Petersen graph by removing any 5group Z2 × Z2 in such a way that for each vertex cycle. The colouring set of the pentagon is ∈ () the three edges incident to have assigned col(P) = {12333, 12223, 11123, 11231, 12311}, pairwise distinct colours (or equivalently, colours with zero sum). For brevity, we denote the elements of Z2 × Z2 so the colour, which appears three times, is always asby 0 = (0, 0), 1 = (0, 1), 2 = (1, 0), and 3 = (1, 1). signed to three dangling edges incident with three conOne can easily observe that for a cubic graph , a map- secutive vertices on the pentagon, respectively. The penping : () → Z2 × Z2 − { 0} is a colouring if and tagon is the only 5-cycle cluster with 5 vertices. It has 5 only if is a nowhere-zero (Z2 × Z2)-flow for any ori- edges and 5 dangling edges. entation of the edges of .
For the purpose of the following definitions, we as- A B sume that the set of semiedges of a multipole is linearly ordered. The type of a colouring of is the lexicographically smallest sequence 1, 2, . . . , that can C C be obtained from (1), (2), . . . , () by permuting colours. The colouring set of a multipole is the set B A containing the colouring types of each colouring of .
A -pole is called colour-open if there exists a 3-edge- Figure 1: Pentagon Figure 2: Double pentagon colourable -pole such that col( ) ∩ col( ) = ∅; otherwise is called colour-closed.
The following well-known result restrict sequences that can occur as colouring types. Double pentagon
[Parity lemma [
For instance, the possible colouring types for a 4-pole are 1111, 1122, 1212, and 1221.
Now, we are prepared to describe the structure and colouring properties of small 5-cycle clusters. For the purpose of the structural analysis of snarks, colour-open 5-cycle clusters are most relevant. Although a colourclosed multipole can also occur in a snark, it is possible col(dP) = {111111, 111122, 112211, 121121, only when is complemented with some multipole that 121211, 121222, 121323, 122133, 122221, already admits no colouring. 122313, 123132, 123231, 123312}.
We focus on those 5-cycle clusters that occur in the smallest snark – the Petersen graph. Note that the Pe- The double pentagon is the unique 5-cycle cluster with 8 tersen graph is a 5-cycle cluster on its own. In what vertices, 9 edges and 6 dangling edges. The dyad D (or Petersen negator) is a 5-cycle cluster consisting of two 5-cycles sharing a path of length 2. It can be constructed by removing a path of length 2 from the Petersen graph. The natural distribution of semiedges into connectors makes it a (2, 2, 1)-pole D(, , ), with 2-connectors and containing the dangling edges formerly incident with and respectively, and the 1-connector containing the only dangling edge formerly incident with (see Figure 3). For each colouring of dyad, the sum of the colours in exactly one of the connectors or is zero. Thus its colouring set is The dyad is the unique 5-cycle cluster with 7 vertices, 8 edges, and 5 semiedges.
R I
O
A B
B A natural distribution of semiedges into connectors turns it into a (2, 3)-pole T(, ), shown in Figure 5, where the connector corresponds to the severed edge and the connector corresponds to the removed vertex. The sum of the colours in both connectors is non-zero for each colouring of T, so
col(T) = = {12333, 12113, 12223, 12131, 12232, 12311, 12322}.
D
E Together with the triad, there are three 5-cycle clusters having 9 vertices, 11 edges and 5 semiedges. One of them has girth 4, the other two have girth 5 (see Figure 9 for the other one). The triad is distinguishable by the fact col(D) = {11123, 11213, 11231, 12311, 12322, 12333}. that it contains two pairs of dangling edges at distance 1.
The heterochromatic is a 5-cycle cluster that arises from the Petersen graph by severing two nonadjacent edges, Isochromatic leaving a natural distribution of its 4 semiedges into 2 The isochromatic I is a 5-cycle cluster consisting of an connectors containing the two dangling edges that arose 8-cycle 12 . . . 8 with two additional edges 15 and by severing the same edge. Two nonadjacent edges in 37. It can be constructed from the Petersen graph the Petersen graph can be at distance 1 or 2. Depending by removing an edge together with its end ver- on this there are two nonisomorphic heterochromatics tices. Isochromatic has two connectors containing the which are called heterochromatic 1 and heterochromatic semiedges formerly incident with and , respectively. 2 according to the distance of the severed edges (see Its colouring set is Figure 6). We denote them H1 and H2, respectively. Each colouring of a heterochromatic assigns diferent colours to the edges from the same connector, so so the edges from the same connector have always the same colour. It is the unique 5-cycle cluster having 8 vertices, 10 edges, 4 semiedges and girth 5. (There are also two other 5-cycle clusters with 8 vertices and 4 semiedges but they have girth 4.)
The triad T is a 5-cycle cluster formed by three 5-cycles 1, 2, and 3 such that 1 and 2 have exactly one edge in common while 3 contains the common edge of 1 and 2 and one additional edge of each 1 and 2. It can be constructed from the Petersen graph by removing one vertex and severing an edge not incident with it. The col(H1) = col(H2) = {1212, 1221}.
There are four 5-cycle clusters with 10 vertices, 13 edges, 4 dangling edges and girth 5, amongst them there are H1 and H2 (see Figure 10 for the remaining two). The distinguishing property of them is that H1 is the only one having a pair of dangling edges at distance 1 and H2 is the only one with distance 2 or 4 between any two dangling edges.
The triple pentagon tP is a 5-cycle cluster consisting of three 5-cycles, each pair having two edges in common. It
A
B can be constructed from the Petersen graph by severing three pairwise non-adjacent edges lying on a 6-cycle in an alternating order, making the triple pentagon a (2, 2, 2)-pole tP(, , ) as depicted in Figure 7. Note that the three severed edges cannot be extended to a perfect matching of the Petersen graph. Due to parity lemma, tP admits no colouring where in each connector, its two semiedges have the same colour. Like the double pentagon, this is not suficient to describe the colouring set of tP which is exactly col(tP) = {111122, 111212, 112121, 112211, 112222, 112233, 121112, 121211, 121222, 121332, 122212, 122313, 122331, 123231}. The only 5-cycle clusters with 10 vertices, 12 edges and 6 dangling edges are the triple pentagon and the tricell. In contrast to the triple pentagon, the tricell has one dangling edge whose distance to each other dangling edge is at least 2.
There are 86 5-cycle clusters of order up to 10. We summarised their numbers divided by order and girth in Table 1. Nine of them are colour-open and contained in the Petersen graph, so there remain 77 colour-closed 5-cycle clusters.
order = 3 = 4 = 5 5
Here, we describe only 5-cycle clusters that are most relevant for our work – that is those with girth 5, because 5-cycle clusters with girth less than 5 can not appear in nontrivial snarks. Also all Petersen 5-cycle clusters have girth 5, so if we analyse snarks that may contain also colour-closed multipoles, we need to distinguish between colour-open (Petersen) and colour-closed 5-cycle clusters. We mentioned these 5-cycle clusters in previous subsection.
Among the 5-cycle clusters with girth 5 of order 9, there is triad which shares the same number of dangling edges with the 5-cycle cluster depicted in Figure 9. The remaining third 5-cycle cluster is the 3-pole obtained from the Petersen graph by removing one vertex. Of order 10, there are eight 5-cycle clusters: two heterochromatics, the triple pentagon, the tricell, the Petersen graph, two 4-poles shown in Figure 10, and the 2-pole obtained from the Petersen graph by severing an edge.
Besides the colouring set of 5-cycle clusters, it is useful to know also number of colourings of the small 5-cycle clusters. The pentagon, double pentagon, dyad and triad all admit only one colouring for each of their possible types (up to permutation of colours). The triple pentagon B A
B
C
A
C
B
A
The tricell tC is a 5-cycle cluster containing three 5cycles 1, 2 and 3, where 1 and 2 share one edge, 2 and 3 share two edges, and 1 and 3 are disjoint. Like the triple pentagon, it arises from the Petersen graph by severing three pairwise non-adjacent edges, however, in this case these edges do not lie on a 6-cycle and can be extended to a perfect matching of the Petersen graph. The 3-cell has a natural representation as a (2, 2, 2)-pole tC(, , ) as shown in Figure 8. Since it was also constructed form the Petersen graph by severing three edges like tP, we get the same restrictions on colourings like for tP. However, there are some diferences in the has two colourings of types 111122, 112211, 112222, and 112233, and one colouring for the remaining types from col(tP). Similarly, the tricell admits two colourings of type 111221 and one for the remaining types from col(tC).
The isochromatic and both the heterochromatics admit two colouring for each of its types. Interestingly, we found no colour-open 5-cycle cluster with 4 dangling edges and an odd number of colourings for some type (note that no colouring for some type is also an even number). We state it in the following proposition which we verified using a computer for all 5-cycle clusters with 4 dangling edges up to order 20 which we generated using Algorithm 1.
Proposition 2. If is a colour-open 5-cycle cluster with 4 dangling edges and at most 20 vertices, then it has an even number of colourings for each colouring type. □
The first step in finding 5-cycle clusters is to find all 5cycles in a given cubic graph . We represent a 5-cycle of as a sequence of 5 vertices. Since the automorphism group of the 5-cycle, which is generated by rotations and reflections, has order 10, each 5-cycle of can be represented using 10 diferent sequences. Thus, assuming that the vertex set of is a subset of integers, we restrict ourselves to finding only sequences (1, 2, 3, 4, 5) in the form, where 1 is minimal and 3 < 4. This representation is unique for every 5-cycle since only one rotation leads to minimal 1 and only one reflection leads to 3 < 4.
For each vertex of , we find the array 1 of neighbours of and the array 2 of the vertices that are at distance 2 from (that is neighbours of the vertices from 1). We put in both 1 and 2 only vertices with numbers higher than . This ensures that each found 5-tuple for a 5-cycle starts with a vertex with the smallest number. Together with the requirement < we can conclude that the found 5-tuple is a canonical representation of a 5-cycle. Thus, Algorithm 2 finds each 5-cycle exactly once. The time complexity of Algorithm 2 is clearly (| ()|).
Algorithm 2: Algorithm for finding all 5-cycles in a cubic graph foreach ∈ () do 1 = ( ∈ (); > ); 2 = ( ∈ (); ∈ 1 ∧ > ); foreach {, } ⊆ 2, < do if ∈ () then
result.add((, (), , , ()));
Now we describe our algorithm for finding all maximal 5-cycle clusters in a given cubic graph.
1. Find all 5-cycles in using Algorithm 2. 2. Determine maximal 5-cycle clusters using unionifnd algorithm. 3. Determine the type of each cluster according to the properties described in Section 3. 4. Determine the connections between clusters and remaining vertices of .
In the third step, we firstly determine the order, number of dangling edges and girth of a cluster (if we do not know that we have a cluster contained in some nontrivial snark, hence with girth 5). If there is more than one suitable 5-cycle cluster, we perform additional checks to distinguish it. For that purpose and also for the purpose of further identification, we compute distances between every pair of dangling edges.
The last step is optional – sometimes it is suficient to know only which clusters are contained in a cubic graph. For each cluster, we identify which of its dangling edges belong to which connector. Then we create a multigraph, were we contract each 5-cycle cluster in to a single vertex and label the edge ends leaving according to their connectors.
We illustrate the last two steps on an example. Assume that we have a 5-cycle cluster with 10 vertices, 4 dangling edges and girth 5. To characterise this cluster, further checks are needed. Say that we find two dangling edges and at distance 1. Now we know that is the heterochromatic 1. In the step 4, we find unique dangling edges ′ and ′ at distance 4 from and , respectively. Then the connectors of are then = {, ′} and = {, ′}.
At the end, we illustrate the output of our algorithm on one snark which we denote 34 of order 34. Its adjacency list together with the output is shown in Figure 11. The output firstly lists for each maximal 5-cycle cluster of 34 denotation and name of , and then for each semiedge of a line consisting of the connector of , the number of the vertex incident with and the identifier of the other end of in 34. Secondly, for each vertex contained in no maximal 5-cycle cluster, the output contains one line listing the identifiers of the neighbours of . The identifier of a vertex (or equivalently edge end) is its number or the denotation of the 5-cycle cluster containing together with the connector the semiedge incident with is in. We see that 34 consists of four 5-cycle clusters: two dyads 0 and 2, two triads 1 and 3, and two vertices 10 and 11 that are contained in no 5-cycle cluster. 0: 18 12 14 1: 20 5 6 2: 16 32 11 3: 8 5 21 4: 32 28 15 5: 1 3 15 6: 1 10 7 7: 16 21 6 8: 19 3 14 9: 19 13 23 10: 18 11 6 11: 2 26 10 12: 0 27 22 13: 9 20 30 14: 0 8 24 15: 17 4 5 16: 2 29 7
Following this output one can easily draw 34
schematically as depicted in Figure 12. This drawing Structural analysis of snarks
does not hold complete information – we would obtained In 2013, Brinkmann et al. [
D0
D2 T3
A
D edges 5-15 and 7-16 with 5-16 and 7-15. However, this representation of 34 still holds enough information to prove, using the properties of dyads and triads from Section 3, that 34 is not 3-edge-colourable. Indeed, suppose to the contrary that 34 is 3-edge-colourable. Then the two colours in the connector of 0 are diferent, since they come from the triad 1. Thus the colours in are the same. Analogously, the two colours in the connector of 2 are the same, but then the vertex 10 is incident with two edges of the same colour – a contradiction.
10 11 10 11 2
22 5 15 3 21
Finally, in this section we describe how we used analysis of 5-cycle clusters in our research. of snarks, at least up to order 36, has girth 5, so they can Uniquely 3-edge-colourable graphs be analysed using 5-cycle clusters.
Using this approach we described all snarks up to or- Interestingly, the only know example of a cyclically
4der 36. We analysed the structure of all critical cyclically edge connected uniquely 3-edge colourable cubic graph
5-edge-connected snarks, where a snark is critical if re- is the generalized Petersen graph (9, 2) on 18 vertices
moval of any two adjacent vertices produces a 3-edge- [
Moreover, we generalised the structure of these small colourable cubic graph, it is useful to construct multipoles snarks to several infinite families, where we use instead of that can be contained in them. We say that a multipole is the 5-cycle clusters larger multipoles with similar colour- possibly uniquely 3-edge-colourable if it has exactly one ing properties. Those multipoles, that are not necessary colouring for at least one of its types. By Proposition 5-cycle clusters, are constructed from other snarks in the 2 we know that every 5-cycle cluster with 4 dangling same way that the corresponding Petersen clusters are edges and at most 20 vertices is not possibly uniquely constructed from the Petersen graph. 3-edge-colourable. Hence it can occur in no uniquely
We illustrate these results on the following exam- 3-edge-colourable cubic graph. sptlreu.cCtoednsaidsefrotllhoewisn:finTitaekfea mthilryeeof5c-puobliecsgrap,hs1 aℱndcon2-, 3-eTdhgues-cwolhoeunraobnlee wmaunlttisptoolecfornosmtraucgtraapphossibbylyruemnioqvuienlgy where is obtained from some snark by removing a some vertices or severing some edges, one has to ensure path of length 2, and each of 1 and 2 is constructed that the resulting multipole contains no 5-cycle cluster from some snark (not necessary distinct) by severing an of order at most 20 and 4 dangling edges. This can be edge and removing a vertex. We then connect , 1 and a useful heuristic in finding such multipoles – when we 2 as depicted in Figure 14. Note that if , 1 and 2 know that a snark contains some not possibly uniquely are all constructed from the Petersen graph, we obtain a 3-edge-colourable multipole , we know that we need dyad and two triads. to remove a vertex from or sever a link of which
We proved that has similar colouring properties narrows down possibilities of possible construction of like the dyad and 1 and 2 have similar colouring prop- multipoles form . erties like the triad, precisely col( ) ⊆ col(D) and col(1), col(2) ⊆ col(T). This implies that all graphs Acknowledgments in ℱ are not 3-edge-colourable. Out of 2110 critical cyclically 5-edge-connected snarks, we found out that 1718 The second author would like to thank his supervisor of them are contained in the class ℱ . Although in most Edita Máčajová for guidance through his PhD study. cases not every one of the 5-poles , 1 and 2 is a 5-cycle cluster, in each of those snarks, at least two of , 1 and 2 are 5-cycle clusters due to the order not References exceeding 36. Thanks to this we were able to identify them using 5-cycle clusters.
For further details and results of our analysis, we refer
the reader to [
N T1
T2