Lokale fraktionale metrische Dimension rotationssymmetrischer planarer Graphen aus planaren Sehnenzirkeln

Grundinformationen

• Papier-ID: 2105.07808
• Titel: Local fractional metric dimension of rotationally symmetric planar graphs arisen from planar chorded cycles
• Autoren: Shahbaz Ali, Raúl M. Falcón, Muhammad Khalid Mahmood
• Klassifizierung: math.CO (Kombinatorik)
• Veröffentlichungsdatum: 17. Mai 2021 (arXiv-Preprint)
• Papierlink: https://arxiv.org/abs/2105.07808

Zusammenfassung

Dieses Papier beschreibt eine neue Familie rotationssymmetrischer planarer Graphen, die durch eine Kantenverschmelzungskonstruktion basierend auf planaren Sehnenzirkeln entstehen. Für Graphen, die von Sehnenzirkeln mit einer Ordnung von höchstens 6 erzeugt werden, wird ihre lokale fraktionale metrische Dimension etabliert. Durch die Analyse ihres asymptotischen Verhaltens wird die Existenz neuer Familien rotationssymmetrischer planarer Graphen mit konstanter oder beschränkter lokaler fraktionaler Dimension sichergestellt.

Forschungshintergrund und Motivation

Problemhintergrund

1. Ursprung des metrischen Dimensionsproblems: Unabhängig in den 1970er Jahren von Slater sowie von Harary & Melter eingeführt, mit dem Ziel, die minimale Anzahl von Knoten zu bestimmen, die durch Distanzvektoren eindeutig dargestellt werden können
2. Komplexität des Problems: Das metrische Dimensionsproblem ist NP-schwer, aber für verschiedene Graphtypen wurden explizite Lösungen gefunden
3. Praktischer Anwendungswert: Wichtige Anwendungen in Roboternavigation, Mustererkennung, Bildverarbeitung, Darstellung chemischer Verbindungen, kombinatorischer Optimierung und Netzwerken

Forschungsmotivation

1. Theoretische Anforderung: Imran und andere Wissenschaftler stellten das Problem auf, Familien von (rotationssymmetrischen) planaren Graphen mit konstanter metrischer Dimension zu charakterisieren
2. Technische Entwicklung: 2000 formulierten Chartrand et al. das metrische Dimensionsproblem als ganzzahliges Programmierproblem; später führten Currie und Oellermann eine lineare Programmierrelaxation ein und führten das Konzept der fraktionalen metrischen Dimension ein
3. Lokalisierte Forschung: 2018 führten Benish et al. das Konzept der lokalen fraktionalen metrischen Dimension ein, die nur benachbarte Knoten betrifft; dieses Forschungsgebiet befindet sich noch in einem frühen Stadium

Einschränkungen bestehender Methoden

1. Die Forschung zur lokalen fraktionalen metrischen Dimension ist sehr begrenzt, mit expliziten Ergebnissen nur für wenige Graphtypen
2. Jüngste Arbeiten von Liu et al. enthalten technische Fehler, die eine umfassende Neuanalyse erfordern
3. Es fehlt eine systematische Untersuchung von Graphen, die aus höherwertigen Sehnenzirkeln konstruiert sind

Kernbeiträge

1. Neue Graphfamilienkonstruktion: Beschreibung einer neuen Familie rotationssymmetrischer planarer Graphen $G_m(G)$ basierend auf Kantenverschmelzung von planaren Sehnenzirkeln
2. Dimensionsberechnung: Etablierung der lokalen fraktionalen metrischen Dimension für alle rotationssymmetrischen planaren Graphen, die von planaren Sehnenzirkeln der Ordnung $n ≤ 6$ erzeugt werden
3. Asymptotische Analyse: Bereitstellung einer asymptotischen Verhaltensanalyse der lokalen fraktionalen metrischen Dimension dieser Graphfamilien
4. Theoretische Korrektur: Korrektur fehlerhafter Ergebnisse in der Literatur zur lokalen fraktionalen metrischen Dimension von Radgraphen
5. Klassifizierungsvollständigkeit: Umfassende Analyse aller nicht-isomorphen Fälle von Vierecks-, Fünfecks- und Sechsecks-Sehnenzirkeln

Methodische Erklärung

Aufgabendefinition

Untersuchung der lokalen fraktionalen metrischen Dimension rotationssymmetrischer planarer Graphen $G_m(G)$, wobei $G$ ein planarer Sehnenzirkel der Ordnung $n$ ist und $m ≥ 2$ die Anzahl der Kopien darstellt.

Graphkonstruktionsmethode

Gegeben $m$ disjunkte Kopien $G_1, G_2, ..., G_m$ eines planaren Sehnenzirkels $G$, wird $G_m(G)$ durch die folgende Sequenz von Kantenverschmelzungen konstruiert:

