Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

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

100%

Belkhechine H., Ille P., Woodrow R. E.

Discussiones Mathematicae Graph Theory

2017

tom 37

nr 1

175-209

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

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Decomposition tree and indecomposable coverings

100%

Breiner A., Deogun J., Ille P.

Discussiones Mathematicae Graph Theory

2011

tom 31

nr 1

37-44

Let G = (V,A) be a directed graph. With any subset X of V is associated the directed subgraph G[X] = (X,A ∩ (X×X)) of G induced by X. A subset X of V is an interval of G provided that for a,b ∈ X and x ∈ V∖X, (a,x) ∈ A if and only if (b,x) ∈ A, and similarly for (x,a) and (x,b). For example ∅, V, and {x}, where x ∈ V, are intervals of G which are the trivial intervals. A directed graph is indecomposable if all its intervals are trivial. Given an integer k > 0, a directed graph G = (V,A) is called an indecomposable k-covering provided that for every subset X of V with |X| ≤ k, there exists a subset Y of V such that X ⊆ Y, G[Y] is indecomposable with |Y| ≥ 3. In this paper, the indecomposable k-covering directed graphs are characterized for any k > 0.

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

2 Ille P.

1 Belkhechine H.

1 Breiner A.

1 Deogun J.

1 Woodrow R. E.

1 2017

1 2011

Wyniki wyszukiwania

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

Decomposition tree and indecomposable coverings