包含所有固定階數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—?），女，遼寧遼陽人，碩士，講師。