Graph associated to an element by minimal generators

Definition

Let \(S\) be a numerical semigroup minimally generated by \(\{n_1, \ldots, n_e\}\), and let \(n \in S\). It is defined the graph associated to \(n\) in \(S\), denoted by \(G_n = (V_n, E_n)\), as the graph with vertices

\[ V_n = \{n_i ~ | ~ n - n_i \in S\}, \]

and edges,

\[ E_n = \{\{n_i, n_j\} ~ | ~ n - (n_i + n_j) \in S, i \ne j\}. \]

It can be proven that the number of connected components of \(G_n\) is equal to the number of R-classes in \(\mathbf{Z}(s)\), where \(\mathbf{Z}(s)\) denotes the set of factorizations of \(s\) in \(S\).

Examples

\(\circ\) Let \(S = \langle 6, 7, 11, 15 \rangle\) and \(n = 25\). We have \(25 - 6 = 19, 25 - 7 = 18, 25 - 11 = 14, 25 - 15 = 10\), where \(\{19, 18, 14\} \subseteq S\) and \(15 \not \in S\), then \(V_{25} = \{6, 7, 11\}\). Now we compute the edges,

\[ 25 - (6 + 7) = 12 \in S, \hspace{0.4cm} 25 - (6 + 11) = 8 \not \in S, \]

\[ 25 - (7 + 11) = 7 \in S. \]

The graph associated to \(n = 25\) is as follows:

NSGraph 1 6 2 7 2--1 3 11 3--2

Examples with GAP

The following examples are made with the package NumericalSgps in GAP.

\(\diamond\) Let \(S = \langle 14, 27, 31, 33, 77 \rangle\), in GAP:

gap> S := NumericalSemigroup(14, 27, 31, 33, 77);
<Numerical semigroup with 5 generators>

Given a numerical semigroup \(S\) and an element \(n\) of it, the function GraphAssociatedToElementInNumericalSemigroup returns the graph associated to \(n\) in \(S\).

gap> GraphAssociatedToElementInNumericalSemigroup(114,S);
[ [ 14, 27, 31, 33 ],
  [ [ 14, 27 ], [ 14, 31 ], [ 27, 31 ], [ 27, 33 ] ] ]

The graph \(G_{114}\) is as follows.

G 14 14 27 27 14--27 31 31 14--31 27--31 33 33 27--33

\(\diamond\) Let \(S = \langle 22, 23, 41, 50 \rangle\), in GAP:

gap> S := NumericalSemigroup(22, 23, 41, 50);
<Numerical semigroup with 4 generators>

Given a numerical semigroup \(S\) and an element \(n \in S\), the function DotRosalesGraph returns the graph associated to \(n\) in \(S\) by minimal generators.

gap> 150 in S;
true
gap> h := DotRosalesGraph(150, S);;
gap> Print(h);
graph  NSGraph{
1 [label="22"];
2 [label="23"];
3 [label="41"];
4 [label="50"];
2 -- 1;
3 -- 1;
3 -- 2;
}

The obtained graph is as follows.

NSGraph 1 22 2 23 2--1 3 41 3--1 3--2 4 50

References

Delgado, M., P. A. Garcia-Sanchez, and J. Morais. 2024. “NumericalSgps, a Package for Numerical Semigroups, Version 1.4.0.” https://gap-packages.github.io/ numericalsgps.
Rosales, J. C., and P. A. Garcı́a-Sánchez. 2009. Numerical Semigroups. Springer.