紧图的两个结果及其应用

双随机矩阵有许多重要的应用, 紧图族可以看作是组合矩阵论中关于双随机矩阵的著名的Birkhoff定理的拓广,具有重要的研究价值． 确定一个图是否紧图是个困难的问题,目前已知的紧图族尚且不多.给出了两个重要结果：任意紧图与任意多个孤立点的不交并是紧图;任意紧图的每一个顶点上各增加一条悬挂边的图是紧图． 利用这两个结果,从已知紧图可构造出无穷多个紧图族．     

有关完全图的图的紧性

双随机矩阵有许多重要的应用,紧图族可以看作是组合矩阵论中关于双随机矩阵的著名的Birkhoff定理的拓广,具有重要的研究价值.确定一个图是否紧图是个困难的问题,目前已知的紧图族尚且不多,给出了三个结果:任意多个完全图的不交并是紧图;圈C_3与圈C_n(n3)的不交并是非紧图;当n是大于等于3的奇数时,完全图K_n与图K_(n+1)的不交并是非紧图,其中图K_(n+1)是从完全图K_(n+1)删去一因子而得到的图.     

关于紧图的一些研究结果

双随机矩阵有许多重要的应用,紧图族可以看作是组合矩阵论中关于双随机矩阵的著名的Birkhoff定理的拓广,具有重要的研究价值.确定一个图是否紧图是个困难的问题,目前已知的紧图类尚且不多,介绍从某些已知的紧图出发不断构造紧图的加边法,可以构造无穷多个紧图族.     

完全超紧图

Chia G.L.和Lim C.K.在东南亚第一次图论会议(1983,新加坡)文集的末尾提出六个未解决问题.第五个问题是:设H是自补图,问是否存在自补完全超紧图G,使G~*=H.第六个问题是:设G是完全超紧图.如果G_0与(?)同构,问G是否自补图.本文肯定地回答了第五个问题和否定地回答了第六个问题.     

模糊数关于紧承下方图度量的线性性质

证明了紧承下方图度量不是平移不变的.对紧承下方图度量的代数运算的连续性进行了讨论.证明了关于紧承下方图度量,模糊数空间只能是嵌入到拓扑向量空间当中,但不嵌入赋范线性空间当中.并与关于上确界度量的结果进行了比较.最后,给出了一个紧承下方图度量的下界.     

下方图度量下的非紧模糊数空间

证明了非紧模糊数空间E^～在下方图度量下关于模糊数的序是可逼近的。本文给出的证明方法是构造性的，从而说明了模糊数值积分如M-积分和G-积分等是可计算的。最后给出了E^～中关于下方图度量的一些分析性质。     

诱导极限中的弱紧集

本文研究了诱导极限中的弱集与紧集，我们给出了诱导极限ｉｎｄｉｍ Ｅｎ中每个弱紧集含于且弱紧于某Ｅｎ的一些条件。     

几乎良紧集

在Ｌ－ｆｕｚｚｙ拓扑空间中提出了几乎良紧集的概念，研究了它的基本特征，讨论了它的性质，通过若干例揭示了几乎良紧性与其它一些Ｆｕｚｚｙ几乎紧性之间的联系。     

仿紧局部紧空间的序列覆盖L-映象

本文利用特定的覆盖性质,建立了仿紧局部紧空的序列覆盖L－映象和紧覆盖L－映象的特征,得到或深化了局部紧度量空间的一些相应结果。     

超序列紧fts,可数超紧fts和超列紧fts

文献[1]中定义了序列紧fts(每个不分明集序列有收敛的子序列)和可数紧fts(每个可数开覆盖存在有限子覆盖)。对于序列紧fts,得到“每个fts都是序列紧的”病态结果,由此可见这样定义的序列紧fts不是一般拓扑学中序列紧的良扩张。对于可数紧fts,[2]在评论F-紧性时,论证了凡T_1空间都不是F-紧空间,以上的论证也可得到凡T_1空间都不是可数紧fts的病态结果。我们还要指出,[1]定义的可数紧fts也不是一般拓扑学中可数紧的良扩张。     

On Compact Graphs

Let G be a finite simple graph with adjacency matrix A, and let P（A） be the convex closure of the set of all permutation matrices commuting with A. G is said to be compact if every doubly stochastic matrix which commutes with A is in P（A）. In this paper, we characterize 3-regular compact graphs and prove that if G is a connected regular compact graph, G - v is also compact, and give a family of almost regular compact connected graphs.     

