Criticality of Switching Classes of Reversible 2-Structures Labeled by an Abelian Group

Belkhechine, Houmem ; Ille, Pierre ; Woodrow, Robert E.

Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 1, pp. 175-209

Résumé

Let V be a finite vertex set and let (𝔸, +) be a finite abelian group. An 𝔸-labeled and reversible 2-structure defined on V is a function g : (V × V) \{ (v, v) : v ∈ V }→𝔸 such that for distinct u, v ∈ V, g(u, v) = −g(v, u). The set of 𝔸-labeled and reversible 2-structures defined on V is denoted by ℒ (V, 𝔸 ). Given g ∈ℒ (V, 𝔸), a subset X of V is a clan of g if for any x, y ∈ X and v ∈ V \ X, g(x, v) = g(y, v). For example, ∅, V and { v } (for v ∈ V) are clans of g, called trivial. An element g of ℒ (V, 𝔸) is primitive if |V| ≥ 3 and all the clans of g are trivial. The set of the functions from V to 𝔸 is denoted by (V, 𝔸 ). Given g ∈ℒ (V, 𝔸 ), with each s ∈ (V, 𝔸) is associated the switch g^s of g by s defined as follows: given distinct x, y ∈ V, g^s(x, y) = s(x) + g(x, y) − s(y). The switching class of g is { g^s : s ∈𝒮 (V, 𝔸 ) }. Given a switching class 𝔊⊆ℒ (V, 𝔸 ) and X ⊆ V, { g_↾ (X × X) \{ (x,x):x ∈ X } : g ∈𝔊} is a switching class, denoted by 𝔊 [X]. Given a switching class 𝔊⊆ℒ (V, 𝔸 ), a subset X of V is a clan of 𝔊 if X is a clan of some g ∈𝔊. For instance, every X ⊆ V such that min (|X|, |V \ X | ) ≤ 1 is a clan of 𝔊, called trivial. A switching class 𝔊⊆ℒ(V, 𝔸 ) is primitive if |V | ≥ 4 and all the clans of 𝔊 are trivial. Given a primitive switching class 𝔊⊆ℒ (V, 𝔸 ), 𝔊 is critical if for each v in V, 𝔊 − v is not primitive. First, we translate the main results on the primitivity of 𝔸-labeled and reversible 2-structures in terms of switching classes. For instance, we prove the following. For a primitive switching class 𝔊⊆ℒ(V, 𝔸) such that |V| ≥ 8, there exist u, v ∈ V such that u v and 𝔊 [V \{ u, v } ] is primitive. Second, we characterize the critical switching classes by using some of the critical digraphs described in [Y. Boudabous and P. Ille, Indecomposability graph and critical vertices of an indecomposable graph, Discrete Math. 309 (2009) 2839–2846].

Détail

Keywords: labeled and reversible 2-structure, switching class, clan, primitivity, criticality