On potentially 3-regular graph graphic sequences

Abstract

For given a graph H, a graphic sequence π = (d₁, d ₂, ⋯, d_n) is said to be potentially H-graphic if there exists a realization of π containing H as a subgraph. In this paper, we characterize the potentially H-graphic sequences where H denotes 3-regular graph with 6 vertices. In other words, we characterize the potentially K _3,3 and K₆ - C_6- graphic sequences where K _r,r is an r ×r complete bipartite graph. One of these characterizations implies a theorem due to Yin [25].