Criticality of switching classes of reversible 2-structures labeled by an abelian group. (English) Zbl 1354.05114
Summary: Let \(V\) be a finite vertex set and let \((\mathbb{A}, +)\) be a finite abelian group. An \(\mathbb{A}\)-labeled and reversible 2-structure defined on \(V\) is a function \(g : (V \times V) \setminus \{(v, v) : v\in V\}\to\mathbb{A}\) such that for distinct \(u, v\in V\), \(g(u, v) = g(v, u)\). The set of \(\mathbb{A}\)-labeled and reversible 2-structures defined on \(V\) is denoted by \(\mathcal{L}(V, \mathbb{A})\). Given \(g\in\mathcal{L} (V,\mathbb{A})\), a subset \(X\) of \(V\) is a clan of \(g\) if for any \(x, y\in X\) and \(v\in V \setminus X\), \(g(x, v) = g(y, v)\). For example, \(\emptyset\), \(V\) and \(\{v\}\) (for \(v\in V\)) are clans of \(g\), called trivial. An element \(g\) of \(\mathcal{L}(V,\mathbb{A})\) is primitive if \(|V|\geq 3\) and all the clans of \(g\) are trivial.
The set of the functions from \(V\) to is denoted by \(\mathcal{S}(V, \mathbb{A})\). Given \(g\in\mathcal{L}(V,\mathbb{A})\), with each \(s\in\mathcal{S}(V,\mathbb{A})\) is associated the switch \(g^{s}\) of \(g\) by \(s\) defined as follows: given distinct \(x, y\in V\), \(g^{s}(x, y) = s(x) + g(x, y)- s(y)\). The switching class of \(g\) is \(\{g^{s} : s\in \mathcal{S}(V, \mathbb{A})\}\). Given a switching class \(\mathfrak{S}(V, \mathbb{A})\) and \(X\subseteq V\), \(\{g_{\upharpoonright (X\times X)\setminus\{(x,x):x\in X\}} : g\in\mathfrak{S}\}\) is a switching class, denoted by \([X]\).
Given a switching class \(\mathfrak{S}\subseteq(V,\mathbb{A})\), a subset \(X\) of \(V\) is a clan of if \(X\) is a clan of some \(g\in\mathfrak{S}\). For instance, every \(X\subseteq V\) such that \(\min(|X|, |V \setminus X|)\leq 1\) is a clan of \(\mathfrak{S}\), called trivial. A switching class \(\mathfrak{S}\subseteq\mathcal{L}(V,\mathbb{A})\) is primitive if \(|V|\geq 4\) and all the clans of are trivial. Given a primitive switching class \(\mathfrak{S}\subseteq\mathcal{L}(V, \mathbb{A})\), \(\mathfrak{S}\) is critical if for each \(v\in V\), \(\mathfrak{S}-v\) is not primitive. First, we translate the main results on the primitivity of \(\mathbb{A}\)-labeled and reversible 2-structures in terms of switching classes. For instance, we prove the following. For a primitive switching class \(\mathfrak{S}\subseteq\mathcal{L}(V, \mathbb{A})\) such that \(|V|\geq 8\), there exist \(u, v\in V\) such that \(u\neq v\) and \(\mathfrak{S}[V \setminus \{u, v\}]\) is primitive. Second, we characterize the critical switching classes by using some of the critical digraphs described in [Y. Boudabbous and P. Ille, Discrete Math. 309, No. 9, 2839–2846 (2009; Zbl 1182.05062)].
The set of the functions from \(V\) to is denoted by \(\mathcal{S}(V, \mathbb{A})\). Given \(g\in\mathcal{L}(V,\mathbb{A})\), with each \(s\in\mathcal{S}(V,\mathbb{A})\) is associated the switch \(g^{s}\) of \(g\) by \(s\) defined as follows: given distinct \(x, y\in V\), \(g^{s}(x, y) = s(x) + g(x, y)- s(y)\). The switching class of \(g\) is \(\{g^{s} : s\in \mathcal{S}(V, \mathbb{A})\}\). Given a switching class \(\mathfrak{S}(V, \mathbb{A})\) and \(X\subseteq V\), \(\{g_{\upharpoonright (X\times X)\setminus\{(x,x):x\in X\}} : g\in\mathfrak{S}\}\) is a switching class, denoted by \([X]\).
Given a switching class \(\mathfrak{S}\subseteq(V,\mathbb{A})\), a subset \(X\) of \(V\) is a clan of if \(X\) is a clan of some \(g\in\mathfrak{S}\). For instance, every \(X\subseteq V\) such that \(\min(|X|, |V \setminus X|)\leq 1\) is a clan of \(\mathfrak{S}\), called trivial. A switching class \(\mathfrak{S}\subseteq\mathcal{L}(V,\mathbb{A})\) is primitive if \(|V|\geq 4\) and all the clans of are trivial. Given a primitive switching class \(\mathfrak{S}\subseteq\mathcal{L}(V, \mathbb{A})\), \(\mathfrak{S}\) is critical if for each \(v\in V\), \(\mathfrak{S}-v\) is not primitive. First, we translate the main results on the primitivity of \(\mathbb{A}\)-labeled and reversible 2-structures in terms of switching classes. For instance, we prove the following. For a primitive switching class \(\mathfrak{S}\subseteq\mathcal{L}(V, \mathbb{A})\) such that \(|V|\geq 8\), there exist \(u, v\in V\) such that \(u\neq v\) and \(\mathfrak{S}[V \setminus \{u, v\}]\) is primitive. Second, we characterize the critical switching classes by using some of the critical digraphs described in [Y. Boudabbous and P. Ille, Discrete Math. 309, No. 9, 2839–2846 (2009; Zbl 1182.05062)].
MSC:
| 05C75 | Structural characterization of families of graphs |
Citations:
Zbl 1182.05062References:
| [1] | P. Bonizzoni, Primitive 2-structures with the (n − 2)-property, Theoret. Comput. Sci. 132 (1994) 151-178. doi:10.1016/0304-3975(94)90231-3; · Zbl 0822.68078 |
| [2] | Y. Boudabous and P. Ille, Indecomposability graph and critical vertices of an indecomposable graph, Discrete Math. 309 (2009) 2839-2846. doi:10.1016/j.disc.2008.07.015; · Zbl 1182.05062 |
| [3] | Y. Cheng and A.L. Wells, Switching classes of directed graphs, J. Combin. Theory Ser. B 40 (1986) 169-186. doi:10.1016/0095-8956(86)90075-4; · Zbl 0565.05034 |
| [4] | A. Cournier and P. Ille, Minimal indecomposable graph, Discrete Math. 183 (1998) 61-80. doi:10.1016/S0012-365X(97)00077-0; · Zbl 0897.05070 |
| [5] | A. Ehrenfeucht, T. Harju and G. Rozenberg, The Theory of 2-Structures, A Framework for Decomposition and Transformation of Graphs (World Scientific, 1999). doi:10.1142/4197; · Zbl 0981.05002 |
| [6] | A. Ehrenfeucht and G. Rozenberg, Theory of 2-structures, Part I: clans, basic subclasses, and morphisms, Theoret. Comput. Sci. 70 (1990) 277-303. doi:10.1016/0304-3975(90)90129-6; · Zbl 0701.05051 |
| [7] | A. Ehrenfeucht and G. Rozenberg, Primitivity is hereditary for 2-structures, Theoret. Comput. Sci. 70 (1990) 343-358.; · Zbl 0701.05053 |
| [8] | P. Ille, Recognition problem in reconstruction for decomposable relations, in: Finite and Infinite Combinatorics in Sets and Logic, B. Sands, N. Sauer and R. Woodrow (Ed(s)), (Kluwer Academic Publishers, 1993) 189-198. doi:10.1007/978-94-011-2080-7_13; · Zbl 0845.04002 |
| [9] | P. Ille, Indecomposable graphs, Discrete Math. 173 (1997) 71-78. doi:10.1016/S0012-365X(96)00097-0; · Zbl 0882.05108 |
| [10] | P. Ille and R. Woodrow, Decomposition tree of a lexicographic product of binary structures, Discrete Math. 311 (2011) 2346-2358. doi:10.1016/j.disc.2011.05.037; · Zbl 1244.05059 |
| [11] | J.H. Schmerl and W.T. Trotter, Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures, Discrete Math. 113 (1993) 191-205. doi:10.1016/0012-365X(93)90516-V; · Zbl 0776.06002 |
| [12] | J.J. Seidel, Strongly regular graphs of L2 type and of triangular type, in: Proc. Kon. Nederl. Akad. Wetensch. Ser. A (Indag. Math. 29, 1967) 188-196. doi:10.1016/S1385-7258(67)50031-8; · Zbl 0161.20802 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
