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

Houmem Belkhechine ; Pierre Ille ; Robert E. Woodrow

Discussiones Mathematicae Graph Theory, Tome 37 (2017), p. 175-209 / Harvested from The Polish Digital Mathematics Library

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 gs of g by s defined as follows: given distinct x, y ∈ V, gs(x, y) = s(x) + g(x, y) − s(y). The switching class of g is gs : 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 ∈ 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

Publié le : 2017-01-01

Zbl 1354.05114

EUDML-ID : urn:eudml:doc:288014