On the existence of combinatorial configurations
| Autor: | Bras Amorós, Maria, Stokes, Klara |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2011 |
| Předmět: |
Graph theory
Configuracions i dissenys combinatoris Combinatorial analysis Grafs Teoria de 05 Combinatorics::05B Designs and configurations [Classificació AMS] Matemàtiques i estadística::Matemàtica discreta::Combinatòria [Àrees temàtiques de la UPC] 05 Combinatorics::05C Graph theory [Classificació AMS] Bipartite graphs Combinatorial designs and configurations Anàlisi combinatòria |
| Zdroj: | UPCommons. Portal del coneixement obert de la UPC Universitat Politècnica de Catalunya (UPC) |
| Popis: | A (v, b, r, k) combinatorial configuration can be defined as a connected, (r, k)-biregular bipartite graph with v vertices on one side and b vertices on the other and with no cycle of length 4. Combinatorial configurations have become very important for some cryptographic applications to sensor networks and to peer-to-peer communities. Configurable tuples are those tuples (v, b, r, k) for which a (v, b, r, k) combinatorial configuration exists. It is proved in this work that the set of configurable tuples with fixed r and k has the structure of a numerical semigroup. The semigroup is completely described whenever r = 2 or r = 3. For the remaining cases some bounds are given on the multiplicity and the conductor of the numerical semigroup. This leads to some concluding results on the existence of configurable tuples. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|