包含所有固定阶数2树作为子图的图的构造

曾德炎 翟冬阳

摘 要：图G是2树当且仅当G是一个3阶完全图，或者G中存在一个度为2的顶点v，使得与v相邻的两个顶点也相邻，且G-v也是一个2树。设G是一个k阶2树，其中k3，设k≡i（mod3），其中i=0，1，2。本文对i=0，1，2这三种情形，分别构造了三类图包含所有k个顶点的2树作为子图。

关键词：2树;完全图;子图

中图分类号：O157.5  文献标识码：A

Constructing graphs

to containing every 2tree as a subgraph with prescribed size

Zeng Deyan Zhai Dongyang

Institute of Technology， University of Sanya HainanSanya 572022

Abstract：A simple graph G is a 2tree if G is a complete graph on 3 vertices，or G has a vertex v of degree 2，whose neighbors are adjacent，and G-v is a 2tree.Let G be a 2tree on k vertices with k3 and k≡i（mod3） where i=0，1，2.In this paper，we construct three types of graph to containing every 2tree on k vertices as a subgraph based on i=0，1，2.

Keywords：2tree;complete graph;subgraph

一、绪论

我们用Km，Km，n和Pm分别表示顶点数为m的完全图，顶点数为m+n的m×n阶完全二部图和m个顶点的路。设v∈V（G），XV（G），我们用NX（v）表示顶点v在点集X中的所有邻点构成的集合。用G-v和G-X分别表示由顶点集V（G）/{v}和V（G）/X诱导的子图。用Km-E（H）表示在m阶完全图的基础上去掉图H所对应的边。文中未定义的标记参见文献[1]。

参考文献：

[1]J.A.Bondy，U.S.R.Murty，Graph Theory With Applications，The Macmillan Press，London，1976.

[2]Bose，P.，Dujmovic，V.，Krizanc，D.，et al.：A characterization of the degree sequences of 2trees.J.Graph Theory，2008，58，191209.

[3]Cai，L.Z.：On spanning 2trees in a graph.Discrete Appl.Math.，1997，74，203216.

基金項目：三亚学院科学研究项目“蕴含k树可图序列的极值问题”（编号USY18YSK061）

作者简介：曾德炎（1989— ），男，湖北荆州人，硕士，讲师，主要从事图论的研究;翟冬阳（1989— ），女，辽宁辽阳人，硕士，讲师。