摘要
设 G 是一个简单无向图.V(G),E(G)分别表示 G 的顶点集和边集.(?)表示 G 的补图.我们以 S_(?) 表示 n+1阶星图 k_(1,n-1).称 G 是(p,p—k)图,如果|E(G)|=|V(G)|—k.称|V(G)|为图 G 的阶.设 G_1,G_2是同阶图,(?)_1是 V(G_1)到 V(G_2)的一个双射,(?)_2是 V(G_2)上的一个置换,我们用(?)_2(?)_1表示 V(G_1)到 V(G_2)的双射。
ABSIRACILet G be a given simple undirected graph.We denote the sets of its verticesand edges by V(G) and E(G) respectively.G is called a (p,p-k) graph if |E(G)|=|V(G)|-k.Let {G_1,G_2}be a pair of graphs with the same order If G_1 is iso-morphic to a subgraph of (?)_2,where (?)_2 is the complement of G_2,we call the pairof graphs {G_1,G_2} packable.In this paper,we obtain a necessary and sufficientcondition for {G_1,G_2} to be packable,where |V(G_1)|≥8,G_1 is a triangle-free (p,p-1) graph and G_2 is an arbitrary (p,p) graph.Thus,we can easily answer P.J.Slater's two packing problems.
出处
《系统科学与数学》
CSCD
北大核心
1989年第2期133-137,共5页
Journal of Systems Science and Mathematical Sciences
