一个关于余直径的度条件

本文研究关于余直径的度条件,主要结果是,若G是3-连通图,其顶点集为V(G)={v1,v2,…,vn),其度序列为: d(v1)≤d(v2)≤…≤d(vn)则对G的任意一条边e都存在特征点对va,vb,使G中过e的最长圈至少为d(va)+d(vb)-1.在相同的条件下我们有d*(G)≥ m-2,     

无向环网的一个组合问题

本文利用[3]提供的方法,研究无向环网,导出了一般无向环网G(N;±s_1,±s_2)的直径的估值和计算方法。     

曲面上图的短圈结构与Mohar和Thomassen的一个问题的解决

研究了(赋权)图的圈基结构并且对包含在最小圈基中的短圈提供了大量信息. 建立了一个基变换的Hall型定理, 利用此定理, 给出了判断一个圈基是最小圈基的充分必要条件, 而且,证明了一个(赋权)图的最小圈基结构是唯一的. 这一性质对于最大圈基也成立 (尽管在最小圈基方面已有很多工作, 而在最大圈基方面的工作几乎没有). 利用这些方法, 发现了(赋权)图中具有特定性质的短圈的一些新结果. 作为应用, 决定了一个嵌入图的短圈的结构, 并找到一个多项式算法能够判断一个嵌入图中是否存在双侧圈, 如果这样的圈存在, 就可以找到一个最短的双侧圈. 这回答了B. Mohar和C. Thomassen提出的一个未解决问题, 并对他们提出的另一个未解决问题给出了部分解答.     

Star网络S_5的Hamilton圈分解

最近Star网络和Pancake网络作为超立方体(并行计算机中多处理机互连的一种著名拓扑结构)的替代品而被许多作者研究.这两种网络的一个好的特点是:与超立方体相比较,它们有较小的直径和顶点度.尤其Star网络,更是受到研究人员的极大关注.在本文中:(a)我们提出了一种在这两种网络中找Hamilton圈的新方法.(b)证明了关于Star网络S_n的一个猜想在n=5时是正确的,即给出了S_5的两个边不交的Hamilton圈,且S_5是这两个Hamilton圈的并.     

关于轮网络的一簇猜想

轮网络是由Cayley图模型设计出来的一种新型互连网络模型.星网络、冒泡排序网络、修正冒泡排序网络可嵌入轮网络.为了揭示它的整体结构,对轮网络提出如下一簇猜想:轮网络是边不交的i个Hamilton圈及2(n-i)-2个完美匹配的并,其中1≤i≤(n-1);并证明了当n=4,5,6,1≤i≤3时,猜想成立.     

一类新的交错群Cayley网络

本文利用交错群的Ｃａｙｌｅｙ图构作了一类互连网络,进而讨论了它的直径,容错度,容错直径和Ｈａｍｉｌｔｏｎ连通性,这些性质表明它优于利用交错群构作的网络ＡＧｎ,且相似于著名的星形网络。     

修正冒泡排序网络的边偶泛圈性

对于一个二部图G,如果在G中存在任意长为偶数l(4≤l≤|V(G)|)的圈,则称这个二部图G是偶泛圈的:如果对G中任意一边e,在G中存在任意长为偶数l(4≤l≤|V(G)|)且包含e的圈,则称这个二部图G是边偶泛圈的.修正冒泡排序网络是互连网络中的一个重要的Cayley图模型.在此,证明了对任意的自然数n,当n≥3时,修正冒泡排序网络Y_n是偶泛圈的,同时也是边偶泛圈的.     

一个复杂网络中完全子图的搜索算法

现实中很多复杂网络是由完全子图通过公共的节点连接而成的．本文提出了一个复杂网络中完全子图的搜索算法,并通过实例说明了所提算法的有效性．     

线图泛圈性的一个充分条件

本文证明了如果Ｇ是２连通线图,Ｇ不是圈,ｎ＝｜Ｖ（Ｇ）｜≥９且Ｇ的每个同构于Ａ的导出子图都满足（ａ１,ａ２）,则Ｇ是泛圈图     

二分图中关于Enomoto问题的结果

设k,n1和n2是3个正整数,G=（V1,V2;E）是一个二分图,使得｜V1｜=n1,｜V2｜=n2,其中n1≥2k＋1,n2≥2k＋1并且n1-n2≤1．如果对任意不相邻的x∈V1和y∈V2,都有d（x）＋d（y）≥2k＋2,则G包含k个相互独立的圈．以上结果部分地回答了Enomoto提出的关于二分图有独立圈的问题．     

On the characterization of the domination of a diameter-constrained network reliability model

Let G=(V,E) be a digraph with a distinguished set of terminal vertices K⊆V and a vertex s∈K. We define the s,K-diameter of G as the maximum distance between s and any of the vertices of K. If the arcs fail randomly and independently with known probabilities (vertices are always operational), the diameter-constrained s,K-terminal reliability of G, R_s,K(G,D), is defined as the probability that surviving arcs span a subgraph whose s,K-diameter does not exceed D.The diameter-constrained network reliability is a special case of coherent system models, where the domination invariant has played an important role, both theoretically and for developing algorithms for reliability computation. In this work, we completely characterize the domination of diameter-constrained network models, giving a simple rule for computing its value: if the digraph either has an irrelevant arc, includes a directed cycle or includes a dipath from s to a node in K longer than D, its domination is 0; otherwise, its domination is -1 to the power |E|-|V|+1. In particular this characterization yields the classical source-to-K-terminal reliability domination obtained by Satyanarayana.Based on these theoretical results, we present an algorithm for computing the reliability.     