1. $G_1(G) := G_1 \cdot G_2(v_2^1v_3^1, v_{n-1}^2v_n^2 : v_{n-1}^2v_n^2)$
2. $G_k(G) := G_{k-1}(G) \cdot G_{k+1}(v_2^kv_3^k, v_{n-1}^{k+1}v_n^{k+1} : v_{n-1}^{k+1}v_n^{k+1})$, für $k \in \{2,...,m-1\}$
3. $G_m(G) := G_{m-1}(G) \cdot G_m(v_2^mv_3^m, v_{n-1}^1v_n^1 : v_{n-1}^1v_n^1)$

Der resultierende Graph $G_m(G)$ ist ein rotationssymmetrischer planarer Graph der Ordnung $m \cdot (n-2)$.

Definitionen von Kernkonzepten

Lokale fraktionale metrische Dimension

Für einen Graphen $G$ ist die lokale fraktionale metrische Dimension definiert als: $\text{ldim}_f(G) := \min\left\{\sum_{v \in V(G)} \vartheta(v) : \vartheta \text{ ist eine lokale Lösungsfunktion von } G\right\}$

wobei eine lokale Lösungsfunktion $\vartheta: V(G) \to [0,1]$ erfüllt: $\sum_{u \in R\{v,w\}} \vartheta(u) \geq 1$ für alle benachbarten Knotenpaare $vw \in E(G)$.

Schlüssellemmata

Lemma 2.1: Für einen endlichen zusammenhängenden Graphen $G$ der Ordnung $n ≥ 2$:

• $\text{ldim}_f(G) \leq \text{dim}_f(G)$
• $\frac{n}{n - \text{ldim}(G) + 1} \leq \text{ldim}_f(G) \leq \frac{n}{\ell(G)} \leq \frac{n}{2}$
• $\text{ldim}_f(G) = 1$ genau dann, wenn $G$ bipartit ist
• $\text{ldim}_f(G) = \frac{n}{2}$ genau dann, wenn jeder Knoten in $V(G)$ einen echten Zwillingknoten hat

Technische Innovationen

1. Systematische Analyse: Erste vollständige Analyse aller rotationssymmetrischen Graphen, die von planaren Sehnenzirkeln der Ordnung höchstens 6 konstruiert sind
2. Berechnungsmethode: Lösung der lokalen fraktionalen metrischen Dimension durch lineare Programmierung für exakte Werte oder Obergrenzen
3. Asymptotische Analyse: Etablierung asymptotischer Verhaltensmuster der lokalen fraktionalen metrischen Dimension für verschiedene Graphfamilien
4. Fehlerkorrektur: Korrektur fehlerhafter Ergebnisse in Referenz 2 zur lokalen fraktionalen metrischen Dimension von Radgraphen

Experimentelle Einrichtung

Graphklassenanalyse

Das Papier analysiert die folgenden Graphklassen:

• Vierecks-Sehnenzirkel: Q₁, Q₂ (2 Typen)
• Fünfecks-Sehnenzirkel: P₁ bis P₆ (6 Typen)
• Sechsecks-Sehnenzirkel: H₁ bis H₁₇ (17 Typen)

Berechnungsmethoden

1. Lineare Programmierung: Konstruktion entsprechender linearer Programmierproblem für jede Graphklasse
2. Ausnutzung von Symmetrie: Nutzung der Rotationssymmetrie des Graphen zur Vereinfachung der Berechnung
3. Analyse der Lösungsumgebung: Berechnung der Größe der Lösungsumgebung $|R\{v,w\}|$ für kritische Kantenpaare

Bewertungsindikatoren

• Exakte Werte der lokalen fraktionalen metrischen Dimension
• Asymptotische Obergrenzen
• Vergleich mit theoretischen Untergrenzen

Experimentelle Ergebnisse

Hauptergebnisse

Vierecksfall

Proposition 3.1: Für $m ≥ 2$:

• $\text{ldim}_f(G_m(Q_1)) = \begin{cases} \frac{3}{2}, & \text{wenn } m = 2 \\ \frac{m}{2}, & \text{sonst} \end{cases}$
• $\text{ldim}_f(G_m(Q_2)) = \begin{cases} \frac{3}{2}, & \text{wenn } m \leq 4 \\ \frac{m}{4}, & \text{sonst} \end{cases}$

Fünfecksfall

Theorem 4.1: Etablierung von Obergrenzen der lokalen fraktionalen metrischen Dimension für alle Fünfecks-Sehnenzirkel $P_1$ bis $P_6$, beispielsweise:

• $\text{ldim}_f(G_m(P_2)) \leq \begin{cases} \frac{2m}{m+1}, & \text{wenn } m \text{ ungerade ist} \\ \frac{6m}{3m+2}, & \text{sonst} \end{cases}$

Sechsecksfall

Theorem 4.2: Für Sechsecks-Sehnenzirkel $H_1$ bis $H_{17}$:

• $\text{ldim}_f(G_m(H_1)) = \text{ldim}_f(G_m(H_2)) = 1$ (bipartite Graphen)
• Andere Fälle geben entsprechende Obergrenzformeln

Korrigierte Ergebnisse für Radgraphen

Lemma 3.1: Für einen Radgraphen $W_n$ der Ordnung $n ≥ 4$: