2012/03/20 by Michael Ferrara, Ferrara, Michael, Timothy D. LeSaulnier +6 · 1 citation
Computer Science · Engineering · Mathematics · #05C07 #Combinatorics (math.CO) #Digital Image Processing Techniques #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1203.4611
openalex publication_date 2012/03/20 · openalex created_date 2022/10/04 · openalex updated_date 2026/07/28
A sequence of nonnegative integers \π =(d1,d2,...,dn) is graphic if there\nis a (simple) graph G with degree sequence \π. In this case, G is said to\nrealize or be a realization of \π. Degree sequence results in the literature\ngenerally fall into two classes: forcible problems, in which all realizations\nof a graphic sequence must have a given property, and potential problems, in\nwhich at least one realization of \π must have the given property.\n Given a graph H, a graphic sequence \π is potentially H-graphic if there is\nsome realization of \π that contains H as a subgraph. In 1991, Erd Hos,\nJacobson and Lehel posed the following question: Determine the minimum integer\n\σ(H,n) such that every n-term graphic sequence with sum at least\n\σ(H,n) is potentially H-graphic. As the sum of the terms of \π is twice\nthe number of edges in any realization of \π, the Erd Hos-Jacobson-Lehel\nproblem can be viewed as a potential degree sequence relaxation of the\n(forcible) Tur 'an problem, wherein one wishes to determine the maximum\nnumber of edges in a graph that contains no copy of H.\n While the exact value of \σ(H,n) has been determined for a number of\nspecific classes of graphs (including cliques, cycles, complete bigraphs and\nothers), very little is known about the parameter for arbitrary H. In this\npaper, we determine \σ(H,n) asymptotically for all H, thereby providing an\nErd Hos-Stone-Simonovits-type theorem for the Erd Hos-Jacobson-Lehel\nproblem.\n