Geodesic
Criticality of Switching Classes of Reversible 2-Structures Labeled by an Abelian Group
Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 1, pp. 175-209.

Voir la notice de l'article provenant de la source Library of Science

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].
Keywords: labeled and reversible 2-structure, switching class, clan, primitivity, criticality 
@article{DMGT_2017_37_1_a13,
     author = {Belkhechine, Houmem and Ille, Pierre and Woodrow, Robert E.},
     title = {Criticality of {Switching} {Classes} of {Reversible} {2-Structures} {Labeled} by an {Abelian} {Group}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {175--209},
     publisher = {mathdoc},
     volume = {37},
     number = {1},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2017_37_1_a13/}
}
TY  - JOUR
AU  - Belkhechine, Houmem
AU  - Ille, Pierre
AU  - Woodrow, Robert E.
TI  - Criticality of Switching Classes of Reversible 2-Structures Labeled by an Abelian Group
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2017
SP  - 175
EP  - 209
VL  - 37
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2017_37_1_a13/
LA  - en
ID  - DMGT_2017_37_1_a13
ER  - 
%0 Journal Article
%A Belkhechine, Houmem
%A Ille, Pierre
%A Woodrow, Robert E.
%T Criticality of Switching Classes of Reversible 2-Structures Labeled by an Abelian Group
%J Discussiones Mathematicae. Graph Theory
%D 2017
%P 175-209
%V 37
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2017_37_1_a13/
%G en
%F DMGT_2017_37_1_a13
Belkhechine, Houmem; Ille, Pierre; Woodrow, Robert E. Criticality of Switching Classes of Reversible 2-Structures Labeled by an Abelian Group. Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 1, pp. 175-209. http://geodesic.mathdoc.fr/item/DMGT_2017_37_1_a13/

[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

[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

[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

[4] A. Cournier and P. Ille, Minimal indecomposable graph, Discrete Math. 183 (1998) 61–80. doi:10.1016/S0012-365X(97)00077-0

[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

[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

[7] A. Ehrenfeucht and G. Rozenberg, Primitivity is hereditary for 2 -structures, Theoret. Comput. Sci. 70 (1990) 343–358.

[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

[9] P. Ille, Indecomposable graphs, Discrete Math. 173 (1997) 71–78. doi:10.1016/S0012-365X(96)00097-0

[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

[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

[12] J.J. Seidel, Strongly regular graphs of L 2 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