Methods of graph decompositions
graph decompositiongraph isomorphisminformation complexityKrausz-type decompositionsself-similarity in graphs
Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph operations (line graphs, products, etc.) (05C76) Graph algorithms (graph-theoretic aspects) (05C85)
A decomposition of a graph is the partition of the graph into parts that satisfy some special conditions. The methods of graph decompositions involve some state-of-the-art decomposition methods in graph theory, which are very useful when considering many fundamental concepts, such as unigraphs, isomorphism, reconstruction conjecture, \(k\)-dimensional graphs, degree sequences, line graphs, and line hypergraphs. This book mainly involves two parts of content. First, the book explores the algebraic theory of graph decomposition, which is based on the idea of defining a binary operation that transforms the set of graphs or objects generated from graphs into an algebraic semigroup. If the operation and the class of graphs are chosen appropriately, then, just like the integers, every graph has a unique factorization (or normal decomposition) into a product of prime factors. This unique factorization property makes this type of decomposition particularly efficient in dealing with problems related to graph isomorphism, and several such examples are described. Second, the book is devoted to Krausz-type decompositions, which are special covering of graphs by cliques directly associated with the representation of graphs as line graphs of hypergraphs. Various algorithmic and structural results related to the existence, properties, and applications of such decompositions are discussed in the book. In particular, it is shown that Krausz-type decompositions are directly related to topological dimension, information complexity, and self-similarity in graphs, thus allowing connections to be established between combinatorics, general topology, information theory, and the study of complex systems. The topics presented are all related to the role of Professor Regina Tyshkevich in their development, and this book is a tribute to her memory. This book will be of interest to researchers, engineers, and experts, who are interested in the fundamental problems and proof techniques in graph theory. Hence, this book is worth reading.
This page was built for publication: Methods of graph decompositions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6535763)
