2-重自补图论(Ⅰ)——度序列特征

Self-complementary 2-multigraphs part Ⅰ: Degree sequences

研究了可2-重度序列的基本特征.获得了两个重要结果:(1) 一个2-重图序列是可2-重自补度序列的充要条件;(2) 一个非负整数序列是可2-重自补度序列的充要条件.

Let G be a 2 multigraph. The complement of G , denoted by G -, is the 2 multigraph in which V(G-=V(G) ; and for every pair of vertices u,v in G -, u and v are joined by i(0≤i≤2) edges if and only if u and v are joined by 2 i edges in G. G is called a self complementary 2 multigraph if G and G - are isomorphic. Let π =( d 1,d 2,…,d p)(p≥2) be a degree sequence of some 2 multigraph. Then π is a potentially 2 s.c. degree sequence if there is a self complementary 2 multigraph G with π(G)=π . In this series papers, the self coomplenentary 2 multigraphs are studies in detail because the fundamental graph of a self complementary digraph is a self complementary 2 multigraph. In part Ⅰ, the characteristics of degree sequences of self complementary 2 multigraphs are considered such as two sufficient and necessary conditions, and the construction of potentially self complementary 2 multi sequences .