Bubble-sort图和Modified Bubble-sort图的自同构群

Bubble-Sort图和Modified Bubble-Sort图是两类特殊的Cayley图,由于其在网络构建中的应用而受到广泛关注.本文完全确定了这两类图的自同构群.     

门槛图与度极大图

证明了门槛图与度极大图是一类图的两种不同说法,同时用图的对角限制极左矩阵刻画这一类图的结构。     

灯笼图的奇优美标号

提出了灯笼图、多向灯笼图、复杂灯笼图,研究了它们的奇优美性,证明灯笼图是二分奇优美图、超级边魔幻图和超级反魔幻图.     

三度边正则图的三个无限族

图X称为边正则图，若X的自同构群Aut(X)在X的边集上的作用是正则的．本文考察了三度边正则图与四度Cayley图的关系，给出了一个由四度Cayley图构造三度边正则图的方法，并且构造了边正则图的三个无限族．     

Cover-Incomparability Graphs of Posets

Cover-incomparability graphs (C-I graphs, for short) are introduced, whose edge-set is the union of edge-sets of the incomparability and the cover graph of a poset. Posets whose C-I graphs are chordal (resp. distance-hereditary, Ptolemaic) are characterized in terms of forbidden isometric subposets, and a general approach for studying C-I graphs is proposed. Several open problems are also stated.     

无向路图和块图上的混合控制

图G=(V,E)的一个混合控制集是一个满足如下条件的集合DV∪E:不在D中的每个点或每条边都相邻或关联于D中的至少一个点或一条边.确定图的最小基数的混合控制集的问题称为混合控制问题.本文研究混合控制问题的算法复杂性,证明了混合控制问题在无向路图上是NP-完全的,但在块图上有线性时间算法.无向路图和块图都是弦图的子类,又是树的母类.     

Equistarable Graphs and Counterexamples to Three Conjectures on Equistable Graphs

Equistable graphs are graphs admitting positive weights on vertices such that a subset of vertices is a maximal stable set if and only if it is of total weight 1. Strongly equistable graphs are graphs such that for every and every nonempty subset T of vertices that is not a maximal stable set, there exist positive vertex weights assigning weight 1 to every maximal stable set such that the total weight of T does not equal c . General partition graphs are the intersection graphs of set systems over a finite ground set U such that every maximal stable set of the graph corresponds to a partition of U . General partition graphs are exactly the graphs every edge of which is contained in a strong clique. In 1994, Mahadev, Peled, and Sun proved that every strongly equistable graph is equistable, and conjectured that the converse holds as well. In 2009, Orlin proved that every general partition graph is equistable, and conjectured that the converse holds as well. Orlin's conjecture, if true, would imply the conjecture due to Mahadev, Peled, and Sun. An “intermediate” conjecture, posed by Miklavi? and Milani? in 2011, states that every equistable graph has a strong clique. The above conjectures have been verified for several graph classes. We introduce the notion of equistarable graphs and based on it construct counterexamples to all three conjectures within the class of complements of line graphs of triangle‐free graphs. We also show that not all strongly equistable graphs are general partition.     

Partitioning Perfect Graphs into Stars

The partition of graphs into “nice” subgraphs is a central algorithmic problem with strong ties to matching theory. We study the partitioning of undirected graphs into same‐size stars, a problem known to be NP‐complete even for the case of stars on three vertices. We perform a thorough computational complexity study of the problem on subclasses of perfect graphs and identify several polynomial‐time solvable cases, for example, on interval graphs and bipartite permutation graphs, and also NP‐complete cases, for example, on grid graphs and chordal graphs.     

Precoloring Extension of Co-Meyniel Graphs

The pre-coloring extension problem consists, given a graph G and a set of nodes to which some colors are already assigned, in finding a coloring of G with the minimum number of colors which respects the pre-coloring assignment. This can be reduced to the usual coloring problem on a certain contracted graph. We prove that pre-coloring extension is polynomial for complements of Meyniel graphs. We answer a question of Hujter and Tuza by showing that “PrExt perfect” graphs are exactly the co-Meyniel graphs, which also generalizes results of Hujter and Tuza and of Hertz. Moreover we show that, given a co-Meyniel graph, the corresponding contracted graph belongs to a restricted class of perfect graphs (“co-Artemis” graphs, which are “co-perfectly contractile” graphs), whose perfectness is easier to establish than the strong perfect graph theorem. However, the polynomiality of our algorithm still depends on the ellipsoid method for coloring perfect graphs. C.N.R.S. Final version received: January, 2007