曾德炎 翟冬陽(yáng)
摘?要:圖G是2樹(shù)當(dāng)且僅當(dāng)G是一個(gè)3階完全圖,或者G中存在一個(gè)度為2的頂點(diǎn)v,使得與v相鄰的兩個(gè)頂點(diǎn)也相鄰,且G-v也是一個(gè)2樹(shù)。設(shè)G是一個(gè)k階2樹(shù),其中k3,設(shè)k≡i(mod3),其中i=0,1,2。本文對(duì)i=0,1,2這三種情形,分別構(gòu)造了三類圖包含所有k個(gè)頂點(diǎn)的2樹(shù)作為子圖。
關(guān)鍵詞:2樹(shù);完全圖;子圖
中圖分類號(hào):O157.5??文獻(xiàn)標(biāo)識(shí)碼: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分別表示頂點(diǎn)數(shù)為m的完全圖,頂點(diǎn)數(shù)為m+n的m×n階完全二部圖和m個(gè)頂點(diǎn)的路。設(shè)v∈V(G),XV(G),我們用NX(v)表示頂點(diǎn)v在點(diǎn)集X中的所有鄰點(diǎn)構(gòu)成的集合。用G-v和G-X分別表示由頂點(diǎn)集V(G)/{v}和V(G)/X誘導(dǎo)的子圖。用Km-E(H)表示在m階完全圖的基礎(chǔ)上去掉圖H所對(duì)應(yīng)的邊。文中未定義的標(biāo)記參見(jiàn)文獻(xiàn)[1]。
參考文獻(xiàn):
[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.
基金項(xiàng)目:三亞學(xué)院科學(xué)研究項(xiàng)目“蘊(yùn)含k樹(shù)可圖序列的極值問(wèn)題”(編號(hào)USY18YSK061)
作者簡(jiǎn)介:曾德炎(1989—?),男,湖北荊州人,碩士,講師,主要從事圖論的研究;翟冬陽(yáng)(1989—?),女,遼寧遼陽(yáng)人,碩士,講師。