2025-11-21T06:28:15.048096

Some results on minimum saturated graphs

Zhang, Cui, Hu et al.
Let $G$ be a graph and $\mathcal{F}$ be a family of graphs. We say a graph $G$ is $\mathcal{F}$-saturated if $G$ does not contain any member in $\mathcal{F}$ and for any $e\in E(\overline{G})$, $G+e$ creates a copy of some member in $ \mathcal{F}$. The saturation number of $\mathcal{F}$ is the minimum number of edges of an $\mathcal{F}$-saturated graphs with $n$ vertices, denoted by $\sat(n,\mathcal{F})$. If $\mathcal{F}=\{F\}$, then we write it as $\sat(n,F)$ for short. In this paper, we determine the exact value of $\sat(n,\{K_3,P_k\})$, and as its application, we obtain two bounds of $\sat(n,K_3\cup P_k)$ for $k\ge 10$ and sufficiently large $n$. Furthermore, $\sat(n,K_1\lor F)$ is determined, where $F$ is a linear forest without isolated vertices.
academic

Quelques résultats sur les graphes saturés minimaux

Informations fondamentales

  • ID de l'article: 2510.10458
  • Titre: Some results on minimum saturated graphs
  • Auteurs: Chenke Zhang, Qing Cui, Jinze Hu, Erfei Yue, Shengjin Ji
  • Classification: math.CO (Mathématiques combinatoires)
  • Date de publication: 12 octobre 2025 (prépublication arXiv)
  • Lien de l'article: https://arxiv.org/abs/2510.10458

Résumé

Cet article étudie le problème du nombre de saturation des graphes. Pour un graphe GG et une famille de graphes F\mathcal{F}, on dit que GG est F\mathcal{F}-saturé si GG ne contient aucun membre de F\mathcal{F} et si, pour toute arête e∈E(G‾)e \in E(\overline{G}), le graphe G+eG+e crée une copie d'un membre de F\mathcal{F}. Le nombre de saturation de F\mathcal{F} est défini comme le nombre minimum d'arêtes d'un graphe F\mathcal{F}-saturé ayant nn sommets, noté sat(n,F)\text{sat}(n,\mathcal{F}). Cet article détermine la valeur exacte de sat(n,{K3,Pk})\text{sat}(n,\{K_3,P_k\}) et applique ce résultat pour obtenir deux bornes de sat(n,K3∪Pk)\text{sat}(n,K_3 \cup P_k) lorsque k≥10k \geq 10 et nn est suffisamment grand. De plus, on détermine sat(n,K1∨F)\text{sat}(n,K_1 \vee F), où FF est une forêt linéaire sans sommets isolés.

Contexte et motivation de la recherche

Contexte du problème

Le problème du nombre de saturation est une direction de recherche importante en théorie extrémale des graphes, initialement proposé par Erdős et ses collaborateurs en 1964. Le cœur du problème consiste à déterminer comment construire un graphe F\mathcal{F}-saturé ayant nn sommets avec un nombre minimum d'arêtes pour une famille donnée de sous-graphes interdits F\mathcal{F}.

Signification de la recherche

  1. Valeur théorique: Le problème du nombre de saturation relie la théorie extrémale des graphes et la théorie structurelle des graphes, offrant une nouvelle perspective pour comprendre la structure des graphes
  2. Perspectives d'application: Applications importantes dans la conception de réseaux et la théorie du codage
  3. Défis techniques: Pour les structures interdites composées (comme K3∪PkK_3 \cup P_k), les méthodes existantes peinent à donner des résultats exacts