On the Hamilton-Waterloo Problem

 The Hamilton-Waterloo problem asks for a 2-factorisation of K _v in which r of the 2-factors consist of cycles of lengths a ₁,a ₂,…,a _t and the remaining s 2-factors consist of cycles of lengths b ₁,b ₂,…,b _u (where necessarily ∑ _i=1 ^t a _i =∑ _j=1 ^u b _j =v). In this paper we consider the Hamilton-Waterloo problem in the case a _i =m, 1≤i≤t and b _j =n, 1≤j≤u. We obtain some general constructions, and apply these to obtain results for (m,n)∈{(4,6),(4,8),(4,16),(8,16),(3,5),(3,15),(5,15)}. Received: July 5, 2000     

The crossing numbers of join of the special graph on six vertices with path and cycle

There are only few results concerning crossing numbers of join of some graphs. In the paper, for the special graph H on six vertices we give the crossing numbers of its join with n isolated vertices as well as with the path P_n on n vertices and with the cycle C_n.     

Decomposition of complete equipartite graphs into paths and cycles of length 2p

Let $P_k$ and $C_k$ respectively denote a path and a cycle on k vertices. In this paper, we give necessary and sufficient conditions for the existence of a complete $\{P_{2p+1},C_{2p}\}$-decomposition of even regular complete equipartite graphs for all prime p.     

The Ordered Gradual Covering Location Problem on a Network

In this paper we develop a network location model that combines the characteristics of ordered median and gradual cover models resulting in the Ordered Gradual Covering Location Problem (OGCLP). The Gradual Cover Location Problem (GCLP) was specifically designed to extend the basic cover objective to capture sensitivity with respect to absolute travel distance. The Ordered Median Location problem is a generalization of most of the classical locations problems like p-median or p-center problems. The OGCLP model provides a unifying structure for the standard location models and allows us to develop objectives sensitive to both relative and absolute customer-to-facility distances. We derive Finite Dominating Sets (FDS) for the one facility case of the OGCLP. Moreover, we present efficient algorithms for determining the FDS and also discuss the conditional case where a certain number of facilities is already assumed to exist and one new facility is to be added. For the multi-facility case we are able to identify a finite set of potential facility locations a priori, which essentially converts the network location model into its discrete counterpart. For the multi-facility discrete OGCLP we discuss several Integer Programming formulations and give computational results.     

Packing cycles in complete graphs

We introduce a new technique for packing pairwise edge-disjoint cycles of specified lengths in complete graphs and use it to prove several results. Firstly, we prove the existence of dense packings of the complete graph with pairwise edge-disjoint cycles of arbitrary specified lengths. We then use this result to prove the existence of decompositions of the complete graph of odd order into pairwise edge-disjoint cycles for a large family of lists of specified cycle lengths. Finally, we construct new maximum packings of the complete graph with pairwise edge-disjoint cycles of uniform length.     

An asymptotic solution to the cycle decomposition problem for complete graphs

Let m₁,m₂,…,mt be a list of integers. It is shown that there exists an integer N such that for all n?N, the complete graph of order n can be decomposed into edge-disjoint cycles of lengths m₁,m₂,…,mt if and only if n is odd, 3?mi?n for i=1,2,…,t, and . In 1981, Alspach conjectured that this result holds for all n, and that a corresponding result also holds for decompositions of complete graphs of even order into cycles and a perfect matching.     

An algorithm for the numbers of endomorphisms on paths (DM13208)

An endomorphism of a graph is a mapping on the vertex set of the graph which preserves edges. In this paper we provide an algorithm to determine the cardinalities of endomorphism monoids of finite undirected paths.     

Disjoint triangles and quadrilaterals in a graph

Let G be a simple graph of order n and s and k be two positive integers. Brandt et al. obtained the following result: If s?k, n?3s+4(k-s) and σ₂(G)?n+s, then G contains k disjoint cycles C₁,…,C_k satisfying |C_i|=3 for 1?i?s and |C_i|?4 for s<i?k. In the above result, the length of C_i is not specified for s<i?k. We get a result specifying the length of C_i for each s<i?k if n?3s+4(k-s)+3.     

Metric inequalities and the Network Loading Problem

Given a simple graph G(V,E) and a set of traffic demands between the nodes of G, the Network Loading Problem consists of installing minimum cost integer capacities on the edges of G allowing routing of traffic demands.In this paper we study the Capacity Formulation of the Network Loading Problem, introducing the new class of Tight Metric Inequalities, that completely characterize the convex hull of the integer feasible solutions of the problem.We present separation algorithms for Tight Metric Inequalities and a cutting plane algorithm, reporting on computational experience.