论简单图所含k阶i爪独立集个数的可重构性

设犐是图犌的一个含有犽个点的独立集（简称犽独立集）．如果犐不是犌的其它任何独立集的真子集,则称犐为犌的一个极大独立集．犌中所含的极大犽独立集的个数记为犿（犵犽,犌）．设犵犽是图犌的任一个犽独立集,如果存在｛狏１,狏２,…,狏犻｝犞（犌）－犵犽,犻≥１,使得（１）对任意犼∈ ｛１,２,…,犻｝,犵犽＋｛狏犼｝的都是犌的（犽＋１） 独立集;（２）对任意狌∈犞（犌）－犵犽－｛狏１,狏２,…,狏犻｝,犵犽＋｛狌｝的都不是犌的独立集;则称犵犽为犌的一个犻爪犽独立集,犌所含的犻爪犽独立集的个数记为犿犻（犵犽,犌）．该文证明了对简单图犌,犿犻（犵犽,犌）和犿（犵犽,犌）都是可重构的．另外,用同样的方法可以证明犌中的极大犽团的个数及犻爪犽团的个数也是可重构的．     

高度图的独立集复形

给定图G，称以G的所有独立集为单形的抽象复形I（G）为G的独立集复形．如果两个图G和H的独立集复形I（G）和I（H）的各阶同调群都是同构的，则称两个图是独立同调的．J（G）表示Gc的连通分支数，J3K2（G）表示Gc中同构于（3H2）c的连通分支数．本文研究了最小次δ（G）至少为其阶数|V（G）|减5的图G的独立集复形的结构，对满足δ（G）≥|V（C）|5，δ（H）≥|V（H）|－5的两个图G和H，（I）证明了，G和H独立同调的充要条件为J（G）＝J（H），J3K2（G）＝J3K2（H），且I（G）和I（H）的Euler示性数相同．（Ⅱ）给出了一个在图上计算I（G）的一维Betti数的方法，得到了一个I（G）是无圈复形的充要条件     

渺位六角系统完美匹配Z——变换图

六角系统是2-连通的平面图，其每个内部面都是单位正六边形．六角系统的完美匹配是化学中苯类芳烃体系的Kekule结构．一个六角系统H完美匹配Z—变换图Z（H）是一个图，它的顶点集是H的完匹配集，两个匹配相邻当且仅当它们的对称差是一个单位正六边形．本文用乘积图刻划了沙位六角系统Z—变换图的结构．     

����״̬������Markov�л����ʱ��ϵͳ�ľ���ָ���ȶ���

考察一类Markov切换时变时滞随机系统的均方指数稳定性. 利用基于Liapunov函数和线性矩阵不等式的方法, 给出了使状态反馈控制系统能克服不确定性和随机干扰, 在均方意义下达到指数稳定的充分条件. 当Markov链遍历所有模态时, 给出了一个独立于Markov链模态集的增益矩阵, 使得状态反馈控制系统均方指数稳定     

极大非独立集可削去的因子临界图

如果对一个简单图G的每一个与G的顶点数同奇偶的独立集I，都有G-I有完美匹配，则称G是独立集可削去的因子临界图．如果图G不是独立集可削去的因子临界图，而对任意两个小相邻的顶点x与y，G xy足独立集可削去的因子临界图，则称G足极大非独立集可削去的因子临界图，本刻画了极大非独立集可削去的因子临界图。     

拟阵中独立集个数的几个不等式

本文利用已建立的拟阵代数结构和面环的 Ｈｉｌｂｅｒｔ函数,给出了拟阵中独立集个数的几个不等式．     

铁磁链型的LANDAU-LIFSHITZ方程

本文研究Ｒｉｅｍａｎｎ曲面上的带有Ｇｉｌｂｅｒｔ阻尼项的铁磁链型方程．设Ｍ和Ｆ是两个闭Ｒｉｅｍａｎｎ曲面，那么对任一初值ｕ０∈Ｈ１，２（Ｍ；Ｆ），利用热方法及先验估计证明了在Ｍ×（０，∞）上存在唯一一个ＬａｎｄａｕＬｉｆｓｈｉｔｚ方程（１．５）的解，而且至多除了Ｍ×（０，∞）中的一个有限点集外，解是正则的．进一步，如果Ｆ的亏格不是零，解在Ｍ×（０，∞）上是正则的．     

具有二个焦点的二次系统极限环的分布与个数

