Computing an Integer Point of a Class of Convex Sets

A simplicial algorithm is proposed for computing an integer point of a convex set ^CRn satisfying

A class of antimagic join graphs

A labeling f of a graph G is a bijection from its edge set E(G) to the set {1, 2, . . . , |E(G)|}, which is antimagic if for any distinct vertices x and y, the sum of the labels on edges incident to x is different from the sum of the labels on edges incident to y. A graph G is antimagic if G has an f which is antimagic. Hartsfield and Ringel conjectured in 1990 that every connected graph other than K 2 is antimagic. In this paper, we show that if G 1 is an n-vertex graph with minimum degree at least r, and G 2 is an m-vertex graph with maximum degree at most 2r-1 (m ≥ n), then G1 ∨ G2 is antimagic.     

Labeling the -path with a condition at distance two

For integer r≥2, the infinite r-path P_∞(r) is the graph on vertices …v₋₃,v₋₂,v₋₁,v₀,v₁,v₂,v₃… such that v_s is adjacent to v_t if and only if |s−t|≤r−1. The r-path on n vertices is the subgraph of P_∞(r) induced by vertices v₀,v₁,v₂,…,v_n−1. For non-negative reals x₁ and x₂, a λ_x1,x2-labeling of a simple graph G is an assignment of non-negative reals to the vertices of G such that adjacent vertices receive reals that differ by at least x₁, vertices at distance two receive reals that differ by at least x₂, and the absolute difference between the largest and smallest assigned reals is minimized. With λ_x1,x2(G) denoting that minimum difference, we derive λ_x1,x2(P_n(r)) for r≥3, 1≤n≤∞, and . For , we obtain upper bounds on λ_x1,x2(P_∞(r)) and use them to give λ_x1,x2(P_∞(r)) for r≥5 and . We also determine λ_x1,x2(P_∞(3)) and λ_x1,x2(P_∞(4)) for all .     

几类强协调图与非强协调图

证明了风车图K4n3(n∈自然数)及其它几类强协调图,并给出了统一的强协调值标号,最后证明了Kn-e(n≥6)是非强协调图.     

模糊最短路的一种算法

模糊最短路问题在许多领域有着广泛的应用,研究这一问题具有重要意义。根据多准则决策理论求非被支配路径集合,求最大效用模糊最短路以及利用模糊数排序方法求模糊最短路是常用的三种研究方法,本文利用OERI排序原理,使网络模糊边长具有线性可加性,对具有三角模糊数边权的网络给出了一种标号算法,该算法简单高效,且易于在计算机上实现,算法的时间复杂度为O(n^2)。     

有向图n·■_m的优美性

给定有向图D(V,E),如果存在一个单射f:V(D)→{0,1,…,|E|}使得对于每条有向边(u,v),诱导函数f′:E(D)→{1,2,…,|E|}是一个双射函数,其中,f′(u,v)=[f(v)-f(u)](mod(|E|+1)),则f称为有向图D(V,E)的优美标号,f′称为有向图D(V,E)的诱导的边的优美标号.本文讨论了有向图n.■m的优美性,并且证明了当m=23且n为偶数时,n.■m是优美有向图.     

Harmonious order of graphs

We consider the following generalization of the concept of harmonious graphs. Given a graph G=(V,E) and a positive integer t≥|E|, a function is called a t-harmonious labeling of G if is injective for t≥|V| or surjective for t<|V|, and for all distinct edges vw,xy∈E(G). Then the smallest possible t such that G has a t-harmonious labeling is named the harmonious order of G. We determine the harmonious order of some non-harmonious graphs, such as complete graphs K_n (n≥5), complete bipartite graphs K_m,n (m,n>1), even cycles C_n, some powers of paths , disjoint unions of triangles nK₃ (n even). We also present some general results concerning harmonious order of the Cartesian product of two given graphs or harmonious order of the disjoint union of copies of a given graph. Furthermore, we establish an upper bound for harmonious order of trees.     

截断切割问题的数学模型

本文就 1 997年全国大学生数学建模竞赛中 B题所给的截断切割问题建立了一个数学模型 ,并给出了求解的方法 .     

On L(d,1)-labelings of graphs

Given a graph G and a positive integer d, an L(d,1)-labeling of G is a function f that assigns to each vertex of G a non-negative integer such that if two vertices u and v are adjacent, then |f(u)−f(v)|d; if u and v are not adjacent but there is a two-edge path between them, then |f(u)−f(v)|1. The L(d,1)-number of G, λ_d(G), is defined as the minimum m such that there is an L(d,1)-labeling f of G with f(V){0,1,2,…,m}. Motivated by the channel assignment problem introduced by Hale (Proc. IEEE 68 (1980) 1497–1514), the L(2,1)-labeling and the L(1,1)-labeling (as d=2 and 1, respectively) have been studied extensively in the past decade. This article extends the study to all positive integers d. We prove that λ_d(G)Δ²+(d−1)Δ for any graph G with maximum degree Δ. Different lower and upper bounds of λ_d(G) for some families of graphs including trees and chordal graphs are presented. In particular, we show that the lower and the upper bounds for trees are both attainable, and the upper bound for chordal graphs can be improved for several subclasses of chordal graphs.     

龙图的奇优美性

根据复杂网络研究的需要,定义(k,m)-奇优美龙图和一致(k,m)-龙图作为复杂网络的模型.这些龙图的奇优美性得到研究,其中证明方法可算法化.