2025-11-23T03:37:16.288381

Moving through Cartesian products, coronas and joins in general position

Klavžar, Krishnakumar, Kuziak et al.
The general position problem asks for large sets of vertices such that no three vertices of the set lie on a common shortest path. Recently a dynamic version of this problem was defined, called the \emph{mobile general position problem}, in which a collection of robots must visit all the vertices of the graph whilst remaining in general position. In this paper we investigate this problem in the context of Cartesian products, corona products and joins, giving upper and lower bounds for general graphs and exact values for families including grids, cylinders, Hamming graphs and prisms of trees.
academic

Bewegung durch kartesische Produkte, Coronas und Verbindungen in allgemeiner Position

Grundinformationen

  • Papier-ID: 2505.00535
  • Titel: Moving through Cartesian products, coronas and joins in general position
  • Autoren: Sandi Klavžar, Aditi Krishnakumar, Dorota Kuziak, Ethan Shallcross, James Tuite, Ismael G. Yero
  • Klassifizierung: math.CO (Kombinatorik)
  • Veröffentlichungsdatum: 16. Oktober 2025 (arXiv-Version)
  • Papierlink: https://arxiv.org/abs/2505.00535

Zusammenfassung

Das Problem der allgemeinen Position erfordert die Suche nach großen Vertex-Mengen, bei denen keine drei Vertices auf demselben kürzesten Weg liegen. Kürzlich wurde eine dynamische Version dieses Problems definiert, die als Bewegungs-Allgemeine-Position-Problem bezeichnet wird, bei dem eine Gruppe von Robotern alle Vertices eines Graphen besuchen muss, während sie die allgemeine Position bewahrt. Dieses Papier untersucht dieses Problem im Kontext kartesischer Produkte, Coronas und Verbindungen und gibt allgemeine Grenzen sowie exakte Werte für Graphenfamilien einschließlich Gitter, Zylinder, Hamming-Graphen und Baumprisma an.

Forschungshintergrund und Motivation

Problemursprung

  1. Statisches Allgemeine-Position-Problem: Stammt aus Dudeneys geometrischem Rätsel und erfordert die Suche nach der größten Vertex-Menge in einem Graphen, bei der keine drei Vertices auf demselben kürzesten Weg liegen
  2. Roboter-Kommunikationsanwendung: Angenommen, Roboter senden Signale über kürzeste Wege zur Kommunikation. Um Störungen zu vermeiden, muss sichergestellt werden, dass kein Roboter auf dem kürzesten Weg zwischen zwei anderen Robotern liegt
  3. Dynamische Anforderungen: In der realen Welt ist die Roboternavigation dynamisch und erfordert Bewegung im Netzwerk, was die Forscher dazu veranlasst, die bewegliche Version des Allgemeine-Position-Problems zu untersuchen

Forschungsbedeutung

  1. Theoretischer Wert: Erweitert die Forschung zum Allgemeine-Position-Problem in der traditionellen Graphentheorie vom Statischen zum Dynamischen
  2. Praktische Anwendung: Bietet theoretische Grundlagen für Pfadplanung und Koordination mobiler Roboter
  3. Graphenstrukturanalyse: Vertieft das Verständnis von Graphenstrukturen durch Untersuchung der Bewegungs-Allgemeine-Position-Zahlen unter verschiedenen Graphenproduktoperationen

Kernbeiträge

  1. Etablierung eines grundlegenden theoretischen Rahmens: Bietet systematische Ober- und Untergrenzen für die Bewegungs-Allgemeine-Position-Zahlen kartesischer Produkte, Coronas und Verbindungsgraphen
  2. Berechnung exakter Werte: Liefert exakte Formeln für die Bewegungs-Allgemeine-Position-Zahlen mehrerer wichtiger Graphenfamilien, einschließlich:
    • Kartesisches Produkt vollständiger Graphen: Mobgp(Kn□Km)\text{Mobgp}(K_n \square K_m)
    • Gittergraphen: Mobgp(Pn□Pm)=3\text{Mobgp}(P_n \square P_m) = 3 (wenn n,m≥3n,m \geq 3)
    • Baumprisma: Mobgp(T□K2)=ℓ(T)\text{Mobgp}(T \square K_2) = \ell(T) (Blattanzahl)
    • Teilweise Ergebnisse für Zylinder- und Torusgraphen
  3. Analyse der Straffheit der Grenzen: Beweist die Straffheit der vorgeschlagenen Grenzen und gibt spezifische Graphenfamilien an, die die Grenzen erreichen
  4. Algorithmische Konstruktion: Konstruiert konkrete Bewegungs-Allgemeine-Position-Mengen und Bewegungssequenzen für mehrere Graphenfamilien

