HPC. Generalizing 2-generated Cayley Digraphs: Arc-forcing digraphs.

Disclaimer. So far I have not seeing  published anything related with the two generalizations we are talking about in this post. But it is possible that some publication about them exists, unknown to me. Until I am sure about this, I am not claiming originality and I might be repeating what other researchers have already discovered. Of course I would highly appreciate if someone is aware about some publication that defines these kind of generalizations and informs me about it. I am neither claiming yet that these generalizations are interesting; by now only studying the matter. My apologies if some ortographic errors are found in the text.    

1. Introduction

The name of the title refers to one of the two non vertex transitive generalizations of Cayley Digraphs that we have been considering in late posts.

Note.

Of course there are other generalizations that leads to vertex transitive digraphs: the most  obvious one is the one you can get adding to a 2-generated Cayley Digraph additional generators. With this one you remain in the Cayley Digraphs region.

Other  lead to Non-Cayley Vertex Transitive digraphs. We researched some time ago about the possibility that the patent´s techniques extends to these Non-cayley Vertex- Transitive digraphs and the situation is unclear. Now I see that the problem we faced is that some of them falls under some of the generalizations we are studying in this post.  I have to re-read in detail this post which summarized our research. I am thinking that it is likely that the generalizations we are studying could provide a method to construct Non Cayley Vertex Transitive Digraphs.

End of Note.

One of the (desirable) properties of all Cayley Digraphs is the fact that they can be decomposed in arc-forcing subdigraphs.

Note. In 2-generated Cayley Digraphs, arc-forcing subdigraph is a different construction from the arc-forcing subgroup. The former contains the latter but they are not equal. The definition of arc-forcing subgroup does not make sense for the kind of generalizations  we are defining. End of note.

In general abelian will have what we have (with the exception of  those that fulfills some quite restricted arithmetic conditions) called Irregular IAS and non abelian (and those abelian exceptions) have Regular IAS as defined in patent description.

IAS regularity associated to the non abelian property is one of the several great discoveries that we have included in our patent. Of course, the arc-forcing technique had been applied before, but so far no one had paid attention to the fact that in non commutative cases, the ard-forcing could be used to decompose the digraph in regular IASes of same order and that this fact was highly relevant for the hamiltonian property.

If one wants to keep the regular IAS property but lift the IAS same order restriction one is lead to one generalization of 2-generate Cayley Digraphs, that we have called in a previous post, IAS-regular digraphs. These digraphs are 2-regular (2-in, 2-out) but not vertex-transitive anymore. For each number of vertices, the will be found more frequently than 2-generated Cayley Digraphs, but still they are, probably, not very abundant neither. Two examples of this kind in bellow image. That the first is an IAS-regular digraph is very apparent (I would say it is smooth). The second seems more chaotic, but can still be decomposed in IAS-regular subdigraphs (of  different orders; I would say this one is twisted or  entangled).

Generalización

generalización iases regulares

If one drops the two restrictions (regularity and order) but still keeps the fact that the digraph can be decomposed in arc-forcing subdigraphs, then one gets another natural generalization, what we have called Arc-Forcing  Digraphs. It is clear that since we are only lifting the regularity restriction but not forcing it that this second generalization includes the first. They are still 2-regular (2-in, 2-out) and as it is apparent more abundant. But how frequent are they, within the set of all non isomorphic connected 2-regular digraphs ? This is one of the questions we would like to answer, but are unable as for yet.

Other questions are how far the properties we have identified and the techniques developed for solving the hamiltonian traversal problem in 2-generated Cayley Digraphs can be applied for this kind of digraphs.

For instance we have shown in a previous post how we think the technique for obtaining the set of possible ending vertices can be applied for arc-forcing digraphs (AFD from now on). Regarding the properties I am thinking, for instance, about how can we define the entanglement property (it should be reminded that entanglement and the more general property of twistedness are quite relevant for the hamiltonian traversal problem) and it these properties still constitute a kind of frontier regarding hardness.

2. The minimum arc-forcing subdigraphs.

generalis

In a previous post we have already published this image. As can be seen, in the first half we show three examples of what I have called minimal arc-forcing subdigraphs.

I think that starting with some minimal digraphs of this kind and with several operations, we can construct all other possible AFD. But that there is a base of minimal digraphs and a finite set of operations such that from them we can get all AFD digraphs is still unclear.

Note. Now since digraphs can be represented by matrices, if there is such base and such operations, it is not impossible that if we can use some of the tools of matrix theory to answer some questions about these kind of digraphs. I am thinking for instance in a translation of the operations to the language of matrices. Just a thought.

