图的圈和树孤立  

Isolation of Cycles and Trees in Graphs

作　　者：张刚 吴宝音都仍 ZHANG Gang;WU Baoyindureng(School of Mathematics and System Sciences,Xinjiang University,Urumqi Xinjiang 830017,China)

机构地区：[1]新疆大学数学与系统科学学院,新疆乌鲁木齐830017

出　　处：《新疆大学学报（自然科学版）（中英文）》2022年第2期169-175,共7页Journal of Xinjiang University(Natural Science Edition in Chinese and English)

基　　金：国家自然科学基金项目(12061073)。

摘　　要：对任一图G,如果顶点子集D使得G-N[D]不包含任何一个F中的F图作为子图,那么D被叫做图G的一个F孤立集,其中F是一个连通图集.图G中最小的一个F孤立集D的阶数被称为图G的F孤立数,记为ι(G,F).特别的,当F={C_(3),K_(1,3),P_(4)}时,定义ι(G,{C_(3),K_(1,3),P_(4)})=ι′c(G).于是,图G中任一{C_(3),K_(1,3),P_(4)}孤立集D使得G-N[D]只是一些K_(1),K_(2)和P_(3)分支,而ιc′(G)表示图G中最小的一个{C_(3),K_(1,3),P_(4)}孤立集D的阶数.本文证明了如果G?{C_(3),C_(7)}是一个顶点数为n的连通图,那么ι′c(G)≤n/4,且这个上界是最好的.A subset D⊆V(G)is called an F-isolating set of a graph G if G−N[D]contains no subgraph isomorphic to any F∈F,where F is a family of connected graphs.The F-isolation number of G,denoted byι(G,F),is the minimum cardinality of an F-isolating set in G.In this paper,take F={C_(3),K_(1,3),P_(4)}and denoteι(G,F)simply byι′c(G),which implies thatι′c(G)is the order of a smallest set D such that G−N[D]consists of some K_(1),K_(2) and P_(3) only.We prove that if G is a connected graph of order n and different from C_(3) or C_(7),thenι′c(G)≤n/4.

关 键 词：孤立数 圈 树 部分控制 

分 类 号：O157.5[理学—数学]