循环图和广义Petersen图的支配参数

代理获取

页面导航

目录
摘要
著录项
相似文献
相关主题

摘要

图的支配问题是近年来图论中一个比较活跃的研究领域，在网络设计中有许多实际应用。比如在一个通讯网络的一些节点上放置发射器，要求每个发射器的节点一定和某个发射器的节点有一个直接的通讯线路。如何选择节点使得放置的发射器的数目最小，就是一个支配数问题。计算图的支配数问题属于NP-完全问题，因此至今只有少数类图的支配数被找到并证明。支配集是指集合S(∈)V(G)，对任意的顶点v∈V(G)，都有v∈S或着v和某点w邻接，且w∈S.即，S是一个支配集当且仅当M[S]=V(G).如果支配集S的任何真子集都不是图G的支配集，则称支配集S为图G的一个极小支配集(minimal dominating set).如果对图G的任意的一个极小支配集S*，满足|S|≥|S|,则称极小支配集S为图G的一个最小支配集(minimum dominating set).最小支配集S中所含元素的个数称为图G的支配数(domination number)，记作γ(G). 独立集是指集合S(∈)V(G)，集合S内不包含两个邻接的顶点。对于任何点集，如果其真子集是S，那么其都不是独立的，那么称S为图G的极大独立集(independent set).如果对图G的任意一个极大独立集S*(maximal independent set)，满足|S*|≤|S|，则称极大独立集S为图G一个最大独立集(minimum independent set).最大独立集S中所含元素的个数称为图G的独立数(independence number)，记作α(G). 本文利用计算机求出n和k比较小的广义Petersen图的独立数和循环图的支配数，并构造出相应的独立集和支配集，从中找出规律，推出n和k较大时的独立集和支配集，从而确定出循环图C(n；{1，k})，n=3k,4k的支配数上确界和广义Petersen图P(n,k),k=1，2，3,5的独立数的下确界。本文利用计算得的结果，并严格证明了循环图C(n;{1，k})，n=3k，4k的支配数的下确界和广义Petersen图P(n，k)，k=1，2，3，5的独立数的上确界，从而得出了两者的准确值。

著录项

作者
田旌熙;
展开▼
作者单位

大连理工大学;

展开▼
授予单位大连理工大学;
学科软件工程
授予学位硕士
导师姓名杨元生;
年度 2008
页码
总页数
原文格式 PDF
正文语种中文
中图分类图论;
关键词
图论; 循环图; 广义Petersen图; 支配参数;

相似文献

中文文献
外文文献
专利

1. 广义Petersen图P(n,1)和P(n,2)的意大利控制数 [J] . 高红 ,黄佳欢 ,尹亚男 . 同济大学学报（自然科学版） . 2021,第005期
2. 一种基于广义Petersen图的互联网络拓扑结构研究 [J] . 李文升 ,岳孟田 ,李同胜 . 山西大同大学学报（自然科学版） . 2020,第005期
3. 双广义Petersen图的可靠性分析 [J] . 马胜栋 ,孟吉翔 . 新疆大学学报（自然科学版） . 2018,第002期
4. 广义Petersen图P (3n, n) 的强边染色 [J] . 谭亚茹 ,马登举 ,董晓媛 . 南通大学学报（自然科学版） . 2018,第003期
5. 广义Petersen图的控制数(n=3k) [J] . 龙艳 . 南京师大学报（自然科学版） . 2016,第002期
6. 循环图与回的乘积图的研究 [C] . 周永生 . 中国运筹学会第五届大会 . 1996
7. 广义Petersen图和循环图的罗马支配研究 [A] . 吉春年 . 2008

循环图和广义Petersen图的支配参数

目录

摘要

著录项

相似文献

相关主题

期刊订阅