Graphic Sequences with a Realization Containing a Union of Cliques |
| |
Authors: | Michael Ferrara |
| |
Institution: | (1) Department of Theoretical and Applied Mathematics, The University of Akron, Akron, OH, 44325 |
| |
Abstract: | An integer sequence π is said to be graphic if it is the degree sequence of some simple graph G. In this case we say that G is a realization of π. Given a graph H, and a graphic sequence π we say that π is potentially H-graphic if there is some realization of π that contains H as a subgraph. We define σ(H,n) to be the minimum even integer such that every graphic sequence with sum at least σ(H,n) is potentially H-graphic. In this paper, we determine σ(H,n) for the graph H = Km1∪ Km2∪...∪ Kmk when n is a sufficiently large integer. This is accomplished by determining σ(Kj + kK2,n) where j and k are arbitrary positive integers, and considering the case where j = m − 2k and m = ∑ mi. |
| |
Keywords: | Potentially H-graphic Degree sequence |
本文献已被 SpringerLink 等数据库收录! |
|