单圈与双圈图的平均最小独立数-数学专业毕业论文.pdfVIP

Ⅺj908999 硕士哥l究生学位论文 新疆太学 论文题目(中文)：单圈与双圈图的平均最小独立数 论文题目(外文)： 0the numberin ic independenceunicycl and ic bicyclgraphs 研究生姓名：张利萍 学科、专业：应用数学 研究方 向：图论及其应用 导师姓名职称：吴宝音都仍教授 论文答辩日期 年月 日 学位授予日期 年月 日 摘要 摘要 对于图G=(KE)的一个点”，G的平均最小独立数{。。(G)被定义为 Ⅳ南∑。。y(G)屯(G)，其中i”(G)是包含”的极大独立集所古的最少点数．i(G) 被定义为G的一个极大独立集所含的最少点数．7(G)为G的控制集所 含的最少点数，对任一个点口∈y(G)，G的匹配数口(G)被定义为G中 最大匹配所含的边数，风(G)为图G—g[v]中最大匹配所含的边数．所以 风(G)=卢(G一Ⅳp1)． with dominationand domination equal Henning(Treesaverage independent numbers，Ars et lower and 树r，i∞(T)s a1．(Onaverageindependence B一2+：．Bfidia in dominationnumbers Mathematics graphs，Discrete295(2005)1-11)证明了 对于任意n个点m条边的图G， ‰(G)≤n一警一：∑风(G)． 口∈V‘“J 受到这些结果的启发，我们给出了单圈和双圈图平均最小独立数的上界． 我们的主要结论是： (1)设G是一个顶点数n≥5的单圈图，则 t。(G)S礼一3+兰， 等号成立当且仅当G是一个通过连接个顶点星图sn的两个一度点得到的 图． ， (2)设G是一个顶点数n≥6的双圈图，则 i。。(G)扎一3+兰． 关键词：平均最低独立数；独立控制集；单圈图；双圉图 Abstract 2 Abstract Gisdefined theminimum ‰(G)of io(v)，wherei。(G)is cardinality as丽1∑veV as ofamaximal setthat Gisdefinedthe