End of note.

Before writing this post, I thought that al these kind of digraphs could be classified as versions of the classes A, B or C in the drawing. But now I am facing some difficulties to reduce a case to one of those. I show it bellow.

new minimal case

We can define an unit a as a pair of arcs that outs from the same vertex (you can define as well the other way: a pair of arcs that ins in to the same vertex). Then one operation could be just to delete an unit. and join the two vertices that remains 1-in after this deletion. The original case is on the left of the image. Deleting 3 units I can transform it into case D, which has 8 vertices. It can be seeing easily that this case D is not isomorphic to case C in above drawing. So I am tempted to create a new class which would  include those similar to case D but with more units. On additional reason why I think we must accept it as a real minimal case is that a formula I discovered the other day, about which I commented in a previous post (in spanish). We need an additional definition to understand the formula. We say that a vertex is saturated if it has already 2-in / 2-out arcs. So the formula says: in a minimal case, number of units + number of saturated vertices +1 = number of vertices. It should be noted that the formula does not work in general.

As with the whole “theory” we are developing I do not know if this formula will remain after all. Do we have already all minimal cases from which with some finite set of operations we can construct all other cases ? Who knows.

As for now I think that the concept of minimal, the minimal cases we got and the operation of deleting a unit, and the decision to keep the saturated vertices untouched under any operation, all of them seems robust so far. For instance if you try to apply the operation to a minimal then you get something which is not anymore a complete arc-forcing digraph. Also one or several units can be removed from de same part in several alternative ways. But the result should always be the same  no matter how you you remove them. When this not  happens then the unit deletion operation can not be effected. An instance is minimal D, the part with vertices 3,4,5 and 8.

The only problem I have with this operation so far is that it would be convenient that it has some practical consequences, such as the one we stated the other day: that the hamiltonian property remains invariant under it. But I have constructed a case based on the one that I draw and can be reduced to D such that you can prove that the original can not be hamiltonian but the reduced (after having tried two different reductions) is. I have not tried all possible reductions yet, but in case one works, how do you choose it ? Who knows. The case bellow. I have found it while trying to construct an entangled case, being succesful.

irregular entangled

Since we deleted three units from the black component, the same amount should be deleted from the red component. Finally I found that one of the reductions (not exhaustive yet, there might be more) is not hamiltonian, but I wouldn´t say it is the one I would had chosen had I not known that it was the non hamiltonian one.

More details about the concepts we are using:

Arc-forcing. We define it as the secuence of arcs that starting from a vertex and ending in this same vertex shows the arc-forcing property. One question that arises is if given a digraph, its decomposition in arc-forcing units is  unique. At present I have not any idea about what could be  the answer to this question. Not even in the restricted class of digraphs we are constructing. I would say that the unique decomposition might be the case for this restricted class, but not sure yet. Re arc-forcing, I am dealing with a new problem: ¿ should we accept loops in an arc-forcing digraph ? After little tought I would say that this issue is not really problematic: you can transform any arc-forcing digraph of odd degree in a similar digraph of even degree. But, I have to sutdy it more. Also an additional generator increases the degree of Cayley Digraphs one unit. In this post we are concentrating in 2-regular arc-forcing digraphs. Does it make sense to allow them to have higher degrees ?

Unit delete operation: it is clear that the unit delete operation includes also a join operation. In all it is a cut, delete and join operation. The two parts that stays incomplete after the cut and delete phases must be joined. In general the degree of a vertex can not be affected by an operation. If the cut and delete desaturates a vertex the join phase must saturate it. On the other hand you can not create a new saturated vertex during the operation. The same for an 1-in/1-out vertex. The arc-forcing property must not be affected neither after the operation.

Note. All this theory that we are trying to  construct has a flavour of knot theory (Reidemesiter moves and so on).  Probably just a flavour. On the other hand, considering that arc-forcing digraphs seems to be quite structured, I am interested in finding an algebraic (or a structure of any kind) wich allow us to construct / label them in a natural way, as groups of permutations allows us to construct / label Cayley digraphs.

monoid

380px-Magma_to_group2.svg

End of note.

Terms and conditions: 1. Any commenter of this blog agrees to transfer the copy right of his comments to the blogger. 2. RSS readers and / or aggregators that captures the content of this blog (posts or comments) are forbidden. These actions will be subject to the DMCA notice-and-takedown rules and will be legally pursued by the proprietor of the blog.

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s


A %d blogueros les gusta esto: