Graphic sequences with a realization containing intersecting cliques |
| |
Authors: | Jian Hua Yin Yan Fang Deng |
| |
Affiliation: | (1) Department of Mathematics, College of Information Science and Technology, Hainan University, Haikou, 570228, P. R. China |
| |
Abstract: | Let r ≥ 1, k ≥ 2 and Fm1 , ?mk ;rF_{m_1 , ldots m_k ;r} denote the most general definition of a friendship graph, that is, the graph of Kr + m1 , ?,Kr + mk K_{r + m_1 } , ldots ,K_{r + m_k } meeting in a common r set, where Kr + m1 K_{r + m_1 } is the complete graph on r + m i vertices. Clearly, | Fm1 , ?mk ;r | = m1 + ?+ mk + rleft| {F_{m_1 , ldots m_k ;r} } right| = m_1 + cdots + m_k + r. Let s( Fm1 , ?mk ;r ,n )sigma left( {F_{m_1 , ldots m_k ;r} ,n} right) be the smallest even integer such that every n-term graphic sequence π = (d 1, d 2, ..., d n ) with term sum s( p) = d1 + d2 + ?+ dn geqslant s( Fm1 , ?mk ;r ,n )sigma left( pi right) = d_1 + d_2 + cdots + d_n geqslant sigma left( {F_{m_1 , ldots m_k ;r} ,n} right), has a realization G containing Fm1 , ?mk ;rF_{m_1 , ldots m_k ;r} as a subgraph. In this paper, we determine s( Fm1 , ?mk ;r ,n )sigma left( {F_{m_1 , ldots m_k ;r} ,n} right) for n sufficiently large. |
| |
Keywords: | Degree sequence potentially P-graphic sequence |
本文献已被 CNKI 维普 SpringerLink 等数据库收录! |
|