Mathematics – Combinatorics
Scientific paper
2012-03-20
Mathematics
Combinatorics
12 pages
Scientific paper
A sequence of nonnegative integers \pi =(d_1,d_2,...,d_n) is graphic if there is a (simple) graph G with degree sequence \pi. In this case, G is said to realize or be a realization of \pi. Degree sequence results in the literature generally fall into two classes: forcible problems, in which all realizations of a graphic sequence must have a given property, and potential problems, in which at least one realization of \pi must have the given property. Given a graph H, a graphic sequence \pi is potentially H-graphic if there is some realization of \pi that contains H as a subgraph. In 1991, Erd\H{o}s, Jacobson and Lehel posed the following question: Determine the minimum integer \sigma(H,n) such that every n-term graphic sequence with sum at least \sigma(H,n) is potentially H-graphic. As the sum of the terms of \pi is twice the number of edges in any realization of \pi, the Erd\H{o}s-Jacobson-Lehel problem can be viewed as a potential degree sequence relaxation of the (forcible) Tur\'{a}n problem, wherein one wishes to determine the maximum number of edges in a graph that contains no copy of H. While the exact value of \sigma(H,n) has been determined for a number of specific classes of graphs (including cliques, cycles, complete bigraphs and others), very little is known about the parameter for arbitrary H. In this paper, we determine \sigma(H,n) asymptotically for all H, thereby providing an Erd\H{o}s-Stone-Simonovits-type theorem for the Erd\H{o}s-Jacobson-Lehel problem.
Ferrara Michael
LeSaulnier Timothy D.
Moffatt Casey K.
Wenger Paul S.
No associations
LandOfFree
On the Sum Neccesary to Ensure that a Degree Sequence is Potentially H-Graphic does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On the Sum Neccesary to Ensure that a Degree Sequence is Potentially H-Graphic, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Sum Neccesary to Ensure that a Degree Sequence is Potentially H-Graphic will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-487742