APP下载

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

2021-10-18曾德炎翟冬阳

科技风 2021年28期
关键词:顶点讲师分类号

曾德炎 翟冬阳

摘 要:图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— ),女,辽宁辽阳人,硕士,讲师。

猜你喜欢

顶点讲师分类号
Research on College Education Based on VR Technology
许珂作品
A Study of Chinese College Athletes’ English Learning
“图形的认识”复习专题
删繁就简三秋树
肥豆豆的一天
数学问答
一个人在顶点
“戈德堡今天没到”