2025-11-17T18:31:12.470972

Distance mutual-visibility coloring: relations with (total) domination, exact distance graphs and graph products

Babu, Brešar, S et al.
The concept of mutual-visibility (MV) has been extended in several directions. A vertex subset $S$ of a graph $G$ is a $k$-distance mutual-visibility ($k$DMV) set if for any two vertices in $S$, there is a geodesic between them of length at most $k$ whose internal vertices are not in $S$. In this paper, we combine this with the MV coloring as follows. For any integer $k\geq1$, a $k$DMV coloring of $G$ is a partition of $V(G)$ into $k$DMV sets, and the $k$DMV chromatic number $χ_{μ_k}(G)$ is the minimum cardinality of such a partition. When $k=1$ or $k\ge {\rm diam}(G)$, it equals the clique cover number $θ(G)$ or the MV chromatic number $χ_μ(G)$, respectively. So, our attention is given to $1<k<{\rm diam}(G)$ with $k=2$ producing the most interesting results. We prove that $χ_{μ_2}(G)\le|V(G)|/2$ and present large families of graphs that attain the bound. In addition, $χ_{μ_2}(G)$ is bounded from above by the total domination number $γ_t(G)$ if $G$ is isolate-free, while in graphs $G$ with girth $g(G)\geq7$, $χ_{μ_2}(G)$ is bounded from below by the domination number $γ(G)$. A surprising relation with the exact distance-2 graphs is found, which results in $θ(G^{[\natural2]})=γ_{t}(G)$ for any isolate-free graph $G$ with $g(G)\geq7$. The relation is explored further in lexicographic product graphs, where we prove the sharp inequalities $χ_{μ_{2}}(G\circ H)\leq θ(G^{[\natural2]})\leq θ\big{(}(G\circ H)^{[\natural2]}\big{)}$. We also prove a sharp lower (resp. upper) bound on $χ_{μ_2}$ (resp. $χ_{μ_k}$) for the Cartesian (resp. strong) product of two connected graphs and show that they are widely sharp. Finally, we characterize the block graphs $G$ with $χ_{μ_k}(G)=χ_μ(G)$, where $k={\rm diam}(G)-1$.
academic

Colorazione della mutua visibilità a distanza: relazioni con (totale) dominazione, grafi a distanza esatta e prodotti di grafi

Informazioni Fondamentali

  • ID Articolo: 2510.10284
  • Titolo: Distance mutual-visibility coloring: relations with (total) domination, exact distance graphs and graph products
  • Autori: Saneesh Babu, Boštjan Brešar, Aparna Lakshmanan S, Babak Samadi
  • Classificazione: math.CO (Matematica Combinatoria)
  • Data di Pubblicazione: 11 ottobre 2025
  • Link Articolo: https://arxiv.org/abs/2510.10284

Riassunto

Questo articolo esamina il problema della colorazione della mutua visibilità a distanza k, che rappresenta un'estensione del concetto di mutua visibilità introdotto da Di Stefano nel 2022. Per un sottoinsieme di vertici S di un grafo G, S è definito come insieme di mutua visibilità a distanza k (insieme k-DMV) se per ogni coppia di vertici in S esiste un cammino geodetico di lunghezza al massimo k i cui vertici interni non appartengono a S. L'articolo combina questo concetto con la colorazione della mutua visibilità, definendo il numero cromatico k-DMV χ_μ_k(G). La ricerca rivela che il caso k=2 produce i risultati più interessanti, dimostrando che χ_μ_2(G) ≤ |V(G)|/2 e stabilendo profonde connessioni con il numero di dominazione, il numero di dominazione totale e i grafi a distanza esatta.

Contesto di Ricerca e Motivazione

  1. Origine del Problema: Il concetto di mutua visibilità è stato inizialmente proposto da Di Stefano nel 2022, correlato al classico problema dei "tre punti non collineari" e ai problemi di riposizionamento di robot mobili nel piano.
  2. Motivazione della Ricerca:
    • Sebbene il concetto di mutua visibilità sia innovativo, ha già ricevuto ampia attenzione (più di 20 citazioni in MathSciNet)
    • La ricerca esistente si concentra principalmente sulla cardinalità massima degli insiemi di mutua visibilità, mancando di uno studio sistematico dei problemi di colorazione
    • Il vincolo di distanza k rende la comunicazione più efficiente, con valore applicativo pratico
  3. Significato Pratico: Nelle reti di computer o nei social network, i vertici con proprietà di mutua visibilità possono rappresentare entità che richiedono comunicazione efficiente e riservata, garantendo che i messaggi non transitino attraverso altre entità.

Contributi Fondamentali

  1. Introduzione di Nuovo Concetto: Prima definizione del numero cromatico di mutua visibilità a distanza k χ_μ_k(G), che unifica il numero di copertura di clique (k=1) e il numero cromatico di mutua visibilità (k≥diam(G))
  2. Stabilimento di Limiti Fondamentali:
    • Dimostrazione che χ_μ_2(G) ≤ ⌈|V(G)|/2⌉, con identificazione delle famiglie di grafi che raggiungono questo limite
    • Per grafi senza vertici isolati, χ_μ_2(G) ≤ γ_t(G)
    • Per grafi con circonferenza almeno 7, χ_μ_2(G) ≥ γ(G)
  3. Scoperta di Connessioni con Grafi a Distanza Esatta: Dimostrazione che per grafi senza vertici isolati e circonferenza almeno 7, vale θ(G♮2) = γ_t(G)
  4. Studio Sistematico dei Prodotti di Grafi:
    • Prodotto lessicografico: χ_μ_2(G∘H) ≤ θ(G♮2) ≤ θ((G∘H)♮2)
    • Prodotto forte: χ_μ_k(G⊠H) ≤ χ_μ_k(G)χ_μ_k(H)
    • Prodotto cartesiano: χ_μ_2(G□H) ≥ max{χ_μ_2(G)ρ_2(H), χ_μ_2(H)ρ_2(G)}
  5. Caratterizzazione di Classi di Grafi Speciali: Caratterizzazione completa dei grafi a blocchi che soddisfano χ_μ_k(G) = χ_μ(G) (dove k = diam(G)-1)

Spiegazione Dettagliata dei Metodi

Definizione del Compito

Dato un grafo G e un intero positivo k, una colorazione della mutua visibilità a distanza k è una partizione di V(G) in diversi insiemi k-DMV. Un insieme k-DMV M soddisfa: per ogni coppia di vertici u,v in M, esiste un cammino geodetico u,v di lunghezza al massimo k i cui vertici interni non appartengono a M.

Input: Grafo G = (V,E), intero positivo k Output: Una partizione {S_1, S_2, ..., S_t} di V(G) tale che ogni S_i sia un insieme k-DMV Obiettivo: Minimizzare il numero di insiemi nella partizione t

Metodi Tecnici Fondamentali

1. Stabilimento della Teoria di Base

Osservazione 1: Per un grafo G di diametro d, vale la catena di monotonia: χ_μ(G) = χ_μ_d(G) ≤ χ_μ_(G) ≤ ... ≤ χ_μ_1(G) = θ(G)

Osservazione 2: Limite inferiore fondamentale χ_μ_k(G) ≥ ⌈|V(G)|/μ_k(G)⌉

2. Analisi Approfondita del Caso k=2

Teorema 4: Per ogni grafo connesso G, χ_μ_2(G) ≤ ⌈n/2⌉

Strategia di Prova: Attraverso costruzione induttiva su alberi generatori, decomposizione dell'albero in strutture colorabili con due colori.

Teorema 5: Se G non ha vertici isolati, allora χ_μ_2(G) ≤ γ_t(G)

Metodo di Prova: Prova costruttiva, utilizzando un insieme di dominazione totale D = {v_1,...,v_γ_t(G)}, definendo D_i = N_G(v_i)\⋃_^{i-1}N_G(v_j), provando che ogni D_i è un insieme 2-DMV.

3. Relazione tra Circonferenza e Numero di Dominazione

Lemma 6: Se g(G) ≥ 7, allora ogni classe di colore C in una colorazione χ_μ_2(G) è un sottoinsieme della chiusura di un intorno di qualche vertice.

Teorema 7: Se g(G) ≥ 7, allora χ_μ_2(G) ≥ γ(G)

Punti di Innovazione Tecnica

  1. Quadro Unificato: Unificazione della copertura di clique, della colorazione della mutua visibilità nel quadro della colorazione k-DMV
  2. Caratterizzazione Precisa della Circonferenza: Dimostrazione che la circonferenza 7 è il valore minimo che garantisce χ_μ_2(G) ≥ γ(G)
  3. Connessione con Grafi a Distanza Esatta: Prima stabilimento di profonde connessioni tra la colorazione 2-DMV e i grafi a distanza esatta-2
  4. Analisi Sistematica dei Prodotti di Grafi: Fornitura di limiti stretti per tre principali prodotti di grafi

Configurazione Sperimentale

Metodi di Verifica Teorica

L'articolo utilizza principalmente metodi di prova teorica, verificando la stretta dei limiti attraverso la costruzione di famiglie di grafi specifiche:

  1. Cammini e Cicli: Calcolo dei valori esatti di χ_μ_k per P_n e C_n
  2. Famiglie di Grafi Speciali: Costruzione di famiglie di grafi che raggiungono vari limiti
  3. Grafi Prodotto: Analisi delle proprietà di grafi prodotto specifici come P_n⊠K_m

Analisi di Istanze Critiche

Proposizione 2:

  • Per il cammino P_n: χ_μ_k(P_n) = ⌈n/2⌉
  • Per il ciclo C_n: χ_μ_k(C_n) = ⌈n/3⌉ (quando n ≤ 3k), ⌈n/2⌉ (altrimenti)

Proposizione 12: Per P_n⊠K_m (n≥4, m≥2, k∈{2,...,n-2}): χ_μ_k(P_n⊠K_m) = 2⌊n/(k+2)⌋ + termine_di_correzione

Risultati Sperimentali

Risultati Teorici Principali

  1. Stretta dei Limiti Fondamentali:
    • χ_μ_2(G) ≤ ⌈|V(G)|/2⌉ vale per tutti i grafi, raggiunto da cammini, cicli lunghi, ecc.
    • χ_μ_2(G) ≤ γ_t(G) vale per grafi senza vertici isolati, con costruzione di famiglie di grafi dove la differenza può essere arbitrariamente grande
  2. Optimalità della Condizione di Circonferenza:
    • Costruzione di contresempio con circonferenza 6 ma γ(G) = 5 > χ_μ_2(G) = 3
    • Dimostrazione che la circonferenza 7 è la condizione minima che garantisce χ_μ_2(G) ≥ γ(G)
  3. Acutezza dei Risultati sui Prodotti di Grafi:
    • Il limite del prodotto forte χ_μ_k(G⊠H) ≤ χ_μ_k(G)χ_μ_k(H) è raggiunto da infinite famiglie di grafi
    • Il limite inferiore del prodotto cartesiano è raggiunto da grafi toroidali, ecc.

Sorprendente Connessione con Grafi a Distanza Esatta

Teorema 8: Se G non ha vertici isolati e g(G) ≥ 7, allora θ(G♮2) = χ_i_μ_2(G) = γ_t(G)

Questo risultato stabilisce relazioni di uguaglianza tra tre parametri di grafi apparentemente non correlati, con significato teorico importante.

Proprietà Speciali degli Ipercubi

Proposizione 16: Per l'ipercubo n-dimensionale Q_n, χ_μ_2(Q_n) ≤ γ(Q_n)

Congettura: χ_μ_2(Q_n) = γ(Q_n) vale per tutti gli n

Lavori Correlati

  1. Ricerca sulla Mutua Visibilità: Di Stefano (2022) introduce il concetto fondamentale, Cera et al. lo estendono alla versione a distanza k
  2. Colorazione della Mutua Visibilità: Klavžar et al. (2025) studiano per la prima volta il problema della colorazione della mutua visibilità
  3. Grafi a Distanza Esatta: Introdotti negli anni '80, recentemente tornati in attenzione
  4. Teoria della Dominazione: Campo classico della ricerca in teoria dei grafi, con nuove connessioni stabilite in questo articolo

Conclusioni e Discussione

Conclusioni Principali

  1. La colorazione della mutua visibilità a distanza k fornisce una nuova prospettiva per lo studio delle proprietà strutturali dei grafi
  2. Il caso k=2 rivela profonde connessioni con la teoria della dominazione e i grafi a distanza esatta
  3. Il comportamento sotto diversi prodotti di grafi rivela le caratteristiche essenziali di questo parametro
  4. La condizione di circonferenza gioca un ruolo cruciale nella determinazione dei limiti del parametro

Limitazioni

  1. I risultati principali si concentrano sul caso k=2, con ricerca limitata per valori generali di k
  2. La stretta di alcuni limiti è verificata solo in famiglie di grafi specifiche
  3. I problemi di complessità computazionale non sono affrontati

Direzioni Future

L'articolo propone tre problemi aperti specifici:

Problema 1: Caratterizzare i grafi a blocchi G che soddisfano χ_μ_2(G) = θ(G)

Problema 2: Per grafi connessi G,H, vale χ_μ_2(G□H) ≥ max{χ_μ_2(G)γ(H), χ_μ_2(H)γ(G)}?

Problema 3: Vale χ_μ_2(Q_n) = γ(Q_n) per tutti gli ipercubi?

Valutazione Approfondita

Punti di Forza

  1. Profondità Teorica: Stabilimento di nuove connessioni tra diversi rami della teoria dei grafi, in particolare con la teoria della dominazione e i grafi a distanza esatta
  2. Completezza dei Risultati: Fornitura di numerosi limiti stretti con costruzione di famiglie di grafi che raggiungono i limiti
  3. Innovazione Tecnica: La caratterizzazione precisa della circonferenza e l'analisi sistematica dei prodotti di grafi dimostrano tecniche sofisticate
  4. Chiarezza della Presentazione: Definizioni precise, prove rigorose, struttura logica

Insufficienze

  1. Assenza di Complessità Computazionale: Mancanza di discussione sulla complessità computazionale di χ_μ_k(G)
  2. Limitazioni Applicative: Sebbene siano menzionate applicazioni nella comunicazione di rete, manca l'analisi di scenari applicativi concreti
  3. Mancanza di Progettazione Algoritmica: Assenza di algoritmi efficienti per calcolare o approssimare χ_μ_k(G)

Impatto

  1. Contributo Teorico: Apertura di una nuova direzione di ricerca nella teoria dei grafi, con previsione di ricerche successive
  2. Valore Tecnico: Le tecniche di prova e i metodi di costruzione hanno valore di riferimento per ricerche correlate
  3. Potenziale Interdisciplinare: La connessione con la teoria della dominazione può promuovere lo sviluppo trasversale di due campi

Scenari Applicabili

  1. Progettazione di Reti: Applicazione in reti che richiedono la garanzia della riservatezza dei percorsi di comunicazione
  2. Ricerca in Teoria dei Grafi: Come nuovo strumento per lo studio delle proprietà strutturali dei grafi
  3. Ottimizzazione Combinatoria: Fornitura di fondamenti teorici per problemi di ottimizzazione correlati

Bibliografia

L'articolo cita 18 riferimenti correlati, principalmente includenti:

  • Di Stefano (2022): Letteratura originale del concetto di mutua visibilità
  • Cera et al.: Estensione della mutua visibilità a distanza k
  • Klavžar et al.: Prima ricerca sulla colorazione della mutua visibilità
  • Testi classici di teoria dei grafi e letteratura sulla teoria della dominazione

Valutazione Complessiva: Questo è un articolo di alta qualità in teoria dei grafi teorica che fornisce contributi importanti nella nuova direzione di ricerca della mutua visibilità. L'articolo non solo stabilisce un quadro teorico completo, ma scopre anche profonde connessioni con concetti classici della teoria dei grafi, gettando una base solida per lo sviluppo di questo campo. Sebbene vi sia ancora spazio per ulteriori ricerche negli aspetti applicativi e algoritmici, il suo valore teorico e l'innovatività lo rendono una letteratura importante in questo campo.