An extremal problem on potentially K<sub>p,1,1</sub>-graphic sequences - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Discrete Mathematics and Theoretical Computer Science Année : 2005

An extremal problem on potentially Kp,1,1-graphic sequences

Résumé

A sequence S is potentially K_p,1,1 graphical if it has a realization containing a K_p,1,1 as a subgraph, where K_p,1,1 is a complete 3-partite graph with partition sizes p,1,1. Let σ (K_p,1,1, n) denote the smallest degree sum such that every n-term graphical sequence S with σ (S)≥ σ (K_p,1,1, n) is potentially K_p,1,1 graphical. In this paper, we prove that σ (K_p,1,1, n)≥ 2[((p+1)(n-1)+2)/2] for n ≥ p+2. We conjecture that equality holds for n ≥ 2p+4. We prove that this conjecture is true for p = 3. AMS Subject Classifications: 05C07, 05C35
Fichier principal
Vignette du fichier
dm070107.pdf (64.67 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00959032 , version 1 (13-03-2014)

Licence

Paternité

Identifiants

Citer

Chunhui Lai. An extremal problem on potentially Kp,1,1-graphic sequences. Discrete Mathematics and Theoretical Computer Science, 2005, Vol. 7, pp.75-80. ⟨10.46298/dmtcs.357⟩. ⟨hal-00959032⟩

Collections

TDS-MACS
57 Consultations
751 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More