Note on decompositions based on the vertexremoving synchronised graph product

Antoon H. Boode

Robotics Research Group, InHolland University of Applied Science, Alkmaar, the Netherlands

ton.boode@inholland.nl https://orcid.org/0000-0001-5119-6275

Recently, we have introduced two graph-decomposition theorems based on a new graph product, motivated by applications in the context of synchronising periodic real-time processes. This vertexremoving 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 ¨ show how we can relax the requirements of these two graph-decomposition theorems.

Keywords: vertex removing synchronised graph product, product graph, decomposition, synchronising processes Mathematics Subject Classification : 05C76, 05C51, 05C20, 94C15

DOI: 10.5614/ejgta.2022.10.1.9

1. Introduction

Recently, we have introduced two graph-decomposition theorems based on a new graph product [5], motivated by applications in the context of synchronising periodic real-time processes, in particular in the field of robotics. More on the background, definitions, and applications can be found in two conference contributions [4, 6], two journal papers [5, 7], the thesis of the author [3] and the extended version of this note [2]. Here, we relax some of the requirements of the two graph-decomposition theorems presented in [5], for which we present a new lemma (Lemma 3.1) that takes bipartite graphs into account.

Received: 26 July 2021, Revised: 18 December 2021, Accepted: 27 February 2022.

2. Terminology and notation

In order to avoid duplication we refer the interested reader to [5] or [2] for background, definitions and more details. Furthermore, we use the textbook of Bondy and Murty [1] for terminology and notation we have not specified here, or in [5] or in [2]. For convenience, we repeat a few definitions and the theorems from [2] that are especially important for this note.

Let G be an edge-labelled acyclic directed multigraph with a vertex set V , an arc set A, a set of label pairs L and two mappings. The first mapping µ : A Ñ V ˆ V is an incidence function that identifies the tail and head of each arc a P A. In particular, µpaq " pu, vq means that the arc a is directed from u P V to v P V , where tailpaq " u and headpaq " v. We also call u and v the ends of a. The second mapping λ : A Ñ L assigns a label pair λpaq " pℓpaq, tpaqq to each arc a P A, where ℓpaq is a string representing the (name of an) action and tpaq is the weight of the arc a.

If X Ď ApGq, then the subgraph of G arc-induced by X, denoted as GtXu, is the graph on arc set X containing all the vertices of G which are an end of an arc in X (together with L, µ and λ restricted to this subset of the arcs).

A subset A¹ of arcs a P ApGq with λpaq " λ¹ is called the largest subset of arcs with the same label pair λ¹ if there does not exist an arc b P ApGqzA¹ with λpbq " λ² and λ¹ " λ2.

An arc a P ApGiq with label pair λpaq is a synchronising arc with respect to G^j , if and only if there exists an arc b P ApG^j q with label pair λpbq such that λpaq " λpbq. Furthermore, an arc a with label pair λpaq of Gⁱ b G^j or Gⁱ n G^j is a synchronous arc, whenever there exist a pair of arcs aⁱ P ApGiq and a^j P ApG^j q with λpaq " λpaiq " λpa^j q. Analogously, an arc a with label pair λpaq of Gⁱ b G^j or Gⁱ n G^j is an asynchronous arc, whenever λpaq R Lⁱ or λpaq R L^j .

A bipartite graph BpV1, V2q is a clean bipartite graph if all subgraphs BpV 1 1 , V ¹ 2 q of BpV1, V2q are complete, where each subgraph BpV 1 1 , V ¹ 2 q is arc-induced by all arcs in rV1, V2s with the same label pair and, rV1, V2s has no backward arcs or rV1, V2s has no forward arcs.

Informally, the vertex-removing synchronised product (VRSP) starts from the well-known Cartesian product, and is based on a reduction of the number of arcs and vertices due to the presence of synchronising arcs, i.e., arcs with the same label. This reduction is done in two steps: in the first step synchronising pairs of arcs from G¹ and G² are replaced by one (diagonal) arc; in the second step, vertices (and the arcs with that vertex as a tail) are removed one by one if they have level ą 0 in the Cartesian product but level " 0 in what is left of the intermediate product.

Theorem 2.1 ([5]). Let G be a graph, let X be a nonempty proper subset of V pGq, and let Y " V pGqzX. Suppose that all the arcs of rX, Y s have distinct label pairs and that the arcs of G{X and G{Y corresponding to the arcs of rX, Y s are the only synchronising arcs of G{X and G{Y . If S 1 pGq Ď X and rX, Y s has no backward arcs, then G – G{Y n G{X.

