兰州大学机构库 >数学与统计学院
(3,6)-富勒烯图与超立方图的匹配强迫和反强迫数
其他题名On the matching forcing and anti-forcing numbers of (3,6)-fullerenes and hypercubes
石玲娟
导师张和平
学位类别硕士
2015-06-01
关键词(3,6)-富勒烯图 n维超立方图 强迫数 反强迫数 强迫谱 反强迫谱 完美匹配
中文摘要图的强迫问题出现在各种子结构及相关应用问题中,如: 完美匹配,控制集和染色等。设M 是图G 的一个完美匹配。如果S ⊆ M 且G 的其它完美匹配都不包含S,那么S 叫做M 的一个强迫集,其最小强迫集的大小叫做M 的强迫数。如果S ⊆ E(G)\M 且G − S 有唯一完美匹配M,那么S 叫做M 的一个反强迫集,最小反强迫集的大小叫做M 的反强迫数。G 的所有完美匹配的强迫数的最小值叫做G 的强迫数,记为f(G)。 G 的所有完美匹配的反强迫数的最小值叫做G 的反强迫数,记为af(G)。G 的所有完美匹配的反强迫数的集合叫做G 的反强迫谱。 (3,6)-富勒烯图是一类连通三正则的平面图,它的每个面的边界是3-长圈或者6-长圈。本文主要研究(3,6)-富勒烯图的强迫数和反强迫数以及超立方图Qn 的反强迫谱。(3,6)-富勒烯图的连通度是2 或者3,依据连通度对(3,6)-富勒烯图G 进行分类讨论,本文证明了f(G) = 1 当且仅当G 的连通度是2 或者G 同构于K4。f(G) ≥ 2 当且仅当G 的连通度是3 且G 不同构于K4。进而证明了af(G) = 2当且仅当G 的连通度是2 或者G 同构于K4,af(G) ≥ 3 当且仅当G 的连通度是3 且G 不同构于K4。特别地,本文确定出所有反强迫数达到下界3 的(3,6)-富勒烯图。对n 维超立方图Qn,当n ≥ 3 时,我们找到了它的反强迫谱的一个子集,这个子集构成一个公差为 n − 2 的等差数列。特别地,本文表明了这样的子集构成3-维、4-维超立方图的反强迫谱。
英文摘要The forcing problem of a graph appears in a series of substructures and corresponding problems such as perfect matchings, dominating sets, coloring and so on. Let M be a perfect matching of a graph G. If S ⊆ M and S is not in any other perfect matchings of G, then S is called a forcing set of M. The cardinality of a smallest forcing set is called the forcing number of M. If S ⊆ E(G) \ M and G − S has a unique perfect matching, then S is called an anti- forcing set of M. The cardinality of a smallest anti-forcing set of M is called the anti-forcing number of M. The smallest value of the forcing numbers of all perfect matchings of G is called the forcing number of G, denoted by f(G). The smallest value of the anti-forcing numbers of all perfect matchings of G is called the anti-forcing number of G, denoted by af(G). The set of the anti-forcing numbers of all perfect matchings of G is called the anti- forcing spectrum of G. (3,6)-fullerene is a connected cubic plane graph whose faces are only triangles and hexagons. In this paper, we mainly considered the forcing number and the anti-forcing number of (3,6)-fullerenes, and the anti-forcing spectrum of Qn. A (3,6)-fullerene graph G has the same connectivity and edge-connectivity 2 or 3. Consequently, we distribute (3,6) -fullerene graph according to its connectivity and study it. For a (3,6)-fullerene graph G, we show that f(G) ≥ 2 if the connectivity of G is 3 and G is not isomorphic to K4, otherwise f(G) = 1. Then we obtain that af(G) = 2 if and only if the connectivity of G is 2 or G is isomorphic to K4, and af(G) ≥ 3 if and only if G has the connectivity 3 and G is not isomorphic to K4. Further, we determine all the (3,6)-fullerenes with anti-forcing number 3. Qn is a n-hypercube, for n ≥ 3, we find a subset of its anti-forcing spectrum, which consists of an arithmetic progression of tolerance n − 2. In particular, we proved that the anti-forcing spectrum of Q3 (Q4) exactly is this subset.
全文链接查看原文
授予单位兰州大学
授予地点兰州
语种中文
文献类型学位论文
条目标识符http://ir.lzu.edu.cn/handle/262010/225751
Collection数学与统计学院
Recommended Citation:
GB/T 7714
石玲娟. (3,6)-富勒烯图与超立方图的匹配强迫和反强迫数[D]. 兰州. 兰州大学,2015.
Files in This Item:
There are no files associated with this item.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Altmetrics Score
谷歌学术
谷歌学术Similar articles in Google Scholar
[石玲娟]'s Articles
百度学术
百度学术Similar articles in Google Scholar
[石玲娟]'s Articles
必应学术
必应学术Similar articles in Google Scholar
[石玲娟]'s Articles
Related Copyright Policies
Null
???item.sidebar.baidu.bookmark-share???
???jsp.display-item.all??? (0)
[???jsp.display-item.idea???]
???jsp.display-item.comment-text2???
Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.