本文证明了具有二个焦点的二次系统必在其中一个焦点外围至多有一个极限环这一猜想．从而得到具有二个焦点的二次系统之极限环必是（Ｏ,ｉ）或（１,ｉ）分布（ｉ＝ ０, １, ２,）．     

关于全图的强完美性

本文证明了图Ｇ的全图Ｔ（Ｇ）是完美的充分必要条件是Ｇ的块至多含有三个点．同时，得到对全图来说强完美性猜想为真．     

独立集的度和与图的哈密尔顿性

关于哈密尔顿连通图的一个基本结果是Ore给出的：设G是n阶图,若对于任意两个不相邻顶点u和v,有d(u) d(v)≥n 1,则G是哈密尔顿连通的．设G是一个图,对于任意u (?)V(G),令N(U)=∪_(u∈∪)N(u),d(U)=|N(U)|,称d(U)是U的度．本文利用独立集的度和得到如下结果：设s和t是正整数,G是(2s 2t 1)-连通n阶图．若对于任两个强不交独立集S,T,|S|=s,|T|=t,有d(S) d(T)≥n 1．则G是哈密尔顿连通的．同时也得到图的哈密尔顿性的其它相关结果．两个独立集S和T称为强不交的,如果S∪T也是独立集．     

Minimal hexagonal chains with respect to the Kirchhoff index

Let G be a connected graph. The resistance distance between any two vertices of G is equal to the effective resistance between them in the corresponding electrical network constructed from G by replacing each edge with a unit resistor. The Kirchhoff index of G is defined as the sum of resistance distances between all pairs of vertices. Hexagonal chains are graph representations of unbranched catacondensed benzenoid hydrocarbons. It was shown in Yang and Klein (2014) [30] that among all hexagonal chains with n hexagons, the linear chain $L_n$ is the unique chain with maximum Kirchhoff index. However, for hexagonal chains with minimum Kirchhoff index, it was only claimed that the minimum Kirchhoff index is attained only when the hexagonal chain is an “all–kink” chain. In this paper, by standard techniques of electrical networks and comparison results on Kirchhoff indices of $S,T$-isomers, “all-kink” chains with maximum and minimum Kirchhoff indices are characterized. As a consequence, hexagonal chains with minimum Kirchhoff indices are singled out.     

Extremal Hosoya index and Merrifield-Simmons index of hexagonal spiders

For any graph G, let m(G) and i(G) be the numbers of matchings (i.e., the Hosoya index) and the number of independent sets (i.e., the Merrifield-Simmons index) of G, respectively. In this paper, we show that the linear hexagonal spider and zig-zag hexagonal spider attain the extremal values of Hosoya index and Merrifield-Simmons index, respectively.     

On the distance spectral radius of some graphs

For a connected graph, the distance spectral radius is the largest eigenvalue of its distance matrix. In this paper, we determine the unique graph with minimum distance spectral radius among all connected graphs of order n with a given diameter. Moreover, we determine the unique graph with maximum distance spectral radius among the catacondensed hexagonal systems with h hexagons.     

Forcing faces in plane bipartite graphs

Let Ω denote the class of connected plane bipartite graphs with no pendant edges. A finite face s of a graph G∈Ω is said to be a forcing face of G if the subgraph of G obtained by deleting all vertices of s together with their incident edges has exactly one perfect matching. This is a natural generalization of the concept of forcing hexagons in a hexagonal system introduced in Che and Chen [Forcing hexagons in hexagonal systems, MATCH Commun. Math. Comput. Chem. 56 (3) (2006) 649-668]. We prove that any connected plane bipartite graph with a forcing face is elementary. We also show that for any integers n and k with n?4 and n?k?0, there exists a plane elementary bipartite graph such that exactly k of the n finite faces of G are forcing. We then give a shorter proof for a recent result that a connected cubic plane bipartite graph G has at least two disjoint M-resonant faces for any perfect matching M of G, which is a main theorem in the paper [S. Bau, M.A. Henning, Matching transformation graphs of cubic bipartite plane graphs, Discrete Math. 262 (2003) 27-36]. As a corollary, any connected cubic plane bipartite graph has no forcing faces. Using the tool of Z-transformation graphs developed by Zhang et al. [Z-transformation graphs of perfect matchings of hexagonal systems, Discrete Math. 72 (1988) 405-415; Plane elementary bipartite graphs, Discrete Appl. Math. 105 (2000) 291-311], we characterize the plane elementary bipartite graphs whose finite faces are all forcing. We also obtain a necessary and sufficient condition for a finite face in a plane elementary bipartite graph to be forcing, which enables us to investigate the relationship between the existence of a forcing edge and the existence of a forcing face in a plane elementary bipartite graph, and find out that the former implies the latter but not vice versa. Moreover, we characterize the plane bipartite graphs that can be turned to have all finite faces forcing by subdivisions.     

