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

Détermination du nombre b-chromatique des couronnes de voisinage de subdivision-sommet

Informations de base

  • ID de l'article: 2302.13667
  • Titre: Determining the b-chromatic number of subdivision-vertex neighbourhood coronas
  • Auteurs: Raúl M. Falcón (Universidad de Sevilla, Espagne), M. Venkatachalam, S. Julie Margaret (Kongunadu Arts and Science College, Inde)
  • Classification: math.CO (Combinatoire)
  • Date de publication: 27 février 2023
  • Lien de l'article: https://arxiv.org/abs/2302.13667

Résumé

Soient GG et HH deux graphes, chacun étant un chemin, un cycle ou un graphe étoilé. Cet article détermine le nombre b-chromatique de chaque graphe couronne de voisinage de subdivision-sommet G⊡HG\boxdot H ou G⊡KnG\boxdot K_n, où KnK_n est le graphe complet d'ordre nn. Des résultats correspondants sont également établis pour les graphes Kn⊡GK_n\boxdot G dont le degré mm ne dépasse pas n+2n+2. Toutes les preuves sont accompagnées d'exemples illustratifs.

Contexte et motivation de la recherche

Contexte du problème

  1. Concept du nombre b-chromatique: Irving et Manlove ont introduit en 1999 le concept de coloration b-chromatique d'un graphe, qui est une coloration kk-propre spéciale exigeant que chaque couleur possède un sommet b (ce sommet étant adjacent à des sommets de toutes les autres couleurs).
  2. Complexité computationnelle: La détermination du nombre b-chromatique d'un graphe est un problème NP-difficile en général, mais elle est résoluble en temps polynomial pour les arbres.
  3. Recherche sur les produits de graphes: De nombreuses études ont porté sur le nombre b-chromatique de divers produits de graphes, tels que le produit cartésien, le produit direct, le produit fort, le produit lexicographique, etc.

Motivation de la recherche

  1. Perfectionnement théorique: La couronne de voisinage de subdivision-sommet (SVN corona) est une méthode importante de construction de graphes, mais sa recherche sur le nombre b-chromatique est relativement insuffisante.
  2. Systématisation des méthodes: Il est nécessaire d'étudier systématiquement le nombre b-chromatique des couronnes SVN de classes de graphes fondamentales (chemins, cycles, graphes étoilés, graphes complets).
  3. Valeur applicative: Le nombre b-chromatique possède des applications importantes dans les problèmes pratiques tels que la coloration de réseaux et l'allocation de fréquences.

Contributions principales

  1. Détermination complète du nombre b-chromatique des couronnes SVN de classes de graphes fondamentales: Pour les couronnes SVN de chemins PnP_n, de cycles CnC_n, de graphes étoilés SnS_n avec des chemins, des cycles, des graphes étoilés et des graphes complets, des formules précises du nombre b-chromatique sont fournies.
  2. Établissement de résultats partiels pour les couronnes SVN de graphes complets: Pour Kn⊡GK_n\boxdot G dont le degré mm ne dépasse pas n+2n+2, le nombre b-chromatique est déterminé.
  3. Fourniture de méthodes de preuve constructives: Tous les résultats sont prouvés par la construction de colorations b-chromatiques optimales explicites, accompagnées d'exemples de graphes détaillés.
  4. Développement d'un cadre d'analyse systématique: Un cadre général et des outils techniques pour analyser le nombre b-chromatique des couronnes SVN sont établis.

Explication détaillée des méthodes

Définition de la tâche

Entrée: Deux graphes GG et HH, où G,H∈{Pn,Cn,Sn,Kn}G,H \in \{P_n, C_n, S_n, K_n\}Sortie: Le nombre b-chromatique φ(G⊡H)\varphi(G\boxdot H) de la couronne SVN Contraintes: Pour le cas Kn⊡GK_n\boxdot G, il est requis que m(Kn⊡G)≤n+2m(K_n\boxdot G) \leq n+2

Construction de la couronne SVN

Étant donnés les graphes GG et HH, le processus de construction de la couronne SVN G⊡HG\boxdot H:

  1. Commencer par le graphe de subdivision S(G)S(G) de GG (insérer un nouveau sommet sur chaque arête)
  2. Ajouter ∣V(G)∣|V(G)| copies sommet-disjointes de HH
  3. Connecter tous les sommets du voisinage de chaque sommet original uiu_i dans S(G)S(G) à tous les sommets de la (i+1)(i+1)-ième copie de HH

Outils techniques clés

1. Concept du degré mm

Pour un graphe GG d'ordre nn, son degré mm est défini par: m(G):=∣{i∈{1,…,n}:d(vi−1)≥i−1}∣m(G) := |\{i \in \{1,\ldots,n\} : d(v_{i-1}) \geq i-1\}| où les sommets sont ordonnés par degré décroissant.

2. Bornes fondamentales

  • Borne inférieure: χ(G)≤φ(G)\chi(G) \leq \varphi(G) (le nombre chromatique ne dépasse pas le nombre b-chromatique)
  • Borne supérieure: φ(G)≤Δ(G)+1\varphi(G) \leq \Delta(G) + 1 (le nombre b-chromatique ne dépasse pas le degré maximum plus un)
  • Borne du degré mm: φ(G)≤m(G)\varphi(G) \leq m(G)

3. Formule du degré pour la couronne SVN

Pour un sommet vv dans G⊡HG\boxdot H:

d_G(v), & \text{si } v \in V(G) \\ 2|V(H)| + 2, & \text{si } v \in I(G) \\ d_G(u_i) + d_H(v_j), & \text{si } v = v_{i,j} \end{cases}$$ ### Stratégie d'analyse L'article adopte une méthode de discussion par cas, traitant différentes combinaisons de classes de graphes: 1. **Couronnes SVN de chemins** (Section 3) 2. **Couronnes SVN de cycles** (Section 4) 3. **Couronnes SVN de graphes étoilés** (Section 5) 4. **Couronnes SVN de graphes complets** (Section 6) Pour chaque cas, la rigueur de la borne supérieure est prouvée par la construction d'une coloration b-chromatique concrète. ## Résultats principaux ### Nombre b-chromatique des couronnes SVN de chemins **Théorème 6** ($P_n \boxdot P_t$): $$\varphi(P_n \boxdot P_t) = \begin{cases} 4, & \text{si } n=3 \text{ et } t \in \{3,4\} \\ 5, & \text{si } (n=3 \text{ et } t \geq 5) \text{ ou } n \in \{4,5\} \\ n-1, & \text{si } 6 \leq n \leq 2t+3 \\ 2t+3, & \text{sinon} \end{cases}$$ **Théorèmes 7-9**: Des formules précises similaires sont données pour $P_n \boxdot C_t$, $P_n \boxdot S_t$, $P_n \boxdot K_t$. ### Nombre b-chromatique des couronnes SVN de cycles **Théorème 11** ($C_n \boxdot P_t$): $$\varphi(C_n \boxdot P_t) = \begin{cases} 5, & \text{si } n \in \{3,4\} \\ n, & \text{si } 5 \leq n \leq 2t+2 \\ 2t+3, & \text{sinon} \end{cases}$$ ### Nombre b-chromatique des couronnes SVN de graphes étoilés **Théorème 17**: Pour les couronnes SVN de graphes étoilés avec des classes de graphes fondamentales, une formule complète du nombre b-chromatique est établie, dont les résultats clés incluent: $$\varphi(S_n \boxdot K_{t'}) = \min\{n, t'+2\} + t'$$ ### Nombre b-chromatique des couronnes SVN de graphes complets **Théorèmes 20-24**: Sous la contrainte du degré $m$, le nombre b-chromatique de $K_n\boxdot G$ est donné, par exemple: $$\varphi(K_n \boxdot P_t) = \begin{cases} n+1, & \text{certaines conditions} \\ n+2, & \text{autres conditions} \end{cases}$$ ## Points d'innovation technique ### 1. Méthode de preuve constructive - Non seulement les bornes supérieures sont prouvées, mais les bornes inférieures sont également prouvées par la construction explicite de colorations b-chromatiques optimales - Chaque construction est accompagnée d'exemples de graphes détaillés, renforçant la vérifiabilité des résultats ### 2. Concept d'ensemble b-arc-en-ciel Le concept d'ensemble b-arc-en-ciel est introduit pour simplifier l'identification des sommets b, marqués par différents symboles dans le graphe: - Croix ×: sommets de l'ensemble b-arc-en-ciel spécifique - Triangle △: autres sommets b - Cercle ●: sommets ordinaires ### 3. Technique d'arithmétique modulaire L'arithmétique modulaire est largement utilisée dans la construction de coloration pour assurer la périodicité et la correction de la coloration, par exemple: $$c(u_i) = (i+1) \bmod \min\{m(P_n \boxdot P_t), n\}$$ ### 4. Systématisation de la discussion par cas Une discussion par cas fine selon les plages de paramètres assure la couverture de tous les cas possibles. ## Vérification expérimentale ### Vérification par graphes L'article fournit de nombreux exemples de graphes pour vérifier les résultats théoriques: - Figure 2: Coloration b-chromatique optimale de $P_{10} \boxdot P_3$ - Figures 3-4: Colorations de couronnes SVN de chemins avec différents paramètres - Figure 11: Exemple de coloration de couronne SVN de cycle - Figures 17-18: Constructions de coloration de couronnes SVN de graphes étoilés ### Vérification de construction La preuve de chaque théorème contient un algorithme de construction de coloration concret, directement vérifiable: 1. Correction de la coloration (sommets adjacents de couleurs différentes) 2. Existence de sommets b (chaque couleur possède un sommet b) 3. Optimalité (atteint la borne théorique) ## Travaux connexes ### Historique de la recherche sur le nombre b-chromatique 1. **Irving-Manlove (1999)**: Introduction initiale du concept de nombre b-chromatique 2. **Recherche sur divers produits de graphes**: Le nombre b-chromatique du produit cartésien, du produit direct, du produit fort, etc. a fait l'objet d'études approfondies 3. **Classes de graphes spéciales**: Le nombre b-chromatique des chemins, cycles, graphes étoilés et graphes complets est connu ### Position de cet article - **Combler une lacune**: La recherche sur le nombre b-chromatique des couronnes SVN est relativement insuffisante - **Innovation méthodologique**: Fournir une méthode systématique et constructive - **Résultats complets**: Fournir des résultats de détermination complets pour les combinaisons de classes de graphes fondamentales ## Conclusion et discussion ### Conclusions principales 1. **Complétude**: Pour les couronnes SVN de classes de graphes fondamentales (chemins, cycles, graphes étoilés, graphes complets), des résultats de détermination complets du nombre b-chromatique sont fournis 2. **Précision**: Tous les résultats sont des valeurs exactes, non des approximations ou des bornes 3. **Constructivité**: Des méthodes de construction de coloration optimale concrètes sont fournies ### Limitations 1. **Restriction des classes de graphes**: Seules les classes de graphes fondamentales sont considérées; les résultats pour les graphes généraux nécessitent une recherche ultérieure 2. **Contrainte des graphes complets**: Les résultats pour $K_n\boxdot G$ nécessitent une condition de contrainte du degré $m$ 3. **Complexité**: La discussion par cas dans certaines situations est relativement complexe ### Directions futures 1. **Extension des classes de graphes**: Étudier le nombre b-chromatique des couronnes SVN de classes de graphes plus générales 2. **Recherche algorithmique**: Développer des algorithmes efficaces de calcul du nombre b-chromatique 3. **Exploration applicative**: Appliquer les résultats aux problèmes pratiques de coloration de réseaux ## Évaluation approfondie ### Points forts 1. **Contribution théorique significative**: Résolution systématique du problème du nombre b-chromatique pour une classe importante de produits de graphes 2. **Méthode rigoureuse**: La méthode de preuve constructive assure la fiabilité des résultats 3. **Expression claire**: De nombreux graphes et exemples rendent les preuves complexes faciles à comprendre 4. **Résultats complets**: Couverture de toutes les combinaisons importantes de classes de graphes fondamentales ### Insuffisances 1. **Innovation technique limitée**: Principalement l'application systématique de méthodes existantes, manquant de techniques fondamentalement nouvelles 2. **Valeur applicative peu claire**: Manque de discussion sur les scénarios d'application pratique 3. **Absence d'analyse de complexité computationnelle**: La complexité temporelle des algorithmes de construction n'est pas discutée ### Impact 1. **Valeur théorique**: Fournit un complément important à la théorie du nombre b-chromatique des graphes 2. **Valeur méthodologique**: Les méthodes de construction peuvent être généralisées à l'étude d'autres produits de graphes 3. **Valeur de complétude**: Comble le vide dans la recherche sur le nombre b-chromatique des couronnes SVN ### Scénarios applicables 1. **Recherche théorique**: Recherche fondamentale dans les domaines de la théorie des graphes et de l'optimisation combinatoire 2. **Conception de réseaux**: Problèmes de coloration de réseaux nécessitant de considérer les contraintes de voisinage 3. **Conception d'algorithmes**: Comme module de base pour des algorithmes de coloration de graphes plus complexes ## Références L'article cite 25 références connexes, incluant principalement: - Irving & Manlove (1999): Définition originale du nombre b-chromatique - Kouider & Mahéo et al.: Recherche sur le nombre b-chromatique de divers produits de graphes - Liu & Lu (2013): Recherche sur la théorie spectrale des couronnes SVN - Brooks (1941): Résultats classiques en coloration de graphes