The structure of zero-divisor semigroups with graph K n ○K 2

This paper determines all commutative zero divisor semigroups whose zero divisor graph is a complete graph (finite or infinite), or a complete graph (finite or infinite) with one additional end vertex, and gives formulas for the numbers of all such semigroups with n elements. The research of T. Wu is supported by the National Natural Science Foundation of China (Grant No. 10671122) and the Natural Science Foundation of Shanghai (Grant No. 06ZR14049).     

Some simple optimization techniques for self-organized public key management in mobile ad hoc networks

We consider some graph theoretical problems arising from security requirements in some communication networks. Basically one has to associate to each node of a directed graph G=(V,E) a partial subgraph of G. A solution consists hence of a collection of |V| subgraphs, subject to some packing constraints or connectivity requirements. We first describe the usual graph theoretical model and we review a known construction procedure for which we point out some basic properties. We then study in more details the case of complete graphs and show the existence of a solution with a guaranteed quality. Next, we study the performance of the construction procedure and we propose an additional construction. We attempt to characterize the cases in which either construction is preferable. In the last section, a tabu search approach is proposed and tested on a sample of numerical examples.     

On a Decomposition of Complete Graphs

It is shown, among other results, that for any prime power q, the complete graph on 1+q+q ²+q ³ vertices can be decomposed into a union of 1+q Siamese Strongly Regular Graphs S R G(1+q+q ²+q ³,q+q ²,q–1,q+1) sharing 1+q ² cliques of size 1+q. Acknowledgments.The authors are indebted to a referee for a very extensive report and for many suggestions which improved the presentation of the paper tremendously.AMS Subject Numbers: 05B05, 05B20, 05E30This work was completed while the first author was on sabbatical leave visiting Institute for studies in theoretical Physics and Mathematics, (IPM), in Tehran, Iran. Support and hospitality is appreciated. Supported by an NSERC operating grant.     

Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs

A locally connected spanning tree of a graph G is a spanning tree T of G such that the set of all neighbors of v in T induces a connected subgraph of G for every v∈V(G). The purpose of this paper is to give linear-time algorithms for finding locally connected spanning trees on strongly chordal graphs and proper circular-arc graphs, respectively.     

Cell rotation graphs of strongly connected orientations of plane graphs with an application

The cell rotation graph D(G) on the strongly connected orientations of a 2-edge-connected plane graph G is defined. It is shown that D(G) is a directed forest and every component is an in-tree with one root; if T is a component of D(G), the reversions of all orientations in T induce a component of D(G), denoted by T⁻, thus (T,T⁻) is called a pair of in-trees of D(G); G is Eulerian if and only if D(G) has an odd number of components (all Eulerian orientations of G induce the same component of D(G)); the width and height of T are equal to that of T⁻, respectively. Further it is shown that the pair of directed tree structures on the perfect matchings of a plane elementary bipartite graph G coincide with a pair of in-trees of D(G). Accordingly, such a pair of in-trees on the perfect matchings of any plane bipartite graph have the same width and height.     

On the Decomposition of Graphs into Complete Bipartite Graphs

In a complete bipartite decomposition π of a graph, we consider the number ϑ(v;π) of complete bipartite subgraphs incident with a vertex v. Let ϑ(G)= ϑ(v;π). In this paper the exact values of ϑ(G) for complete graphs and hypercubes and a sharp upper bound on ϑ(G) for planar graphs are provided, respectively. An open problem proposed by P.C. Fishburn and P.L. Hammer is solved as well.     

随机偏好连接图的中心极限定理

我们研究了一类具有随机顶点和边的随机连接图模型, 其中顶点的随机性由一个Poisson 点过程所决定, 边的随机性由一个概率连接函数所决定. 我们得到了带偏好的随机连接图模型的关于所有随机边的长度和的一个中心极限定理.     

On risk processes with the Markov property and with independent increments

We study the influence on the underlying counting process of the Markov property and of the property of independent increments for a risk process.     

Some Remarks on the Graph Γ I (R)

Let R be a commutative ring with nonzero identity and Z(R) its set of zero-divisors. The zero-divisor graph of R is Γ(R), with vertices Z(R)?{0} and distinct vertices x and y are adjacent if and only if xy = 0. For a proper ideal I of R, the ideal-based zero-divisor graph of R is Γ _I (R), with vertices {x ∈ R?I | xy ∈ I for some y ∈ R?I} and distinct vertices x and y are adjacent if and only if xy ∈ I. In this article, we study the relationship between the two graphs Γ(R) and Γ _I (R). We also determine when Γ _I (R) is either a complete graph or a complete bipartite graph and investigate when Γ _I (R) ? Γ(S) for some commutative ring S.     

Blockers and transversals

Given an undirected graph G=(V,E) with matching number ν(G), we define d-blockers as subsets of edges B such that ν((V,E?B))≤ν(G)−d. We define d-transversals T as subsets of edges such that every maximum matching M has |M∩T|≥d. We explore connections between d-blockers and d-transversals. Special classes of graphs are examined which include complete graphs, regular bipartite graphs, chains and cycles and we construct minimum d-transversals and d-blockers in these special graphs. We also study the complexity status of finding minimum transversals and blockers in arbitrary graphs.     

极小拟(k+1)连通图的最小度

给出了极小拟5连通图有围长大于或等于4的极小拟（k）＋1连通图的最小度。     

On bipartite distance-regular graphs with a strongly closed subgraph of diameter three

Let Γ denote a distance-regular graph with a strongly closed regular subgraph Y. Hosoya and Suzuki [R. Hosoya, H. Suzuki, Tight distance-regular graphs with respect to subsets, European J. Combin. 28 (2007) 61-74] showed an inequality for the second largest and least eigenvalues of Γ in the case Y is of diameter 2. In this paper, we study the case when Γ is bipartite and Y is of diameter 3, and obtain an inequality for the second largest eigenvalue of Γ. Moreover, we characterize the distance-regular graphs with a completely regular strongly closed subgraph H(3,2).     

三正则连通图的Cordial性

用调整顶点标号的方法确定了3正则连通图的Cordial性．     

Two new sufficient conditions for Hamilton-connected graphs

ＴＷＯＮＥＷＳＵＦＦＩＣＩＥＮＴＣＯＮＤＩＴＩＯＮＳＦＯＲＨＡＭＩＬＴＯＮ－ＣＯＮＮＥＣＴＥＤＧＲＡＰＨＳＷＵＺＨＥＮＧＳＨＥＮＧ（吴正声）（ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ,ＮａｎｊｉｎｇＮｏｍａｌＵｎｉｖｅｒｓｉｔｙ,Ｎａｎｊｉｎｇ...