平面图的Alcuin数

广义渡河问题是一类重要的组合优化问题,它是经典的狼-羊-卷心菜游戏的推广。冲突图是一个图,这个图的任意两个点所代表的物品不相容时(例如,狼和羊代表的物品不相容),则在这两个点之间连结一条边。渡河覆盖问题的目的是确定冲突图全部点所代表的物品从河的一岸安全地摆渡到河的对岸时所需船的最小容量,而冲突图的Alcuin数定义这个最小容量。本文讨论了平面图的Alcuin数, 给出了该类图Alcuin数的完全刻画。     

Extremal double hexagonal chains with respect to k-matchings and k-independent sets

“Double hexagonal chains” can be considered as benzenoids constructed by successive fusions of successive naphthalenes along a zig-zag sequence of triples of edges as appear on opposite sides of each naphthalene unit. In this paper, we discuss the numbers of k-matchings and k-independent sets of double hexagonal chains, as well as Hosoya indices and Merrifield-Simmons indices, and obtain some extremal results: among all the double hexagonal chains with the same number of naphthalene units, (a) the double linear hexagonal chain has minimal k-matching number and maximal k-independent set number and (b) the double zig-zag hexagonal chain has maximal k-matching number and minimal k-independent set number, which are extensions to hexagonal chains [L. Zhang and F. Zhang, Extremal hexagonal chains concerning k-matchings and k-independent sets, J. Math. Chem. 27 (2000) 319-329].     

Fragile graphs with small independent cuts

A graph is called fragile if it has a vertex cut which is also an independent set. Chen and Yu proved that every graph with n vertices and at most 2n?4 edges is fragile, which was conjectured to be true by Caro. However, their proof does not give any information on the number of vertices in the independent cuts. The purpose of this paper is to investigate when a graph has a small independent cut. We show that if G is a graph on n vertices and at most (12n/7)?3 edges, then G contains an independent cut S with ∣S∣≤3. Upper bounds on the number of edges of a graph having an independent cut of size 1 or 2 are also obtained. We also show that for any positive integer k, there is a positive number ε such that there are infinitely many graphs G with n vertices and at most (2?ε)n edges, but G has no independent cut with less than k vertices. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 327–341, 2002     

Characterization of reducible hexagons and fast decomposition of elementary benzenoid graphs

A benzenoid graph is a finite connected plane graph with no cut vertices in which every interior region is bounded by a regular hexagon of a side length one. A benzenoid graph G is elementary if every edge belongs to a 1-factor of G. A hexagon h of an elementary benzenoid graph is reducible, if the removal of boundary edges and vertices of h results in an elementary benzenoid graph. We characterize the reducible hexagons of an elementary benzenoid graph. The characterization is the basis for an algorithm which finds the sequence of reducible hexagons that decompose a graph of this class in O(n²) time. Moreover, we present an algorithm which decomposes an elementary benzenoid graph with at most one pericondensed component in linear time.     

Estimates of the number of independent sets in graphs with a fixed independence number

Attainable estimates of the number of independent sets in graphs with a given size of the maximal independent set are obtained. Three graph classes—trees, forests, and the class of all graphs—are considered. Extremal graphs are described.     

A successful algorithm for solving directed Hamiltonian path problems

In this paper we present a graph-theoretic polynomial algorithm which has positive probability of finding a Hamiltonian path in a given graph, if there is one; if the algorithm fails, it can be rerun with a randomly chosen starting solution, and there is again a positive probability it will find an answer. If there is no Hamiltonian path, the algorithm will always terminate with failure. We call this a Successful Algorithm because it has high (close to 1) empirical probability of success and it works in polynomial time. Some basic theoretical results concerning spanning arborescences of a graph are given. The concept of a ramification index is defined and it is shown that ramification index of a Hamiltonian path is zero. The algorithm starts with finding any spanning arborescence and by suitable pivots it endeavors to reduce the ramification index to zero. Probabilistic properties of the algorithm are discussed. Computational experience with graphs up to 30 000 nodes is included.