Methodische Details

Aufgabendefinition

Allgemeine-Position-Menge: Eine Vertex-Teilmenge SS eines Graphen GG wird als Allgemeine-Position-Menge bezeichnet, wenn keine drei Vertices in SS auf demselben kürzesten Weg von GG liegen.

Bewegungs-Allgemeine-Position-Menge: Wenn es von einer Allgemeine-Position-Menge SS ausgehend eine Reihe legaler Bewegungen gibt, so dass jeder Vertex des Graphen mindestens einmal von einem Roboter besucht wird, wird SS als Bewegungs-Allgemeine-Position-Menge bezeichnet.

Legale Bewegung: Eine Bewegung u⇝vu \rightsquigarrow v eines Roboters von Vertex uu zu benachbartem Vertex vv ist legal, wenn und nur wenn:

  1. vv derzeit keinen Roboter enthält
  2. Die neue Konfiguration nach der Bewegung immer noch eine Allgemeine-Position-Menge ist

Bewegungs-Allgemeine-Position-Zahl: Mobgp(G)\text{Mobgp}(G) bezeichnet die Größe der größten Bewegungs-Allgemeine-Position-Menge des Graphen GG.

Zentrale technische Methoden

1. Grenzanalyse für kartesische Produkte

Für das kartesische Produkt G□HG \square H etabliert das Papier zwei wichtige Untergrenzen:

Proposition 2.1:

  • Mobgp(G□H)≥max⁡{Mobgp(G),Mobgp(H)}\text{Mobgp}(G \square H) \geq \max\{\text{Mobgp}(G), \text{Mobgp}(H)\}
  • Mobgp(G□H)≥max⁡{gpo(G),gpo(H)}\text{Mobgp}(G \square H) \geq \max\{\text{gp}^o(G), \text{gp}^o(H)\}

wobei gpo(G)\text{gp}^o(G) die äußere Allgemeine-Position-Zahl ist.

2. Schicht-Analysetechnik

Nutzt die Schichtstruktur des kartesischen Produkts (GG-Schichten und HH-Schichten) zur Analyse:

  • GG-Schichten: Der von V(G)×{h}V(G) \times \{h\} induzierte Teilgraph, bezeichnet als GhG^h
  • HH-Schichten: Der von {g}×V(H)\{g\} \times V(H) induzierte Teilgraph, bezeichnet als gH{}^gH

3. Nutzung von Konvexität

Schlüsselbeobachtung: Schichten in kartesischen Produkten sind konvexe Teilgraphen, was bedeutet, dass kürzeste Wege innerhalb einer Schicht diese nicht verlassen.

4. Konstruktive Beweismethode

Für Untergrenzenbeweise verwendet das Papier konstruktive Methoden:

  1. Platzierung von Robotern in spezifischen Schichten
  2. Entwurf konkreter Bewegungssequenzen
  3. Verifikation der Legalität jedes Bewegungsschritts
  4. Beweis, dass alle Vertices besucht werden können

Technische Innovationen

  1. Zwischenschicht-Bewegungsstrategie: Entwicklung von Techniken zur sicheren Bewegung von Robotern zwischen verschiedenen Schichten unter Beibehaltung der Allgemeine-Position-Eigenschaft
  2. Symmetrienutzung: Geschickte Nutzung der Graphensymmetrie zur Vereinfachung des Bewegungssequenzdesigns
  3. Kombinatorisch-geometrische Einsichten: Verbindung des Bewegungs-Allgemeine-Position-Problems mit Positionsproblemen in der kombinatorischen Geometrie
  4. Rekursive Konstruktion: Etablierung rekursiver Konstruktionsmethoden für bestimmte Graphenfamilien

