2025-11-23T03:01:16.593819

Determining the b-chromatic number of subdivision-vertex neighbourhood coronas

Falcón, Venkatachalam, Margaret
Let $G$ and $H$ be two graphs, each one of them being a path, a cycle or a star. In this paper, we determine the $b$-chromatic number of every subdivision-vertex neighbourhood corona $G\boxdot H$ or $G\boxdot K_n$, where $K_n$ is the complete graph of order $n$. It is also established for those graphs $K_n\boxdot G$ having $m$-degree not greater than $n+2$. All the proofs are accompanied by illustrative examples.
academic

Determinazione del numero b-cromatico delle corone di vicinanza di vertici suddivisi

Informazioni Fondamentali

  • ID Articolo: 2302.13667
  • Titolo: Determinazione del numero b-cromatico delle corone di vicinanza di vertici suddivisi
  • Autori: Raúl M. Falcón (Universidad de Sevilla, Spagna), M. Venkatachalam, S. Julie Margaret (Kongunadu Arts and Science College, India)
  • Classificazione: math.CO (Combinatoria)
  • Data di Pubblicazione: 27 febbraio 2023
  • Link dell'Articolo: https://arxiv.org/abs/2302.13667

Riassunto

Siano GG e HH due grafi, ciascuno dei quali sia un cammino, un ciclo o una stella. Questo articolo determina il numero b-cromatico di ogni grafo corona di vicinanza di vertici suddivisi G⊡HG\boxdot H o G⊡KnG\boxdot K_n, dove KnK_n è il grafo completo di ordine nn. Per i grafi Kn⊡GK_n\boxdot G con grado mm non superiore a n+2n+2, vengono stabiliti risultati corrispondenti. Tutte le dimostrazioni sono accompagnate da esempi illustrativi.

Contesto di Ricerca e Motivazione

Contesto del Problema

  1. Concetto di numero b-cromatico: Irving e Manlove hanno introdotto nel 1999 il concetto di colorazione b-cromatica di un grafo, che è una speciale colorazione kk-propria che richiede che ogni colore abbia un vertice-b (un vertice adiacente a vertici di tutti gli altri colori).
  2. Complessità Computazionale: La determinazione del numero b-cromatico di un grafo è un problema NP-difficile nel caso generale, ma è risolvibile in tempo polinomiale per gli alberi.
  3. Ricerca sui Prodotti di Grafi: Esiste una vasta letteratura che affronta il numero b-cromatico di vari prodotti di grafi, come il prodotto cartesiano, il prodotto diretto, il prodotto forte, il prodotto lessicografico, ecc.

Motivazione della Ricerca

  1. Completamento Teorico: La corona di vicinanza di vertici suddivisi (SVN corona) è un importante metodo di costruzione di grafi, ma la ricerca sul suo numero b-cromatico è relativamente carente.
  2. Sistematizzazione dei Metodi: È necessario uno studio sistematico del numero b-cromatico delle corone SVN di classi di grafi fondamentali (cammini, cicli, stelle, grafi completi).
  3. Valore Applicativo: Il numero b-cromatico ha importanti applicazioni in problemi pratici come la colorazione di reti e l'allocazione di frequenze.

Contributi Principali

  1. Determinazione completa del numero b-cromatico delle corone SVN di classi di grafi fondamentali: Per i cammini PnP_n, i cicli CnC_n, le stelle SnS_n e le loro corone SVN con cammini, cicli, stelle e grafi completi, vengono fornite formule esatte del numero b-cromatico.
  2. Stabilimento di risultati parziali per le corone SVN di grafi completi: Per Kn⊡GK_n\boxdot G con grado mm non superiore a n+2n+2, viene determinato il numero b-cromatico.
  3. Fornitura di metodi di dimostrazione costruttivi: Tutti i risultati sono provati attraverso la costruzione esplicita di colorazioni b-cromatiche ottimali, accompagnate da esempi grafici dettagliati.
  4. Sviluppo di un quadro di analisi sistematica: Viene stabilito un metodo generale e strumenti tecnici per analizzare il numero b-cromatico delle corone SVN.

Spiegazione Dettagliata dei Metodi

Definizione del Compito

Input: Due grafi GG e HH, dove G,H∈{Pn,Cn,Sn,Kn}G,H \in \{P_n, C_n, S_n, K_n\}Output: Il numero b-cromatico φ(G⊡H)\varphi(G\boxdot H) della corona SVN Vincoli: Nel caso di Kn⊡GK_n\boxdot G, è richiesto che m(Kn⊡G)≤n+2m(K_n\boxdot G) \leq n+2

Costruzione della Corona SVN

Dato un grafo GG e un grafo HH, il processo di costruzione della corona SVN G⊡HG\boxdot H:

  1. Si inizia dal grafo suddiviso S(G)S(G) di GG (inserendo un nuovo vertice su ogni spigolo)
  2. Si aggiungono ∣V(G)∣|V(G)| copie vertice-disgiunte di HH
  3. Si collegano tutti i vertici nella vicinanza di ogni vertice originale uiu_i in S(G)S(G) a tutti i vertici della (i+1)(i+1)-esima copia di HH

