Nombre de Bondage Indépendant dans les Graphes sous Contraintes de Maille

Informations Fondamentales

• ID de l'article : 2411.01687
• Titre : Independent Bondage Number in Graphs under Girth Constraints
• Auteurs : E.G.K.M. Gamlath, Andrew Pham, Bing Wei
• Classification : math.CO (Mathématiques Combinatoires)
• Date de publication : 15 octobre 2025 (prépublication arXiv)
• Lien de l'article : https://arxiv.org/abs/2411.01687

Résumé

Étant donné un graphe simple fini $G$, le nombre de bondage indépendant d'un graphe $G$ est la taille minimale d'un ensemble d'arêtes dont la suppression produit un graphe ayant un nombre de domination indépendante strictement supérieur à celui de $G$. Bien que le nombre de bondage dans les graphes sous contraintes de maille ait été étudié, les résultats concernant le nombre de bondage indépendant restent peu nombreux. Cette étude établit des bornes supérieures pour le nombre de bondage indépendant des graphes planaires sous contraintes de maille données, étendant les résultats de Fischermann, Rautenbach et Volkmann sur le nombre de bondage ainsi que les résultats de Borodin et Ivanova sur la structure des graphes planaires. En particulier, nous identifions des structures supplémentaires et établissons des bornes pour le nombre de bondage indépendant des graphes planaires satisfaisant $\delta(G) \geq 2$ et $g(G) \geq 5$, $\delta(G) \geq 3$ et $g(G) \geq 4$, ainsi que $\delta(G) \geq 2$ et $g(G) \geq 10$.

Contexte et Motivation de la Recherche

Définition du Problème et Importance

1. Concepts fondamentaux :
   • Ensemble de domination indépendante : ensemble de sommets qui est à la fois un ensemble indépendant et un ensemble dominant
   • Nombre de domination indépendante $\gamma_i(G)$ : cardinalité de l'ensemble de domination indépendante minimal
   • Nombre de bondage indépendant $b_i(G)$ : taille minimale d'un ensemble d'arêtes $B$ tel que $\gamma_i(G-B) > \gamma_i(G)$
2. Signification de la recherche :
   • Mesure la fragilité de la structure de domination indépendante d'un réseau en cas de défaillance d'arêtes
   • Possède une valeur d'application importante dans l'analyse des défaillances de liaisons dans les réseaux interconnectés
   • Étend le champ d'étude de la théorie classique de la domination
3. Limitations des recherches existantes :
   • Le nombre de bondage traditionnel $b(G)$ a été étudié systématiquement sous contraintes de maille
   • Les résultats concernant le nombre de bondage indépendant $b_i(G)$ sont extrêmement limités, particulièrement sous contraintes de maille
   • Absence de résultats de bornes supérieures constantes pour des classes de graphes spécifiques
4. Motivation de la recherche :
   • Inspirée par les résultats de Fischermann et al. (2003) sur les contraintes de maille du nombre de bondage pour les graphes planaires
   • Exploration naturelle de la question de savoir si le nombre de bondage indépendant peut également obtenir des bornes supérieures constantes similaires sous contraintes de maille
   • Combler les lacunes dans la recherche théorique du nombre de bondage indépendant

Contributions Principales

1. Établissement de quatre théorèmes de bornes supérieures constantes principales :
   • $\delta(G) \geq 3$ et $g(G) \geq 4$ : $b_i(G) \leq 6$
   • $\delta(G) \geq 2$ et $g(G) \geq 5$ : $b_i(G) \leq 5$
   • $\delta(G) \geq 2$ et $g(G) \geq 7$ : $b_i(G) \leq 4$
   • $\delta(G) \geq 2$ et $g(G) \geq 10$ : $b_i(G) \leq 3$
2. Identification de multiples configurations de structures graphiques critiques :
   • Pour $\delta(G) \geq 2$ et $g(G) \geq 5$ : identification de 10 configurations inévitables
   • Pour $\delta(G) \geq 3$ et $g(G) \geq 4$ : identification de 3 configurations critiques
   • Construction d'ensembles de bondage indépendant correspondants pour chaque configuration
3. Extension du cadre théorique existant :
   • Généralisation des résultats de Fischermann et al. sur le nombre de bondage au nombre de bondage indépendant
   • Utilisation et développement de la théorie de la structure des graphes planaires de Borodin et Ivanova
4. Fourniture d'une méthode de preuve systématique :
   • Utilisation de la méthode de décharge (discharging method) pour identifier les structures inévitables
   • Fourniture de preuves constructives d'ensembles de bondage indépendant pour chaque structure

Explication Détaillée de la Méthode

Fondements Théoriques

Système de définitions :

• Nombre de bondage indépendant du graphe $G$ : $b_i(G) = \min\{|B| : B \subseteq E(G), \gamma_i(G-B) > \gamma_i(G)\}$
• Maille $g(G)$ : longueur du plus court cycle du graphe
• Degré minimum $\delta(G)$ : degré minimum des sommets du graphe

Lemme clé :

Théorème 1 (Priddy, Wang, Wei) : Pour tout graphe non vide G,
b_i(G) ≤ min{d(u) + d(v) - |N(u) ∩ N(v)| - 1 : uv ∈ E(G)}

Méthode Centrale : Technique de Décharge

Principe de la méthode de décharge :