Theorem 2.2 ([5]). Let G be a graph, and let X1, X² and Y " V pGqzpX¹ Y X2q be three disjoint nonempty subsets of V pGq. Suppose that all the arcs of rX1, Y s have distinct label pairs, all the arcs of rY, X2s have distinct label pairs, all the arcs of rX1, X2s have distinct label pairs, the arcs of rX1, X2s have no label pairs in common with any arcs in rX1, Y s Y rY, X2s, and that the arcs of G{X1{X² and G{Y corresponding to the arcs of rX1, Y s Y rY, X2s Y rX1, X2s are the only synchronising arcs of G{X1{X² and G{Y . If S 1 pGq Ď X1, and rX1, Y s, rY, X2s and rX1, X2s have no backward arcs, then G – G{Y n G{X1{X2.

3. New results

We like to point out that the proof of the lemma and theorems presented in this note are modelled along the same lines as the proof given in [5]. We start with relaxing the requirement in Theorem 2.1 that states that all arcs of rX, Y s have distinct label pairs in the following manner: each largest set of arcs in rX, Y s with the same label pair arc-induces a complete bipartite subgraph of G. Furthermore, we relax the requirement in Theorem 2.2 that all arcs of rX1, Y s, rY, X2s and rX1, X2s have distinct label pairs in the following manner: firstly, each largest set of arcs in rX1, Y s with the same label pair arc-induces a complete bipartite subgraph of G, secondly, each largest set of arcs in rY, X2s with the same label pair arc-induces a complete bipartite subgraph of G, and, thirdly, the label pairs of the arcs in rX1, X2s do not have to be distinct. Hence, GtrX1, Y su is a clean bipartite subgraph of G and GtrY, X2su is a clean bipartite subgraph of G.

