A characterization for a sequence to be potentially K r+1 − e-graphic
Tóm tắt
Let n ≥ r, let π = (d
1, d
2, ..., d
n
) be a non-increasing sequence of nonnegative integers and let K
r+1 − e be the graph obtained from K
r+1 by deleting one edge. If π has a realization G containing K
r+1 − e as a subgraph, then π is said to be potentially K
r+1 − e-graphic. In this paper, we give a characterization for a sequence π to be potentially K
r+1 − e-graphic.
Tài liệu tham khảo
Erdős, P., Gallai, T. Graphs with prescribed degrees of vertices. Mat. Lapok, 11: 264–274 (1960) (Hungarian)
Eschen, E., Niu, J.B. On potentially K 4 − e-graphic sequences. Australas. J. Combin., 29: 59–65 (2004)
Fulkerson, D.R., Hoffman, A.J., McAndrew, M.H. Some properties of graphs with multiple edges. Canad. J. Math., 17: 166–177 (1965)
Gould, R.J., Jacobson, M.S., Lehel, J. Potentially G-graphical degree sequences. In: Y. Alavi et al. (Eds.), Combinatorics, Graph Theory and Algorithms, Vol.1, New Issues Press, Kalamazoo Michigan, 1999, 451–460
Kézdy, A.E., Lehel, J. Degree sequences of graphs with prescribed clique size. In: Y. Alavi et al. (Eds.), Combinatorics, Graph Theory and Algorithms, Vol.2, New Issues Press, Kalamazoo Michigan, 1999, 535–544
Lai, C.H. Characterize the potentially K 4 − e-graphical sequences. J. Zhangzhou Teachers College, 15: 53–59 (2002)
Rao, A.R. The clique number of a graph with given degree sequence. In: Proc. Symposium on Graph Theory, A.R. Rao ed., MacMillan and Co. India Ltd., I.S.I. Lecture Notes Series, 4: 251–267 (1979)
Yin, J.H., Li, J.S. Two sufficient conditions for a graphic sequence to have a realization with prescribed clique size. Discrete Math., 301: 218–227 (2005)
Yin, M.X., Yin, J.H. On potentially H-graphic sequences. Czechoslovak Math. J., 57: 705–724 (2007)