1. Attribution initiale de charge : allocation de charge selon trois méthodes naturelles dérivées de la formule d'Euler
   • Charge des sommets : $d(v) - 6$, charge des faces : $2\ell(f) - 6$ (décharge par sommets)
   • Charge des sommets : $2d(v) - 6$, charge des faces : $\ell(f) - 6$ (décharge par faces)
   • Charge des sommets : $d(v) - 4$, charge des faces : $\ell(f) - 4$ (décharge équilibrée)
2. Règles de redistribution de charge : conception de règles spécifiques permettant le flux de charge des sommets/faces à charge positive vers les sommets/faces à charge négative
3. Identification de structures : analyse de la distribution finale de charge pour prouver l'inévitabilité de certaines structures

Stratégie de Mise en Œuvre Concrète

Pour le cas $\delta(G) \geq 2$ et $g(G) \geq 5$ :

Règles de décharge :

• (R1) Chaque sommet de degré 2 reçoit $\frac{1}{2}$ unité de charge de chaque sommet adjacent et de chaque face incidente
• (R2) Chaque sommet de degré 3 reçoit $\frac{1}{3}$ unité de charge de chaque face incidente
• (R3) Règles d'allocation de charge pour certains sommets de degré 6
• (R4) Règles d'allocation de charge pour certains sommets de degré 5

Vérification des faits clés :

• Fait 1 : La charge finale de chaque sommet de degré ≤ 4 est nulle
• Fait 2 : Caractère mutuellement exclusif de l'allocation de charge des sommets de degré 5+
• Faits 3-8 : Garantie de charge non négative pour diverses faces et sommets

Résultats Principaux

Théorème 7 : Caractérisation de Structure pour $\delta(G) \geq 2$ et $g(G) \geq 5$

Chaque graphe planaire $G$ satisfaisant les conditions doit contenir l'une des configurations suivantes :

• (a) Arête $(2,4^-)$ ou arête $(3,3^-)$
• (b) Sommet $v \in S(5^+, [d(v)-1]^+)$ dont les voisins restants sont des sommets de degré 4 ou des sommets dans $S(5^+,1^+)$
• (c)-(j) Huit configurations complexes impliquant des sommets de degré 5 avec des voisins de degré 2 partageant une 5-face

Théorème 8 : Borne Supérieure du Nombre de Bondage Indépendant

Pour un graphe planaire $G$ avec $\delta(G) \geq 2$ et $g(G) \geq 5$ : $b_i(G) \leq 5$

Schéma de preuve :

1. Construction d'un ensemble d'arêtes $B$ de taille ≤ 5 pour chaque configuration
2. Preuve que la suppression de $B$ augmente strictement le nombre de domination indépendante
3. Utilisation du raisonnement par l'absurde et des propriétés des ensembles de domination indépendante

Autres Résultats Principaux

Théorème 10 : $\delta(G) \geq 3$ et $g(G) \geq 4$ ⟹ $b_i(G) \leq 6$

Corollaire 1 : $\delta(G) \geq 2$ et $g(G) \geq 7$ ⟹ $b_i(G) \leq 4$ (basé sur le lemme de Cranston-West)

Théorème 13 : $\delta(G) \geq 2$ et $g(G) \geq 10$ ⟹ $b_i(G) \leq 3$

Points d'Innovation Technique

Innovations Méthodologiques

1. Application systématique pour la première fois de la méthode de décharge à l'étude du nombre de bondage indépendant
2. Développement de nouvelles stratégies d'allocation de charge : conception adaptée aux propriétés spéciales du nombre de bondage indépendant
3. Établissement d'un cadre complet pour l'identification de structures et la construction d'ensembles de bondage

Contributions Théoriques

1. Extension des résultats classiques : généralisation du nombre de bondage au nombre de bondage indépendant
2. Comblage des lacunes théoriques : fourniture des premiers résultats systématiques du nombre de bondage indépendant sous contraintes de maille
3. Identification de nouvelles structures graphiques : découverte de configurations critiques affectant le nombre de bondage indépendant

Techniques de Preuve

1. Analyse fine de charge : assurance de la correction du processus de décharge par vérification détaillée des faits
2. Preuve constructive : construction explicite d'ensembles de bondage indépendant pour chaque configuration
3. Complétude de l'analyse par cas : épuisement de toutes les configurations de structures possibles

Travaux Connexes

Développement Historique

1. 1979 : Garey et Johnson prouvent la NP-complétude du problème du nombre de domination
2. 1983 : Bauer et al. introduisent le concept de stabilité de domination par arêtes
3. 1990 : Fink et al. définissent formellement le nombre de bondage
4. 2003 : Fischermann et al. établissent les bornes supérieures du nombre de bondage sous contraintes de maille

Recherche sur le Nombre de Bondage Indépendant

1. 2018 : Priddy, Wang, Wei étudient systématiquement pour la première fois le nombre de bondage indépendant
2. 2021 : Pham et Wei établissent des bornes supérieures constantes pour les graphes planaires avec $\delta(G) \geq 3$
3. Cet article : première étude du nombre de bondage indépendant sous contraintes de maille

Comparaison des Méthodes Techniques

• Méthodes traditionnelles : basées principalement sur l'analyse des contraintes de degré et des structures locales
• Méthode de cet article : combinaison des contraintes de maille et de la technique de décharge, fournissant une caractérisation de structure plus fine

Conclusion et Discussion

Conclusions Principales

Établissement d'un système complet de bornes supérieures pour le nombre de bondage indépendant des graphes planaires sous contraintes de maille :