The relaxed requirement of Theorem 2.1 and the first and second relaxed requirement of Theorem 2.2 are based on the decomposition of a complete bipartite graph where all arcs have the same label pair. If BpX, Y q is a clean bipartite graph and rX, Y s does not contain backward arcs then BpX, Y q – BpX, Y q{Y n BpX, Y q{X, which we state and prove in Lemma 3.1. The third relaxed requirement of Theorem 2.2 is based on the observation that the contraction of X¹ and X2, G{X1{X² (shorthand for pG{X1q{X2), replaces the set of arcs rX1, X2s by a set of arcs rtx˜1u, tx˜2us. Hence, let G¹ be the subgraph of G{Y arc-induced by the set of arcs rX1, X2s of G{Y and let G² be the subgraph of G{X1{X² arc-induced by the set of arcs rtx˜1u, tx˜2us of G{X1{X2. Then G¹ – G¹ n G² .

Before we can prove Theorem 3.1 and Theorem 3.2, we state and prove in Lemma 3.1 that a clean bipartite graph BpX, Y q for which rX, Y s has no backward arcs or rX, Y s has no forward arcs, can be decomposed in such a manner that BpX, Y q – BpX, Y q{Y n BpX, Y q{X.

The decomposition given in Lemma 3.1 is restricted to a clean bipartite graph. Note that we allow parallel arcs with different label pairs in BpX, Y q. Furthermore, note that BpX, Y q is not necessarily weakly connected.

Lemma 3.1. Let BpX, Y q be a clean bipartite graph. Then BpX, Y q – BpX, Y q{Y nBpX, Y q{X.

Proof. It suffices to define a mapping ϕ : V pBpX, Y qq Ñ V pBpX, Y q{Y n BpX, Y q{Xq and to prove that ϕ is an isomorphism from BpX, Y q to BpX, Y q{Y n BpX, Y q{X. Let x˜ and y˜ be the new vertices replacing the sets X and Y when defining BpX, Y q{X and BpX, Y q{Y , respectively. Consider the mapping ϕ : V pBpX, Y qq Ñ V pBpX, Y q{Y nBpX, Y q{Xq defined by ϕpuq " pu, x˜q for all u P X, and ϕpvq " py, v ˜ q for all v P Y . Then ϕ is obviously a bijection if V pBpX, Y q{Y n BpX, Y q{Xq " Z, where Z is defined as Z " tpu, x˜q | u P Xu Y tpy, v ˜ q | v P Y u. We are going to show this later by arguing that all the other vertices of BpX, Y q{Y l BpX, Y q{X will disappear from BpX, Y q{Y b BpX, Y q{X. But first we are going to prove the following claim.

Claim 1. The subgraph of BpX, Y q{Y b BpX, Y q{X induced by Z is isomorphic to BpX, Y q.

Proof. Obviously, ϕ is a bijection from V pBpX, Y qq to Z. It remains to show that this bijection preserves the arcs and their label pairs. Let X " tu1, . . . , umu, Y " tv1, . . . , vnu be the disjoint vertex sets of a clean bipartite graph BpX, Y q. Let L " tλ1, . . . , λxu be the set of label pairs belonging to BpX, Y q. Let all arcs of ApBpX, Y qq with label pair λⁱ arc-induce the clean bipartite

subgraph \(B(X_i,Y_i)\). Then, \(X=\bigcup\limits_{i=1}^x X_i\) and \(Y=\bigcup\limits_{i=1}^x Y_i\). Note that \(X_i\cap X_j\) and \(Y_i\cap Y_j, i\neq j\), are not necessarily empty sets and note that \(B(X_i,Y_i)\) is complete. Let [X,Y] have no backward arcs. Hence, \([X_i,Y_i], i=1\dots x\), have no backward arcs. Because, \(X_i\subseteq X\) and \(Y_i\subseteq Y\), and \(\tilde{x}\) and \(\tilde{y}\) are the new vertices replacing the sets X and Y when defining B(X,Y)/X and B(X,Y)/Y, respectively, we have that \(X_i\) and \(Y_i\) (when defining \(B(X_i,Y_i)/X_i\) and \(B(X_i,Y_i)/Y_i\)) are replaced by \(\tilde{x}\) and \(\tilde{y}\), respectively.

Now, we will prove that the subgraph of \(B(X_i,Y_i)/Y_i\boxtimes B(X_i,Y_i)/X_i\) induced by \(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\) is isomorphic to \(B(X_i,Y_i)\). Obviously, the mapping \(\phi\) restricted to \(V(B(X_i,Y_i))\) is a bijection from \(V(B(X_i,Y_i))\) to \(Z_i\). It remains to show that this bijection preserves the arcs and their label pairs. Let \(X_i=\{u_{i_1},\ldots,u_{i_k}\}\subseteq X,Y=\{v_{i_1},\ldots,v_{i_l}\}\subseteq Y\) be the disjoint vertex sets of \(B(X_i,Y_i)\).

\(B(X_i, Y_i)\) is a clean bipartite graph, \(B(X_i, Y_i)\) has the arc set \(A_i = \{a \mid \mu(a) = (u_{i_s}, v_{j_t}), a \in A_i \}\)\([X_i, Y_i]\) for \(1 \le s \le k\) and \(1 \le t \le l\), and \(|A_i| = k \cdot l\). Any two arcs b with \(\mu(b) = (u_{i_s}, \tilde{y})\)in \(B(X_i, Y_i)/Y_i\) and c with \(\mu(c) = (\tilde{x}, v_{jt})\) in \(B(X_i, Y_i)/X_i\) are synchronising arcs, because \(\lambda(b) = \lambda(c)\). Due to the VRSP, the arcs b in \(B(X_i, Y_i)/Y_i\) and c in \(B(X_i, Y_i)/X_i\) correspond to an arc d with \(\mu(d) = ((u_{i_s}, \tilde{x}), (\tilde{y}, v_{j_t})) = (\phi(u_{i_s}), \phi(v_{j_t}))\) in \(B(X_i, Y_i)/Y_i \boxtimes B(X_i, Y_i)/X_i\)with \(\lambda(b) = \lambda(d)\). Because the arc set \(A_i = A(B(X_i, Y_i)/Y_i) = \{b \mid \mu(b) = (u_{is}, \tilde{y})\}\) has cardinality k, the arc set \(A(B(X_i, Y_i)/X_i) = \{c \mid \mu(c) = (\tilde{x}, v_{j_t})\}\) has cardinality l and all arcs of \(A(B(X_i,Y_i)/Y_i)\) and \(A(B(X_i,Y_i)/X_i)\) have identical label pairs, it follows that the arc set \(A_i'=\)\(\{d \mid \mu(d) = ((u_{i_s}, \tilde{x}), (\tilde{y}, v_{j_t})) = (\phi(u_{i_s}), \phi(v_{j_t})), 1 \leqslant s \leqslant k, 1 \leqslant t \leqslant l\} \subseteq A(B(X_i, Y_i)/Y_i \boxtimes I)\)\(B(X_i, Y_i)/X_i\) has cardinality \(k \cdot l\). Furthermore, \(\phi\) restricted to \(V(B(X_i, Y_i))\) maps vertices \(u_{i_s}\) and \(v_{i_t}\) onto vertices \((u_{i_s}, \tilde{x})\) and \((\tilde{y}, v_{i_t})\), respectively, and therefore we have an arc a with \(\mu(a) = (u_{i_s}, v_{j_t})\) in \(B(X_i, Y_i)\) which corresponds to the arc d with \(\mu(d) = ((u_{i_s}, \tilde{x}), (\tilde{y}, v_{j_t}))\) in \(B(X_i, Y_i)/Y_i \boxtimes B(X_i, Y_i)/X_i\), with \(\lambda(a) = \lambda(d)\). Together with \(|A_i| = |A_i'|\), we have the oneto-one relationship between the arc d in \(B(X_i, Y_i)/Y_i \boxtimes B(X_i, Y_i)/X_i\) and the arc d in \(B(X_i, Y_i)\). Therefore, because there are no other vertices in \(Z_i\) than \((u_{i_s}, \tilde{x})\) and \((\tilde{y}, v_{j_t})\) and there are no other vertices in \(B(X_i, Y_i)\) then \((u_{i_s}, v_{j_t})\), the subgraph of \(B(X_i, Y_i)/Y_i \boxtimes B(X_i, Y_i)/X_i\) arc-induced by the arcs of \(B(X_i,Y_i)/Y_i \boxtimes B(X_i,Y_i)/X_i\) with label pair \(\lambda_i\) is isomorphic to \(B(X_i,Y_i)\). This is valid for all \(B(X_i,Y_i)\) because \(\lambda_i \neq \lambda_j, i \neq j, \bigcup_{i=1}^x X_i = X, \bigcup_{i=1}^x Y_i = Y\) and \(\bigcup_{i=1}^x Z_i = Z\). Therefore, we have that the subgraph of \(B(X,Y)/Y \boxtimes B(X,Y)/X\) induced by Z is isomorphic to B(X,Y). This completes the proof of Claim 1.

It remains to show that \(\phi\) is a bijection from V(B(X,Y)) to \(Z' = V(B(X,Y)/Y \boxtimes B(X,Y)/X)\). Now, we have \(Z' \subseteq V(B(X,Y)/Y \boxtimes B(X,Y)/X) = \{(u_i,v_j)\} \cup \{(u_i,\tilde{x})\} \cup \{(\tilde{y},v_j)\} \cup \{(\tilde{y},\tilde{x})\}\). The arcs b with \(\mu(b) = (u_i,\tilde{x})\) in B(X,Y)/Y and c with \(\mu(c) = (\tilde{y},v_j)\) in B(X,Y)/X are synchronising arcs. Therefore, the only vertices that are the tail of an arc in \(B(X,Y)/Y \boxtimes B(X,Y)/X\) are \((u_i,\tilde{x})\) and the only vertices that are the head of an arc in \(B(X,Y)/Y \boxtimes B(X,Y)/X\) are \((\tilde{y},v_j)\). Next, the vertices \(u_i\) in B(X,Y)/Y and the vertex \(\tilde{x}\) in B(X,Y)/X have \(level\ 0\). All other vertices in B(X,Y)/Y and B(X,Y)/X have \(level\ 1\). Therefore, the only vertices in \(B(X,Y)/Y \boxtimes B(X,Y)/X\) with \(level\ 0\) are the vertices \((u_i,\tilde{x})\). It follows that the vertices \((u_i,v_j)\) and \((\tilde{y},\tilde{x})\) are removed from \(V(B(X,Y)/Y \boxtimes B(X,Y)/X)\) because \(level\ ((u_i,v_j)) > 0\) in \(B(X,Y)/Y \boxtimes B(X,Y)/X\) but \(level\ ((u_i,v_j)) = 0\) in \(B(X,Y)/Y \boxtimes B(X,Y)/X\) and \(level\ ((\tilde{y},\tilde{x}))\)

ą 0 in BpX, Y q{Y l BpX, Y q{ X but levelppy˜, x˜qq " 0 in BpX, Y q{Y b BpX, Y q{X. Therefore, it follows that Z ¹ " tpuⁱ , x˜qu Y tpy, v ˜ ^j qu " Z, for 1 ď i ď m and 1 ď j ď n. Hence, ϕ is a bijection from V pBpX, Y qq to Z preserving the arcs and their label pairs and therefore BpX, Y q – BpX, Y q{Y n BpX, Y q{X. With similar arguments, it follows that BpX, Y q – BpX, Y q{Y n BpX, Y q{X if rX, Y s contains no forward arcs. This completes the proof of Lemma 3.1.

In Figure 1, we give a bipartite graph where all arcs have identical label pairs which is not complete. The example shows that one cannot relax the condition on the completeness of the bipartite graph where all arcs have the same label pair without violating the conclusion of Lemma 3.1.

Figure 1. Decomposition of BpX, Y q for which BpX, Y q fl BpX, Y q{Y n BpX, Y q{X. Because all label pairs are identical, we have omitted these label pairs.

Using Lemma 3.1, we relax Theorem 2.1 and Theorem 2.2 leading to Theorem 3.1 and Theorem 3.2, respectively. We assume that the graphs we want to decompose are connected; if not, we can apply our decomposition results to the components separately.

The only difference between Theorem 2.1 and Theorem 3.1 is that the arcs of rX, Y s must have unique label pairs in Theorem 2.1, whereas this is not required in Theorem 3.1. To relax this requirement of Theorem 2.1, we require that the set of arcs rX, Y s arc-induces a clean bipartite graph. By Lemma 3.1, these clean bipartite graphs are decomposable.

Theorem 3.1. Let G be a graph, let X be a nonempty proper subset of V pGq, and let Y " V pGqzX. Suppose that the graph GtrX, Y su is a clean bipartite subgraph of G and that the arcs of G{X and G{Y corresponding to the arcs of rX, Y s are the only synchronising arcs of G{X and G{Y . If S 1 pGq Ď X and rX, Y s has no backward arcs, then G – G{Y n G{X.

Proof. The proof is given in the extended version of this note [2].

Finally, we give Theorem 3.2 which relaxes the requirement of Theorem 2.2 that all the arcs of rX1, Y s have distinct label pairs, all the arcs of rY, X2s have distinct label pairs and all the arcs of rX1, X2s have distinct label pairs. Note that a bipartite subgraph of G arc-induced by all arcs in rX1, X2s with the same label pair does not have to be complete.

Theorem 3.2. Let G be a graph, and let X1, X² and Y " V pGqzpX¹ Y X2q be three disjoint nonempty subsets of V pGq. Suppose that the graph GtrX1, Y su is a clean bipartite subgraph of G, the graph GtrY, X2su is a clean bipartite subgraph of G, the arcs of rX1, X2s have no label pairs in common with any arc in rX1, Y s Y rY, X2s, and the arcs of G{X1{X² and G{Y corresponding to the arcs of rX1, Y s Y rY, X2s Y rX1, X2s are the only synchronising arcs of G{X1{X² and G{Y . If S 1 pGq Ď X1, and rX1, Y s, rY, X2s and rX1, X2s have no backward arcs, then G – G{Y n G{X1{X2.

Proof. The proof is given in the extended version of this note [2].

Acknowledgement

The author would like to express his gratitude to the anonymous reviewers for their very useful suggestions and comments.

References

• [1] J.A. Bondy and U.S.R. Murty, Graph Theory, Springer, Berlin (2008).
• [2] A.H. Boode, A modification of two graph-decomposition theorems based on a vertexremoving synchronised graph product. arXiv: 2103.10808 (2022)
• [3] A.H. Boode, On the Automation of Periodic Hard Real-Time Processes: A Graph-Theoretical Approach, PhD thesis, University of Twente (2018). DOI: 10.3990/1.9789036545518
• [4] A.H. Boode and J.F. Broenink, Performance of periodic real-time processes: a vertexremoving synchronised graph product, In Communicating Process Architectures 2014, Oxford, UK, 36th WoTUG conference on concurrent and parallel programming, pages 119–138, Bicester, August 2014. Open Channel Publishing Ltd.
• [5] A.H. Boode and H.J. Broersma, Decompositions of graphs based on a new graph product. Discrete Appl. Math. 259 (2019) 31–40.
• [6] A.H. Boode, H.J. Broersma, and J.F. Broenink, Improving the performance of periodic realtime processes: a graph theoretical approach, In Communicating Process Architectures 2013, Edinburgh, UK, 35th WoTUG conference on concurrent and parallel programming, pages 57–79, Bicester, August 2013. Open Channel Publishing Ltd.
• [7] A.H. Boode, H.J. Broersma, and J.F. Broenink, On a directed tree problem motivated by a newly introduced graph product, Electron. J. Graph Theory Appl. 3(2) (2015) 162–181.