Limitations des travaux existants

  • Le nombre de saturation pour des graphes interdits individuels a été largement étudié, mais la recherche sur le nombre de saturation pour les familles de graphes est relativement limitée
  • Le nombre de saturation de K3∪PkK_3 \cup P_k ne dispose que de résultats de majoration, manquant de valeurs exactes
  • L'influence de l'opération de jointure de graphes (comme l'opération join) sur le nombre de saturation manque d'étude systématique

Contributions principales

  1. Détermination de la valeur exacte de sat(n,{K3,Pk})\text{sat}(n,\{K_3,P_k\}): Pour k≥10k \geq 10 et n≥ak1n \geq a_k^1, on prouve que sat(n,{K3,Pk})=n−⌊n/ak1⌋\text{sat}(n,\{K_3,P_k\}) = n - \lfloor n/a_k^1 \rfloor
  2. Établissement de bornes serrées pour sat(n,K3∪Pk)\text{sat}(n,K_3 \cup P_k): On prouve que 2+sat(n,{K3,Pk})≤sat(n,K3∪Pk)≤6+sat(n,{K3,Pk})2 + \text{sat}(n,\{K_3,P_k\}) \leq \text{sat}(n,K_3 \cup P_k) \leq 6 + \text{sat}(n,\{K_3,P_k\})
  3. Résolution du problème du nombre de saturation pour les graphes join: On détermine complètement que sat(n,K1∨F)=(n−1)+sat(n−1,F)\text{sat}(n,K_1 \vee F) = (n-1) + \text{sat}(n-1,F), où FF est une forêt linéaire sans sommets isolés
  4. Introduction d'une nouvelle méthode d'analyse de structures graphiques: Par le concept de « couches », on analyse systématiquement la structure des arbres {K3,Pk}\{K_3,P_k\}-saturés

Explication détaillée des méthodes

Définition de la tâche

Étant donné un entier positif nn et une famille de graphes F\mathcal{F}, trouver le nombre minimum d'arêtes sat(n,F)\text{sat}(n,\mathcal{F}) d'un graphe F\mathcal{F}-saturé ayant nn sommets, et caractériser tous les graphes extrémaux atteignant ce minimum.

Méthodes techniques principales

1. Analyse de la structure en couches

Définition: Pour un arbre TT de diamètre s≥2s \geq 2, soit Ps+1=v1v2⋯vs+1P_{s+1} = v_1v_2\cdots v_{s+1} son plus long chemin. On définit:

  • Couche 1: contient un ou deux sommets au centre
  • Couche ii: ensemble des sommets à distance i−1i-1 de la couche 1

Structures d'arbres clés:

  • TkT_k: l'arbre classique PkP_k-saturé
  • Tk0T_k^0: nouvel arbre {K3,Pk}\{K_3,P_k\}-saturé introduit, contenant ⌈k−22⌉\lceil\frac{k-2}{2}\rceil couches
  • Tk1T_k^1: autre classe d'arbre {K3,Pk}\{K_3,P_k\}-saturé, contenant ⌊k2⌋\lfloor\frac{k}{2}\rfloor couches

2. Méthode de vérification de la saturation

Pour un arbre TT et toute paire de sommets non adjacents (u,v)(u,v), on prouve que T+uvT+uv contient K3K_3 ou PkP_k par la stratégie suivante:

Analyse par cas:

  • Si u,vu,v sont sur le même chemin et l(u)≥l(v)+3l(u) \geq l(v)+3, on construit un chemin de longueur au moins k−1k-1
  • Si u,vu,v sont sur des chemins différents, on trouve un sommet commun ww et on construit le chemin correspondant

Points d'innovation technique

1. Caractérisation des arbres saturés minimaux

Lemme 2.3: Pour k≥10k \geq 10, si TT est un arbre {K3,Pk}\{K_3,P_k\}-saturé et n'est pas une étoile, alors Tk0⊆TT_k^0 \subseteq T ou Tk1⊆TT_k^1 \subseteq T, et e(Tk0)>e(Tk1)e(T_k^0) > e(T_k^1).

2. Stratégie de séparation

En considérant séparément les contraintes d'interdiction de K3K_3 et PkP_k, on décompose habilement le problème composé en sous-problèmes plus faciles à traiter.

3. Preuve constructive

On construit des graphes spécifiques G0G_0 et H0H_0, prouvant qu'ils atteignent respectivement sat(n,{K3,Pk})\text{sat}(n,\{K_3,P_k\}) et les majorations correspondantes.

Résultats principaux

Théorème 1.1 (Nombre de saturation de {K3,Pk}\{K_3,P_k\})

Énoncé: Si n≥ak1n \geq a_k^1 et k≥10k \geq 10, alors sat(n,{K3,Pk})=n−⌊n/ak1⌋\text{sat}(n,\{K_3,P_k\}) = n - \lfloor n/a_k^1 \rfloor.

Schéma de preuve:

  1. On construit le graphe G0=G1∪G2∪⋯∪GtG_0 = G_1 \cup G_2 \cup \cdots \cup G_t, où G1G_1 est un arbre {K3,Pk}\{K_3,P_k\}-saturé et GiG_i est une copie de Tk1T_k^1
  2. On prouve que G0G_0 est {K3,Pk}\{K_3,P_k\}-saturé et possède n−⌊n/ak1⌋n - \lfloor n/a_k^1 \rfloor arêtes
  3. Par l'absurde, on prouve que tout graphe {K3,Pk}\{K_3,P_k\}-saturé possède au moins ce nombre d'arêtes

Théorème 1.2 (Bornes pour K3∪PkK_3 \cup P_k)

Énoncé: Pour k≥10k \geq 10 et nn suffisamment grand, 2+sat(n,{K3,Pk})≤sat(n,K3∪Pk)≤6+sat(n,{K3,Pk})2 + \text{sat}(n,\{K_3,P_k\}) \leq \text{sat}(n,K_3 \cup P_k) \leq 6 + \text{sat}(n,\{K_3,P_k\})

Points clés de la preuve:

  • Majoration: On construit le graphe H0H_0 contenant K4K_4 et plusieurs copies de Tk1T_k^1, prouvant qu'il est (K3∪Pk)(K_3 \cup P_k)-saturé
  • Minoration: On analyse la structure des graphes (K3∪Pk)(K_3 \cup P_k)-saturés, utilisant la connexité et les contraintes de degré

Théorème 1.3 (Nombre de saturation des graphes join)

Énoncé: Soit FF une forêt linéaire sans sommets isolés. Pour nn suffisamment grand, sat(n,K1∨F)=(n−1)+sat(n−1,F)\text{sat}(n,K_1 \vee F) = (n-1) + \text{sat}(n-1,F)

Stratégie de preuve:

  1. On prouve que tout graphe (K1∨F)(K_1 \vee F)-saturé a un diamètre de 2
  2. On analyse le degré maximum, prouvant l'existence d'un sommet central
  3. On utilise le Lemme 4.2 pour établir une correspondance avec les graphes FF-saturés

Analyse des détails techniques

Preuve des lemmes clés

Cœur de la preuve du Lemme 2.3:

  • Par les contraintes de diamètre, on détermine k−3≤s≤k−2k-3 \leq s \leq k-2
  • On discute par cas s=k−3s = k-3 et s=k−2s = k-2
  • On utilise les conditions de saturation pour déduire les contraintes de degré de l'arbre

Précision des constructions

Les graphes extrémaux construits dans l'article ne sont pas arbitraires, mais optimisés selon les principes suivants:

  1. Minimalité: Chaque composante est la solution minimale du problème correspondant
  2. Saturation: L'ajout de toute arête produit une structure interdite
  3. Modularité: Facilite le calcul et l'analyse

Vérification expérimentale et exemples

Cas de petits paramètres

Pour k≤9k \leq 9, l'article donne dans la Proposition 5.1 les arbres {K3,Pk}\{K_3,P_k\}-saturés minimaux correspondants:

  • k=5k = 5: T1T_1
  • k=6k = 6: T2T_2 ou T3T_3
  • 7≤k≤87 \leq k \leq 8: Tk0T_k^0
  • k=9k = 9: T91T_9^1 ou T90T_9^0

Illustrations

L'article fournit plusieurs figures (Figures 1-5) qui présentent clairement les diverses structures d'arbres, facilitant la compréhension des définitions abstraites.

Travaux connexes

Développement historique

  1. Erdős et al. (1964): Première introduction du concept de nombre de saturation, détermination de sat(n,Kp)\text{sat}(n,K_p)
  2. Kászonyi et Tuza (1986): Étude du nombre de saturation pour les étoiles, les chemins et autres graphes fondamentaux
  3. Travaux récents: Chen et al. étudient le nombre de saturation des forêts, Li et Xu étudient les graphes (K3∪Pk)(K_3 \cup P_k)-saturés connexes

Positionnement de la contribution de cet article

Cet article réalise des progrès importants dans les domaines suivants:

  • Première détermination exacte du nombre de saturation de {K3,Pk}\{K_3,P_k\}
  • Amélioration de la majoration du nombre de saturation de K3∪PkK_3 \cup P_k
  • Résolution systématique du problème du nombre de saturation pour les graphes join

Conclusions et discussion

Conclusions principales

  1. Résolution complète du problème du nombre de saturation de {K3,Pk}\{K_3,P_k\} pour k≥10k \geq 10
  2. Fourniture de bornes serrées pour le nombre de saturation de K3∪PkK_3 \cup P_k
  3. Établissement de lois générales concernant l'influence de l'opération join sur le nombre de saturation

Limitations

  1. Restrictions paramétriques: Les résultats principaux s'appliquent uniquement à k≥10k \geq 10
  2. Absence de valeurs exactes: Pour K3∪PkK_3 \cup P_k, on n'a pas encore donné de valeur exacte
  3. Complexité technique: Les cas de petits paramètres nécessitent un traitement séparé

Directions futures

L'article propose des problèmes ouverts importants: Problème 2: Pour k≥10k \geq 10, a-t-on sat(n,K3∪Pk)=6+sat(n,{K3,Pk})\text{sat}(n,K_3 \cup P_k) = 6 + \text{sat}(n,\{K_3,P_k\})?

Évaluation approfondie

Points forts

  1. Profondeur théorique: Introduction de la méthode d'analyse en couches, fournissant un nouvel outil pour l'étude de la structure des graphes saturés
  2. Innovation technique: Séparation habile des contraintes composées, simplification de problèmes complexes
  3. Complétude des résultats: Non seulement des résultats numériques, mais aussi caractérisation de tous les graphes extrémaux
  4. Rigueur de la preuve: Discussions par cas exhaustives, traitement technique raffiné

Insuffisances

  1. Manque d'uniformité: Différentes méthodes de traitement sont nécessaires pour différentes plages de paramètres
  2. Complexité computationnelle: Les expressions paramétriques des structures d'arbres sont relativement complexes
  3. Problèmes ouverts: La conjecture centrale (Problème 2) reste non résolue

Impact

  1. Valeur académique: Contribution importante au développement de la théorie du nombre de saturation
  2. Contribution méthodologique: La méthode d'analyse en couches peut s'appliquer à d'autres problèmes extrémaux
  3. Utilité pratique: Fourniture de support théorique pour l'optimisation de topologie de réseau et autres applications

Domaines d'application

Cette recherche s'applique à:

  • Recherche théorique en théorie extrémale des graphes
  • Optimisation de topologie de réseau
  • Problèmes de construction de graphes en théorie du codage
  • Problèmes de satisfaction de contraintes en optimisation combinatoire

Références bibliographiques

L'article cite 27 références connexes, couvrant le développement principal de la théorie du nombre de saturation, incluant:

  • Travaux fondateurs classiques (Erdős et al., Bollobás et al.)
  • Progrès importants récents (Chen et al., Hu et al.)
  • Méthodes techniques connexes (Cameron et Puleo et al.)

Évaluation globale: Ceci est un article de haute qualité en mathématiques combinatoires qui réalise des progrès substantiels dans la direction de recherche importante du nombre de saturation. Les méthodes techniques sont innovantes, les résultats possèdent une valeur théorique importante et jettent une bonne base pour les recherches ultérieures.