- Tytuł:
- Criticality of Switching Classes of Reversible 2-Structures Labeled by an Abelian Group
- Autorzy:
-
Belkhechine, Houmem
Ille, Pierre
Woodrow, Robert E. - Powiązania:
- https://bibliotekanauki.pl/articles/31342140.pdf
- Data publikacji:
- 2017-02-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
labeled and reversible 2-structure
switching class
clan
primitivity
criticality - Opis:
- Let $V$ be a finite vertex set and let $(\mathbb{A}, +)$ be a finite abelian group. An $ \mathbb{A} $-labeled and reversible 2-structure defined on $V$ is a function $ g : (V \times V) \backslash \{ (v, v) : v \in V \} \rightarrow \mathbb{A} $ such that for distinct $ u, v \in V, g(u, v) = −g(v, u) $. The set of $ \mathbb{A} $-labeled and reversible 2-structures defined on $V$ is denoted by $ \mathcal{L} (V, \mathbb{A} ) $. Given $g \in \mathcal{L} (V, \mathbb{A}) $, a subset $X$ of $V$ is a clan of $g$ if for any $x, y \in X$ and $ v \in V \backslash X, g(x, v) = g(y, v) $. For example, $ \emptyset $, $V$ and $ \{ v \} $ (for $v \in V $) are clans of $g$, called trivial. An element $g$ of $ \mathcal{L} (V, \mathbb{A}) $ is primitive if $ |V| \ge 3 $ and all the clans of $g$ are trivial. The set of the functions from $V$ to $ \mathbb{A} $ is denoted by $ (V, \mathbb{A} ) $. Given $ g \in \mathcal{L} (V, \mathbb{A} ) $, with each $ s \in (V, \mathbb{A})$ is associated the switch $ g^s $ of $g$ by $s$ defined as follows: given distinct $x, y \in V $, $g^s(x, y) = s(x) + g(x, y) − s(y) $. The switching class of $g$ is $ \{ g^s : s \in \mathcal{S} (V, \mathbb{A} ) \} $. Given a switching class $ \mathfrak{G} \subseteq \mathcal{L} (V, \mathbb{A} ) $ and $ X \subseteq V $, \( \{ g_{ \upharpoonright (X \times X) \backslash \{ (x,x):x \in X \} } : g \in \mathfrak{G} \} \) is a switching class, denoted by $ \mathfrak{G} [X] $. Given a switching class $ \mathfrak{G} \subseteq \mathcal{L} (V, \mathbb{A} ) $, a subset $X$ of $V$ is a clan of $ \mathfrak{G} $ if $X$ is a clan of some $ g \in \mathfrak{G} $. For instance, every $ X \subseteq V $ such that $ min (|X|, |V \backslash X | ) \le 1 $ is a clan of $ \mathfrak{G} $, called trivial. A switching class $ \mathfrak{G} \subseteq \mathcal{L}(V, \mathbb{A} ) $ is primitive if $ |V | \ge 4 $ and all the clans of $ \mathfrak{G} $ are trivial. Given a primitive switching class $ \mathfrak{G} \subseteq \mathcal{L} (V, \mathbb{A} ) $, $ \mathfrak{G} $ is critical if for each $ v in V $, $ \mathfrak{G} − v $ is not primitive. First, we translate the main results on the primitivity of $ \mathbb{A} $-labeled and reversible 2-structures in terms of switching classes. For instance, we prove the following. For a primitive switching class $ \mathfrak{G} \subseteq \mathcal{L}(V, \mathbb{A})$ such that $|V| \ge 8$, there exist $ u, v \in V$ such that $ u \ne v$ and $ \mathfrak{G} [V \backslash \{ 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].
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2017, 37, 1; 175-209
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł