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: dG⊡H(v)={dG(v),si v∈V(G)2∣V(H)∣+2,si v∈I(G)dG(ui)+dH(vj),si v=vi,jd_{G\boxdot H}(v) = \begin{cases} 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 (Pn⊡PtP_n \boxdot P_t): φ(Pn⊡Pt)={4,si n=3 et t∈{3,4}5,si (n=3 et t≥5) ou n∈{4,5}n−1,si 6≤n≤2t+32t+3,sinon\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 Pn⊡CtP_n \boxdot C_t, Pn⊡StP_n \boxdot S_t, Pn⊡KtP_n \boxdot K_t.

Nombre b-chromatique des couronnes SVN de cycles

Théorème 11 (Cn⊡PtC_n \boxdot P_t): φ(Cn⊡Pt)={5,si n∈{3,4}n,si 5≤n≤2t+22t+3,sinon\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: φ(Sn⊡Kt′)=min⁡{n,t′+2}+t′\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é mm, le nombre b-chromatique de Kn⊡GK_n\boxdot G est donné, par exemple: φ(Kn⊡Pt)={n+1,certaines conditionsn+2,autres conditions\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(ui)=(i+1) mod min⁡{m(Pn⊡Pt),n}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 P10⊡P3P_{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 Kn⊡GK_n\boxdot G nécessitent une condition de contrainte du degré mm
  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