Experimentelle Einrichtung

Theoretische Verifikationsmethoden

Als reines mathematisches Papier verwendet dieses strenge mathematische Beweise statt experimenteller Verifikation:

  1. Konstruktive Beweise: Beweis von Untergrenzen durch explizite Konstruktion von Bewegungs-Allgemeine-Position-Mengen
  2. Beweis durch Widerspruch: Beweis von Obergrenzen durch Annahme einer größeren Menge und Ableitung eines Widerspruchs
  3. Mathematische Induktion: Verwendung mathematischer Induktion für parametrisierte Graphenfamilien
  4. Computergestützte Verifikation: Für komplexe Fälle (wie Torusgraphen) wird computergestützte Suche zur Verifikation der Ergebnisse verwendet

Analysierte Graphenfamilien

  1. Kartesische Produkte vollständiger Graphen: Kr□KsK_r \square K_s
  2. Kartesische Produkte von Wegen: Pn□PmP_n \square P_m (Gittergraphen)
  3. Baumprisma: T□K2T \square K_2
  4. Zylindergraphen: Cr□PsC_r \square P_s
  5. Torusgraphen: Cr□CsC_r \square C_s
  6. Corona: G⊙HG \odot H
  7. Verbindung: G∨HG \vee H

Experimentelle Ergebnisse

Haupttheoretische Ergebnisse

1. Exakte Werte für kartesische Produkte vollständiger Graphen

Theorem 2.4: Für n≥m≥1n \geq m \geq 1:

n & \text{wenn } m \in \{1,2\} \\ n + m - 3 & \text{wenn } m \geq 3 \end{cases}$$ #### 2. Ergebnisse für Gittergraphen **Theorem 3.2**: Für $n,m \geq 3$ gilt $\text{Mobgp}(P_n \square P_m) = 3$ **Theorem 3.3**: Für unendliche Gitter gilt $\text{Mobgp}(P_\infty \square P_\infty) = 4$ #### 3. Baumprisma **Theorem 3.1**: Für jeden Baum $T$ mit mindestens 3 Vertices gilt $\text{Mobgp}(T \square K_2) = \ell(T)$ wobei $\ell(T)$ die Anzahl der Blätter des Baums $T$ bezeichnet. #### 4. Teilweise Ergebnisse für Zylindergraphen **Theorem 3.4**: Für $n \geq 3$: $$\text{Mobgp}(C_n \square K_2) = \begin{cases} 3 & \text{wenn } n = 3 \\ 2 & \text{wenn } n = 4 \\ 4 & \text{sonst} \end{cases}$$ #### 5. Grenzen für Corona **Theorem 4.1**: Für beliebige Graphen $G$ und $H$: $$\max\{\text{Mobgp}(G), \text{Mobgp}(H \vee K_1)\} \leq \text{Mobgp}(G \odot H) \leq \max\{n(G), \text{gp}(H \vee K_1)\}$$ #### 6. Grenzen für Verbindungsgraphen **Theorem 4.4**: Wenn die Cliquenzahlen von $G$ und $H$ mindestens 2 sind und nicht beide Cliquen sind, dann: $$\min\{\omega(G), \omega(H)\} + 1 \leq \text{Mobgp}(G \vee H) \leq \omega(G) + \omega(H) - 1$$ ### Straffheit der Grenzen Das Papier beweist, dass alle vorgeschlagenen Grenzen straff sind, indem konkrete Graphenfamilien diese Grenzen erreichen: 1. **Straffheit der Untergrenzen**: Beweis durch $K_r \square P_s$, dass die Grenzen in Proposition 2.1 straff sind 2. **Straffheit der Obergrenzen**: Beweis durch kartesische Produkte von Sterngraphen und andere Beispiele 3. **Lückenanalyse**: Beweis, dass die Lücke zwischen Bewegungs-Allgemeine-Position-Zahl und Allgemeine-Position-Zahl beliebig groß sein kann ### Wichtige Erkenntnisse 1. **Kosten der Beweglichkeit**: Die Bewegungs-Allgemeine-Position-Zahl ist typischerweise streng kleiner als die Allgemeine-Position-Zahl 2. **Strukturabhängigkeit**: Die Bewegungs-Allgemeine-Position-Zahl hängt stark von den Struktureigenschaften des Graphen ab 3. **Auswirkungen von Produktoperationen**: Verschiedene Graphenproduktoperationen haben unterschiedliche Auswirkungsmuster auf die Bewegungs-Allgemeine-Position-Zahl ## Verwandte Arbeiten ### Statisches Allgemeine-Position-Problem 1. **Ursprung**: Dudeneys geometrisches Problem, später von Manuel und Klavžar in die Graphentheorie eingeführt 2. **Kartesische-Produkt-Forschung**: Umfangreiche Literatur zur Untersuchung von Allgemeine-Position-Mengen in kartesischen Produkten 3. **Varianten**: Verwandte Konzepte wie äußere Allgemeine Position, untere Allgemeine Position, gegenseitige Sichtbarkeit usw. ### Bewegliche Versionen 1. **Erstmalige Vorschlag**: Erstmals von Klavžar et al. 2023 definiert 2. **Spezielle Graphenfamilien**: Bereits untersuchte Familien umfassen Blockgraphen, Wurzelprodukte, Kneser-Graphen, Einfachzyklusgraphen usw. 3. **Verwandte dynamische Probleme**: Bewegliche gegenseitige Sichtbarkeitsprobleme usw. ### Roboter-Navigationsanwendungen 1. **Gegenseitige Sichtbarkeitsprobleme**: Anwendungen in Roboternavigation und Kommunikation 2. **Pfadplanung**: Bezug zu Hindernisausweichproblemen in der Roboterpfadplanung 3. **Verteilte Algorithmen**: Bezug zu Koordinationsproblemen in verteilten Robotersystemen ## Schlussfolgerungen und Diskussion ### Hauptschlussfolgerungen 1. **Systematischer Rahmen**: Etablierung eines systematischen theoretischen Rahmens für die Bewegungs-Allgemeine-Position-Zahlen kartesischer Produkte, Coronas und Verbindungsgraphen 2. **Exakte Ergebnisse**: Erhalt exakter Werte für die Bewegungs-Allgemeine-Position-Zahlen mehrerer wichtiger Graphenfamilien 3. **Vollständigkeit der Grenzen**: Bereitstellung straf­fer Ober- und Untergrenzen und Beweis ihrer Optimalität 4. **Konstruktionsmethoden**: Entwicklung allgemeiner Methoden zur Konstruktion von Bewegungs-Allgemeine-Position-Mengen ### Einschränkungen 1. **Rechenkomplexität**: Das Papier diskutiert nicht die algorithmische Komplexität der Berechnung von Bewegungs-Allgemeine-Position-Zahlen 2. **Allgemeine Graphen**: Für allgemeine Graphen fehlen noch effektive Berechnungsmethoden für Bewegungs-Allgemeine-Position-Zahlen 3. **Dynamische Strategien**: Optimierungsprobleme von Bewegungsstrategien wurden nicht tiefgreifend untersucht 4. **Praktische Einschränkungen**: Physikalische Einschränkungen in realen Robotersystemen wurden nicht berücksichtigt ### Zukünftige Richtungen Das Papier stellt in Abschnitt 5 mehrere offene Probleme vor: 1. **Nicht-triviale Obergrenzen für kartesische Produkte**: Suche nach besseren Obergrenzen für $\text{Mobgp}(G \square H)$ 2. **Hochdimensionale Fälle**: Untersuchung der Bewegungs-Allgemeine-Position-Zahlen von $k$-fachen kartesischen Produkten $P_\infty^{\square k}$ 3. **Spezielle Graphenfamilien**: Bestimmung exakter Werte für Zylindergraphen $C_7 \square P_s$ und $C_{10} \square P_s$ 4. **Andere Graphenprodukte**: Untersuchung von Bewegungs-Allgemeine-Position-Problemen für starke Produkte und direkte Produkte 5. **Hyperwürfel**: Bestimmung der Bewegungs-Allgemeine-Position-Zahlen von Hyperwürfeln ## Tiefgreifende Bewertung ### Stärken 1. **Theoretische Tiefe**: Bietet tiefgreifende theoretische Analyse des Bewegungs-Allgemeine-Position-Problems und etabliert einen systematischen theoretischen Rahmen 2. **Methodische Innovation**: Entwicklung mehrerer Analysetechniken, einschließlich Schichtanalyse, Symmetrienutzung und konstruktive Beweismethoden 3. **Vollständigkeit der Ergebnisse**: Nicht nur Grenzen, sondern auch Beweis ihrer Straffheit und konkrete Beispiele, die die Grenzen erreichen 4. **Klare Darstellung**: Klare Papierstruktur, strenge Beweise, leicht verständlich und verifizierbar 5. **Problemwichtigkeit**: Das untersuchte Problem hat wichtigen theoretischen Wert und potenzielle praktische Anwendungen ### Mängel 1. **Algorithmische Aspekte**: Mangel an effizienten Algorithmen zur Berechnung von Bewegungs-Allgemeine-Position-Zahlen für allgemeine Graphen 2. **Komplexitätsanalyse**: Keine Diskussion der Rechenkomplexität verwandter Probleme 3. **Praktische Anwendungen**: Die Verbindung zu realen Robotersystemen muss noch gestärkt werden 4. **Offene Probleme**: Viele wichtige offene Probleme warten noch auf Lösungen ### Einfluss 1. **Theoretischer Beitrag**: Trägt eine neue Forschungsrichtung zum Bereich der Kombinatorik und Graphentheorie bei 2. **Methodologischer Wert**: Die bereitgestellten Analysemethoden können auf andere verwandte Probleme angewendet werden 3. **Anwendungspotenzial**: Bietet theoretische Grundlagen für Roboterpfadplanung und Netzwerkoptimierung 4. **Forschungsinspiration**: Die vorgeschlagenen offenen Probleme werden nachfolgende Forschungen inspirieren ### Anwendungsszenarien 1. **Roboternetzwerke**: Koordination und Pfadplanung von Multi-Roboter-Systemen 2. **Sensornetzwerke**: Bereitstellung und Kommunikationsoptimierung von Sensorknoten 3. **Netzwerksicherheit**: Entwurf von Protokollen für sichere verteilte Kommunikation 4. **Graphentheorieforschung**: Als theoretische Grundlage für die Forschung zu Positionsproblemen in der Graphentheorie ## Literaturverzeichnis Das Papier zitiert 32 verwandte Literaturquellen, hauptsächlich einschließlich: 1. **Grundlegende Arbeiten zum Allgemeine-Position-Problem**: Manuel & Klavžar (2018) 2. **Serien von Forschungen zur Allgemeinen Position in kartesischen Produkten**: Mehrere Papiere von Klavžar et al. 3. **Verwandte Arbeiten zur Roboternavigation**: Anwendungsforschung von Aljohani, Sharma et al. 4. **Erstes Papier zum Bewegungs-Allgemeine-Position-Problem**: Klavžar et al. (2023) --- Dieses Papier bietet systematische theoretische Analysen für das Bewegungs-Allgemeine-Position-Problem und hat wichtigen theoretischen Wert im Bereich der Kombinatorik und Graphentheorie, während es gleichzeitig theoretische Grundlagen für praktische Roboternavigationsanwendungen bietet. Obwohl noch einige offene Probleme zu lösen sind, legt das von diesem Papier etablierte theoretische Rahmenwerk und die Analysemethoden eine solide Grundlage für nachfolgende Forschungen.