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

• Autorzy: Houmem Belkhechine , Pierre Ille , Robert E. Woodrow
• Języki publikacji: EN

Abstrakty

EN

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].

Słowa kluczowe

EN

labeled and reversible 2-structure; switching class; clan; primitivity; criticality

Kategorie tematyczne

• 05C75: Structural characterization of families of graphs

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2017
• Tom: 37
• Numer: 1
• Strony: 175-209

Daty

wydano

2017-02-01

otrzymano

2015-09-27

poprawiono

2016-03-29

zaakceptowano

2016-03-29

online

2017-01-13

Twórcy

autor

Houmem Belkhechine

• University of Carthage, Institut Préparatoire aux Études d’Ingénieurs de Bizerte, BP 64, 7021 Bizerte,

autor

Pierre Ille

• Institut de Mathématiques de Marseille, CNRS UMR 7373, 13453 Marseille,

autor

Robert E. Woodrow

• Department of Mathematics and Statistics, University of Calgary, 2500 University Drive, Calgary, Alberta, T2N 1N4

Identyfikatory

DOI

10.7151/dmgt.1943