Genetic theory for cubic graphs (Q2517298): Difference between revisions

Motivated by the fact that certain challenging problems such as the Traveling Salesman Problem may be inherited from simpler graphs in some sense, this book proposes an interesting approach to study cubic graphs. Connected unlabeled cubic graphs are partitioned into two classes called genes (considered as ``ancestors'') and descendants, respectively. The book proves the fundamental result that any descendant can be constructed from a finite set of genes via certain operations (called breeding operations) in such a way that certain properties of the genes may be inherited to the descendant. This set of ancestor genes for the given descendant is considered as a ``complete family of ancestor genes'' for that particular descendant. It is shown that identifying genes that can be used to generate any given descendant is always possible, and inverse operations are available to enable reconstructions. Furthermore, for any given descendant, the corresponding complete family of ancestor genes is unique in some sense. The book consists of three chapters. It starts in Chapter one by providing basic terminologies and notation, preliminaries and motivations, and by introducing the breeding and parthenogenic operations. It is proved that any given descendant may be constructed by starting from a finite set of genes, that each breeding operation is invertible, and that inverse operations exist. Chapter two is devoted to the study of inherited properties of descendants, and Chapter three studies the uniqueness of the ancestors genes for any given descendant. The book has a conjecture that every descendant can only be generated by starting with a unique set of ancestor genes. This conjecture is supported by numerical experiments. Generally, this is a concise treatment of the theory. Its self-contained nature and its thoughtful organization will make it a useful reference for researchers in the field.