Three new decompositions of graphs based on a vertex-removing synchronised graph product

arXiv2105.10828MaRDI QIDQ6368317FDOQ6368317

Publication date: 22 May 2021

Abstract: Recently, we have introduced and modified two graph-decomposition theorems based on a new graph product, motivated by applications in the context of synchronising periodic real-time processes. This vertex-removing synchronised product (VRSP), is based on modifications of the well-known Cartesian product, and is closely related to the synchronised product due to Wohrle and Thomas. Here, we recall the definition of the VRSP and the two modified graph-decompositions and introduce three new graph-decomposition theorems. The first new theorem decomposes a graph with respect to the semicomplete bipartite subgraphs of the graph. For the second new theorem, we introduce a matrix graph, which is used to decompose a graph in a manner similar to the decomposition of graphs using the Cartesian product. In the third new theorem, we combine these two types of decomposition. Ultimately, the goal of these graph-decomposition theorems is to come to a prime-graph decomposition.

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph operations (line graphs, products, etc.) (05C76) Applications of graph theory to circuits and networks (94C15) Graph designs and isomorphic decomposition (05C51)

This page was built for publication: Three new decompositions of graphs based on a vertex-removing synchronised graph product

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6368317)