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

Houmem Belkhechine, Pierre Ille, and Robert E. Woodrow. "Criticality of Switching Classes of Reversible 2-Structures Labeled by an Abelian Group." Discussiones Mathematicae Graph Theory 37.1 (2017): 175-209. <http://eudml.org/doc/288014>.

@article{HoumemBelkhechine2017,
abstract = {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]. },
author = {Houmem Belkhechine, Pierre Ille, Robert E. Woodrow},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {labeled and reversible 2-structure; switching class; clan; primitivity; criticality},
language = {eng},
number = {1},
pages = {175-209},
title = {Criticality of Switching Classes of Reversible 2-Structures Labeled by an Abelian Group},
url = {http://eudml.org/doc/288014},
volume = {37},
year = {2017},
}

TY - JOUR
AU - Houmem Belkhechine
AU - Pierre Ille
AU - Robert E. Woodrow
TI - Criticality of Switching Classes of Reversible 2-Structures Labeled by an Abelian Group
JO - Discussiones Mathematicae Graph Theory
PY - 2017
VL - 37
IS - 1
SP - 175
EP - 209
AB - 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].
LA - eng
KW - labeled and reversible 2-structure; switching class; clan; primitivity; criticality
UR - http://eudml.org/doc/288014
ER -