Strumenti Tecnici Chiave

1. Concetto di Grado mm

Per un grafo GG di ordine nn, il suo grado mm è definito come: m(G):=∣{i∈{1,…,n}:d(vi−1)≥i−1}∣m(G) := |\{i \in \{1,\ldots,n\} : d(v_{i-1}) \geq i-1\}| dove i vertici sono ordinati in ordine non crescente di grado.

2. Limiti Fondamentali

  • Limite Inferiore: χ(G)≤φ(G)\chi(G) \leq \varphi(G) (il numero cromatico non supera il numero b-cromatico)
  • Limite Superiore: φ(G)≤Δ(G)+1\varphi(G) \leq \Delta(G) + 1 (il numero b-cromatico non supera il grado massimo più uno)
  • Limite del Grado mm: φ(G)≤m(G)\varphi(G) \leq m(G)

3. Formule del Grado per le Corone SVN

Per un vertice vv in G⊡HG\boxdot H:

d_G(v), & \text{se } v \in V(G) \\ 2|V(H)| + 2, & \text{se } v \in I(G) \\ d_G(u_i) + d_H(v_j), & \text{se } v = v_{i,j} \end{cases}$$ ### Strategia di Analisi L'articolo adotta un metodo di discussione per casi, affrontando diverse combinazioni di classi di grafi: 1. **Corone SVN di cammini** (Sezione 3) 2. **Corone SVN di cicli** (Sezione 4) 3. **Corone SVN di stelle** (Sezione 5) 4. **Corone SVN di grafi completi** (Sezione 6) In ogni caso, la stretta dei limiti superiori è provata attraverso la costruzione di colorazioni b-cromatiche specifiche. ## Risultati Principali ### Numero b-cromatico delle Corone SVN di Cammini **Teorema 6** ($P_n \boxdot P_t$): $$\varphi(P_n \boxdot P_t) = \begin{cases} 4, & \text{se } n=3 \text{ e } t \in \{3,4\} \\ 5, & \text{se } (n=3 \text{ e } t \geq 5) \text{ o } n \in \{4,5\} \\ n-1, & \text{se } 6 \leq n \leq 2t+3 \\ 2t+3, & \text{altrimenti} \end{cases}$$ **Teoremi 7-9**: Analogamente, vengono fornite formule esatte per $P_n \boxdot C_t$, $P_n \boxdot S_t$, $P_n \boxdot K_t$. ### Numero b-cromatico delle Corone SVN di Cicli **Teorema 11** ($C_n \boxdot P_t$): $$\varphi(C_n \boxdot P_t) = \begin{cases} 5, & \text{se } n \in \{3,4\} \\ n, & \text{se } 5 \leq n \leq 2t+2 \\ 2t+3, & \text{altrimenti} \end{cases}$$ ### Numero b-cromatico delle Corone SVN di Stelle **Teorema 17**: Per le corone SVN di stelle con classi di grafi fondamentali, viene stabilita una formula completa del numero b-cromatico, i cui risultati chiave includono: $$\varphi(S_n \boxdot K_{t'}) = \min\{n, t'+2\} + t'$$ ### Numero b-cromatico delle Corone SVN di Grafi Completi **Teoremi 20-24**: Sotto il vincolo del grado $m$, vengono forniti i numeri b-cromatici di $K_n\boxdot G$, ad esempio: $$\varphi(K_n \boxdot P_t) = \begin{cases} n+1, & \text{in determinate condizioni} \\ n+2, & \text{in altre condizioni} \end{cases}$$ ## Punti di Innovazione Tecnica ### 1. Metodo di Dimostrazione Costruttiva - Non solo si provano i limiti superiori, ma si dimostrano anche i limiti inferiori attraverso la costruzione esplicita di colorazioni b-cromatiche ottimali - Ogni costruzione è accompagnata da esempi grafici dettagliati, aumentando la verificabilità dei risultati ### 2. Concetto di Insieme b-Arcobaleno Viene introdotto il concetto di insieme b-arcobaleno per semplificare l'identificazione dei vertici-b, contrassegnati nel grafo con simboli diversi: - Croce ×: vertici di un insieme b-arcobaleno specifico - Triangolo △: altri vertici-b - Cerchio ●: vertici ordinari ### 3. Tecniche di Aritmetica Modulare L'aritmetica modulare è ampiamente utilizzata nella costruzione della colorazione per garantire la periodicità e la correttezza della colorazione, ad esempio: $$c(u_i) = (i+1) \bmod \min\{m(P_n \boxdot P_t), n\}$$ ### 4. Sistematizzazione della Discussione per Casi La discussione per casi è condotta in modo sistematico in base agli intervalli di parametri, garantendo la copertura di tutte le possibili situazioni. ## Verifica Sperimentale ### Verifica Grafica L'articolo fornisce numerosi esempi grafici per verificare i risultati teorici: - Figura 2: Colorazione b-cromatica ottimale di $P_{10} \boxdot P_3$ - Figure 3-4: Colorazioni di corone SVN di cammini con parametri diversi - Figura 11: Esempio di colorazione di corona SVN di cicli - Figure 17-18: Costruzioni di colorazione di corone SVN di stelle ### Verifica della Costruzione La dimostrazione di ogni teorema contiene algoritmi di costruzione di colorazione concreti che possono essere direttamente verificati: 1. Correttezza della colorazione (vertici adiacenti hanno colori diversi) 2. Esistenza di vertici-b (ogni colore ha un vertice-b) 3. Ottimalità (raggiungimento del limite teorico) ## Lavori Correlati ### Storia della Ricerca sul Numero b-cromatico 1. **Irving-Manlove (1999)**: Prima introduzione del concetto di numero b-cromatico 2. **Ricerca su vari prodotti di grafi**: Il numero b-cromatico del prodotto cartesiano, del prodotto diretto, del prodotto forte, ecc. è stato ampiamente studiato 3. **Classi di grafi speciali**: Il numero b-cromatico di cammini, cicli, stelle e grafi completi è noto ### Posizione di questo Articolo - **Colmare le lacune**: La ricerca sul numero b-cromatico delle corone SVN è relativamente carente - **Innovazione metodologica**: Fornisce un metodo sistematico e costruttivo - **Completezza dei risultati**: Fornisce risultati completi per le combinazioni di classi di grafi fondamentali ## Conclusioni e Discussione ### Conclusioni Principali 1. **Completezza**: Per le corone SVN di classi di grafi fondamentali (cammini, cicli, stelle, grafi completi), vengono forniti risultati completi di determinazione del numero b-cromatico 2. **Precisione**: Tutti i risultati sono valori esatti, non approssimazioni o limiti 3. **Costruttività**: Vengono forniti metodi di costruzione concreti di colorazioni ottimali ### Limitazioni 1. **Restrizione alle classi di grafi**: Sono considerate solo classi di grafi fondamentali; i risultati per grafi generali richiedono ulteriori ricerche 2. **Vincoli per grafi completi**: I risultati per $K_n\boxdot G$ richiedono condizioni di vincolo sul grado $m$ 3. **Complessità**: In alcuni casi, la discussione per casi è piuttosto complessa ### Direzioni Future 1. **Estensione a classi di grafi più generali**: Ricerca del numero b-cromatico delle corone SVN di classi di grafi più generali 2. **Ricerca algoritmica**: Sviluppo di algoritmi efficienti per il calcolo del numero b-cromatico 3. **Esplorazione applicativa**: Applicazione dei risultati a problemi pratici di colorazione di reti ## Valutazione Approfondita ### Punti di Forza 1. **Contributo teorico significativo**: Risoluzione sistematica del problema del numero b-cromatico per una classe importante di prodotti di grafi 2. **Metodo rigoroso**: Il metodo di dimostrazione costruttiva garantisce l'affidabilità dei risultati 3. **Esposizione chiara**: Numerose figure ed esempi rendono le dimostrazioni complesse facili da comprendere 4. **Completezza dei risultati**: Copertura di tutte le importanti combinazioni di classi di grafi fondamentali ### Insufficienze 1. **Innovazione tecnica limitata**: Principalmente applicazione sistematica di metodi esistenti, mancanza di tecniche fondamentalmente nuove 2. **Valore applicativo poco chiaro**: Mancanza di discussione su scenari di applicazione pratica 3. **Analisi della complessità computazionale assente**: Non viene discussa la complessità temporale degli algoritmi di costruzione ### Impatto 1. **Valore teorico**: Fornisce un importante complemento alla teoria del numero b-cromatico dei grafi 2. **Valore metodologico**: I metodi costruttivi possono essere generalizzati alla ricerca di altri prodotti di grafi 3. **Valore di completezza**: Colma il vuoto nella ricerca del numero b-cromatico delle corone SVN ### Scenari di Applicabilità 1. **Ricerca teorica**: Ricerca fondamentale nei campi della teoria dei grafi e dell'ottimizzazione combinatoria 2. **Progettazione di reti**: Problemi di colorazione di reti che richiedono considerazione di vincoli di vicinanza 3. **Progettazione di algoritmi**: Come modulo di base per algoritmi di colorazione di grafi più complessi ## Bibliografia L'articolo cita 25 riferimenti correlati, principalmente includenti: - Irving & Manlove (1999): Definizione originale del numero b-cromatico - Kouider & Mahéo e altri: Ricerca sul numero b-cromatico di vari prodotti di grafi - Liu & Lu (2013): Ricerca sulla teoria spettrale delle corone SVN - Brooks (1941): Risultati classici sulla colorazione di grafi