On Graphs Having Maximal Independent Sets of Exactly t Distinct Cardinalities

For a given positive integer t we consider graphs having maximal independent sets of precisely t distinct cardinalities and restrict our attention to those that have no vertices of degree one. In the situation when t is four or larger and the length of the shortest cycle is at least 6t ? 6, we completely characterize such graphs.     

哈密尔顿性和部分平方图的独立集

设G是一个图,G的部分平方图G*满足V(G*)=V(G),E(G*)=E(G)∪{uv:uv■E(G),且J(u,v)≠■},这里J(u,v)={w∈N(u)∩N(v):N(w)■N[u]∪N[v]}.利用插点方法,证明了如下结果:设G是k-连通图(k2),b是整数,0min {k,(2b-1+k)/2}(n(Y)-1),则G是哈密尔顿图.同时给出图是1-哈密尔顿的和哈密尔顿连通的相关结果.     

Path Factors and Neighborhoods of Independent Sets in Graphs

A path-factor is a spanning subgraph F of G such that every component of F is a path with at least two vertices.Let k≥2 be an integer.A P_≥k-factor of G means a path factor in which each component is a path with at least k vertices.A graph G is a P_≥k-factor covered graph if for any e∈E(G),G has a P_≥k-factor including e.Let β be a real number with 1/3≤β≤1 and k be a positive integer.We verify that(ⅰ) a k-connected graph G of order n with n≥5k+2 has a P_≥3...     

Nonseparating Independent Sets and Maximum Genus of Graphs

Acta Mathematicae Applicatae Sinica, English Series - A subset I of vertices of an undirected connected graph G is a nonseparating independent set (NSIS) if no two vertices of I are adjacent and G...     

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

关于哈密尔顿连通图的一个基本结果是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也是独立集．     

门槛图与度极大图

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

A New Method for Enumerating Independent Sets of a Fixed Size in General Graphs

We develop a new method for enumerating independent sets of a fixed size in general graphs, and we use this method to show that a conjecture of Engbers and Galvin [7] holds for all but finitely many graphs. We also use our method to prove special cases of a conjecture of Kahn [13]. In addition, we show that our method is particularly useful for computing the number of independent sets of small sizes in general regular graphs and Moore graphs, and we argue that it can be used in many other cases when dealing with graphs that have numerous structural restrictions.     

On the Mean Distance in Scale Free Graphs

We consider a graph, where the nodes have a pre-described degree distribution F, and where nodes are randomly connected in accordance to their degree. Based on a recent result (R. van der Hofstad, G. Hooghiemstra and P. Van Mieghem, “Random graphs with finite variance degrees,” Random Structures and Algorithms, vol. 17(5) pp. 76–105, 2005), we improve the approximation of the mean distance between two randomly chosen nodes given by M. E. J. Newman, S. H. Strogatz, and D. J. Watts, “Random graphs with arbitrary degree distribution and their application,” Physical Review. E vol. 64, 026118, pp. 1–17, 2001. Our new expression for the mean distance involves the expectation of the logarithm of the limit of a super-critical branching process. We compare simulations of the mean distance with the results of Newman et al. and with our new approach. AMS 2000 Subject Classification: 05C80, 60F05     

强定向图的k-强距离

对强连通有向图D的一个非空顶点子集S,D中包含S的具有最少弧数的强连通有向子图称为S的Steiner子图,S的强Steiner距离d(S)等于S的Steiner子图的弧数. 如果|S|=k, 那么d(S)称为S的k-强距离. 对整数k≥2和强有向图D的顶点v,v的k-强离心率sek(v)为D中所有包含v的k个顶点的子集的k-强距离的最大值. D中顶点的最小k-强离心率称为D的k-强半径,记为sradk(D),最大k-强离心率称为D的k-强直径,记为sdiamk(D). 本文证明了,对于满足k+1≤r,d≤n的任意整数r,d,存在顶点数为n的强竞赛图T′和T″,使得sradk(T′)=r和sdiamk(T″)=d;进而给出了强定向图的k-强直径的一个上界.     

On the Independent Domination Number of Regular Graphs

A set S of vertices in a graph G is an independent dominating set of G if S is an independent set and every vertex not in S is adjacent to a vertex in S. In this paper, we consider questions about independent domination in regular graphs.     

On the Number of Independent Sets in Simple Hypergraphs

Extremal problems on the number of j-independent sets in uniform simple hypergraphs are studied. Nearly optimal results on the maximum number of independent sets for the class of simple regular hypergraphs and on the minimum number of independent sets for the class of simple hypergraphs with given average degree of vertices are obtained.     

关于图的直径和平均距离

图的直径和平均距离是度量网络有效性的两个重要参数．Ore通过图的顶点数和直径给出无向图的最大边数．Entringer，Jakson，Slater和Ng，Teh通过图的顶点数和边数分别给出无向图和有向图平均距离的下界．该文提供这两个结果的简单证明，给出有向图类似Ore的结果，并通过图的直径改进Entringer等人的结果到更一般的情形．结合本文和Ore的结果，可以得到一个无向图和有向图平均距离的下界，它比Plesnik得到的下界更好．     

Counting Independent Sets of a Fixed Size in Graphs with a Given Minimum Degree

Galvin showed that for all fixed δ and sufficiently large n, the n‐vertex graph with minimum degree δ that admits the most independent sets is the complete bipartite graph . He conjectured that except perhaps for some small values of t, the same graph yields the maximum count of independent sets of size t for each possible t. Evidence for this conjecture was recently provided by Alexander, Cutler, and Mink, who showed that for all triples with , no n‐vertex bipartite graph with minimum degree δ admits more independent sets of size t than . Here, we make further progress. We show that for all triples with and , no n‐vertex graph with minimum degree δ admits more independent sets of size t than , and we obtain the same conclusion for and . Our proofs lead us naturally to the study of an interesting family of critical graphs, namely those of minimum degree δ whose minimum degree drops on deletion of an edge or a vertex.     

双圈图的距离无符号拉普拉斯谱半径

连通图$G$的距离无符号拉普拉斯矩阵定义为$\mathcal{Q}(G)=Tr(G)+D(G)$, 其中$Tr(G)$和$D(G)$分别为连通图$G$的点传输矩阵和距离矩阵. 图$G$的距离无符号拉普拉斯矩阵的最大特征值称为$G$的距离无符号拉普拉斯谱半径. 本文确定了给定点数的双圈图中具有最大的距离无符号拉普拉斯谱半径的图.     

Distance Measures for Well-Distributed Sets

In this paper we investigate the Erdos/Falconer distance conjecture for a natural class of sets statistically, though not necessarily arithmetically, similar to a lattice. We prove a good upper bound for spherical means that have been classically used to study this problem. We conjecture that a majorant for the spherical means suffices to prove the distance conjecture(s) in this setting. For a class of non-Euclidean distances, we show that this generally cannot be achieved, at least in dimension two, by considering integer point distributions on convex curves and surfaces. In higher dimensions, we link this problem to the question about the existence of smooth well-curved hypersurfaces that support many integer points.