<i>L</i>(0, 1)-Labelling of Cactus Graphs

An L(0,1)-labelling of a graph G is an assignment of nonnegative integers to the vertices of G such that the difference between the labels assigned to any two adjacent vertices is at least zero and the difference between the labels assigned to any two vertices which are at distance two is at least one. The span of an L(0,1)-labelling is the maximum label number assigned to any vertex of G. The L(0,1)-labelling number of a graph G, denoted by λ0.1(G) is the least integer k such that G has an L(0,1)-labelling of span k. This labelling has an application to a computer code assignment problem. The task is to assign integer control codes to a network of computer stations with distance restrictions. A cactus graph is a connected graph in which every block is either an edge or a cycle. In this paper, we label the vertices of a cactus graph by L(0,1)-labelling and have shown that, △-1≤λ0.1(G)≤△ for a cactus graph, where △ is the degree of the graph G.

OPTIMAL LABELLING OF UNIT IN TERVAL GRAPHS

This paper shows that, for every unit interval graph, there is a labelling which is simultaneously optimal for the following seven graph labelling problems: bandwidth, cyclic bandwidth, profile, fill-in, cutwidth, modified cutwidth, and bandwidth sum(linear arrangement).

Some Sequence of Wrapped Δ-Labellings for the Complete Bipartite Graph

The design of large disk array architectures leads to interesting combinatorial problems. Minimizing the number of disk operations when writing to consecutive disks leads to the concept of “cluttered orderings” which were introduced for the complete graph by Cohen et al. (2001). Mueller et al. (2005) adapted the concept of wrapped Δ-labellings to the complete bipartite case. In this paper, we give some sequence in order to generate wrapped Δ-labellings as cluttered orderings for the complete bipartite graph. New sequence we give is different from the sequences Mueller et al. gave, though the same graphs in which these sequences are labeled.

Two-dimensional horizontal visibility graph analysis of human brain aging on gray matter

Characterizing the trajectory of the healthy aging brain and exploring age-related structural changes in the brain can help deepen our understanding of the mechanism of brain aging.Currently,most structural magnetic resonance imaging literature explores brain aging merely from the perspective of morphological features,which cannot fully utilize the grayscale values containing important intrinsic information about brain structure.In this study,we propose the construction of two-dimensional horizontal visibility graphs based on the pixel intensity values of the gray matter slices directly.Normalized network structure entropy(NNSE)is then introduced to quantify the overall heterogeneities of these graphs.The results demonstrate a decrease in the NNSEs of gray matter with age.Compared with the middle-aged and the elderly,the larger values of the NNSE in the younger group may indicate more homogeneous network structures,smaller differences in importance between nodes and thus a more powerful ability to tolerate intrusion.In addition,the hub nodes of different adult age groups are primarily located in the precuneus,cingulate gyrus,superior temporal gyrus,inferior temporal gyrus,parahippocampal gyrus,insula,precentral gyrus and postcentral gyrus.Our study can provide a new perspective for understanding and exploring the structural mechanism of brain aging.

Felicitous Labellings of Some Network Models

Building up graph models to simulate scale-free networks is an important method since graphs have been used in researching scale-free networks. One use labelled graphs for distinguishing objects of communication and information networks. In this paper some methods are given for constructing larger felicitous graphs from smaller graphs having special felicitous labellings, and some network models are shown to be felicitous.

A Note on <i>n</i>-Set Distance-Labelings of Graphs

This note is considered as a sequel of Yeh [1]. Here, we present a generalized (vertex) distance labeling (labeling vertices under constraints depending the on distance between vertices) of a graph. Instead of assigning a number (label) to each vertex, we assign a set of numbers to each vertex under given conditions. Some basic results are given in the first part of the note. Then we study a particular class of this type of labelings on several classes of graphs.

<i>L</i>(2,1)-Labeling Number of the Product and the Join Graph on Two Fans

L(2,1)-labeling number of the product and the join graph on two fans are discussed in this paper, we proved that L(2,1)-labeling number of the product graph on two fans is?λ(G) ≤ Δ+3 , L(2,1)-labeling number of the join graph on two fans is?λ(G) ≤ 2Δ+3.

Zero-M-Cordial Labeling of Some Graphs

In this paper we prove that the complete bipartite graph kmn where m and n are even, join of two cycle graphs cn and cm where n + m ≡ 0 (mod 4), split graph of cn for even “n”, Kn × P2 where n is even are admits a Zero-M-Cordial labeling. Further we prove that Kn × P2Bn = K1,n × P2 of odd n admits a Zero-M-Cordial labeling.

Prime Cordial Labeling of Some Graphs

In this paper we prove that the split graphs of K1,n and Bn,n are prime cordial graphs. We also show that the square graph of Bn,n is a prime cordial graph while middle graph of Pn is a prime cordial graph for n≥4 . Further we prove that the wheel graph Wn admits prime cordial labeling for n≥8.

<i>L</i>(2,1)-Labeling of the Brick Product Graphs

A k-L(2,1)-labeling for a graph G is a function such that whenever and whenever u and v are at distance two apart. The λ-number for G, denoted by λ(G), is the minimum k over all k-L(2,1)-labelings of G. In this paper, we show that for or 11, which confirms Conjecture 6.1 stated in [X. Li, V. Mak-Hau, S. Zhou, The L(2,1)-labelling problem for cubic Cayley graphs on dihedral groups, J. Comb. Optim. (2013) 25: 716-736] in the case when or 11. Moreover, we show that? if 1) either (mod 6), m is odd, r = 3, or 2) (mod 3), m is even (mod 2), r = 0.

Induced Total Labellings of Models as Scale-free Networks

A recently discovered approach including de Brujin graphs and Eulerian circuits are used to DNA sequencing and fragment assembly, and to simplify DNA graphs through a series of transformations on graphs and digraphs in the field of bioinformatics. Since numbered graphs provide underlying mathematical models in studying the wide variety of seemingly unrelated practical applications, so graph colorings often are used to divide large systems into subsystems. A new graph labeling has been introduced and investigated.

N-Set Distance-Labelings for Cycle Graphs

Let G = (V, E) be a graph and Cm be the cycle graph with m vertices. In this paper, we continued Yeh’s work [1] on the distance labeling of the cycle graph Cm. An n-set distance labeling of a graph G is the labeling of the vertices (with n labels per vertex) of G under certain constraints depending on the distance between each pair of the vertices in G. Following Yeh’s notation [1], the smallest value for the largest label in an n-set distance labeling of G is denoted by λ1(n)(G). Basic results were presented in [1] for λ1(2)(Cm) for all m and λ1(n)(Cm) for some m where n ≥ 3. However, there were still gaps left unstudied due to case-by-case complexities. For these uncovered cases, we proved a lower bound for λ1(n)(Cm). Then we proposed an algorithm for finding an n-set distance labeling for n ≥ 3 based on our proof of the lower bound. We verified every single case for n = 3 up to n = 500 by this same algorithm, which indicated that the upper bound is the same as the lower bound for n ≤ 500.

Hopf Algebra of Labeled Simple Graphs

A lot of combinatorial objects have a natural bialgebra structure. In this paper, we prove that the vector space spanned by labeled simple graphs is a bialgebra with the conjunction product and the unshuffle coproduct. In fact, it is a Hopf algebra since it is graded connected. The main conclusions are that the vector space spanned by labeled simple graphs arising from the unshuffle coproduct is a Hopf algebra and that there is a Hopf homomorphism from permutations to label simple graphs.

Edge Product Cordial Labeling of Some Cycle Related Graphs

For a graph having no isolated vertex, a function is called an edge product cordial labeling of graph G, if the induced vertex labeling function defined by the product of labels of incident edges to each vertex is such that the number of edges with label 0 and the number of edges with label 1 differ by at most 1 and the number of vertices with label 0 and the number of vertices with label 1 also differ by at most 1. In this paper, we discuss edge product cordial labeling for some cycle related graphs.

The L(3,2,1)-labeling on Bipartite Graphs

An L（3, 2, 1）-labeling of a graph G is a function from the vertex set V（G） to the set of all nonnegative integers such that ｜f（u）-f（v）｜≥3 if dG（u,v） = 1, ｜f（u）-f（v）｜≥2 if dG（u,v） = 2, and ｜f（u）-f（v）｜≥1 if dG（u,v） = 3. The L（3, 2,1）-labeling problem is to find the smallest number λ3（G） such that there exists an L（3, 2,1）-labeling function with no label greater than it. This paper studies the problem for bipartite graphs. We obtain some bounds of λ3 for bipartite graphs and its subclasses. Moreover, we provide a best possible condition for a tree T such that λ3（T） attains the minimum value.

基于label的空间叠置方法及在嵌入式GIS中的应用

针对嵌入式GIS中地图数据的空间叠置问题,提出一种基于label的空间拓扑算子实现方法,主要包括构建拓扑图,计算弧段的label,根据规则选取弧段,构建新的结果几何体。实验结果证明了该方法不仅对于同维度几何体、而且对于不同维度几何体的空间叠置都适用,将该算法嵌入野外调查GIS系统,能够现场完成变更,在工程实践中具有一定的普遍有效性。

基于L1-Graph表示的标记传播多观测样本分类算法

同类样本被认为是分布在同一个高维观测空间的低维流形上,针对多观测样本分类如何利用这一流形结构的问题,提出基于L1-Graph表示的标记传播多观测样本分类算法。首先基于稀疏表示的思路构造L1-Graph,进而得到样本之间的相似度矩阵,然后在半监督分类标记传播算法的基础上,限制所有的观测样本都属于同一个类别的条件下,得到一个具有特殊结构的类标矩阵,最后把寻找最优类标矩阵的计算转化为离散目标函数优化问题,进而计算出测试样本所属类别。在USPS手写体数据库、ETH-80物体识别数据库以及Cropped Yale人脸识别数据库上进行了一系列实验,实验结果表明了本文提出方法的可行性和有效性。

A DEGREE SEQUENCE METHOD FOR THE CUTWIDTH PROBLEM OF GRAPHS

The cutwidth problem fora graph G is to embed G into a path such thatthe maximum number of overlap edges is minimized.This paperpresents an approach based on the degree se- quence of G for determining the exact value of cutwidth of typical graphs (e.g.,n- cube,cater- pillars) .Relations between the cutwidth and other graph- theoretic parameters are studied as wel

CYCLIC BANDWIDTH SUM OF GRAPHS

Let G be a simple graph. The cyclic bandwidth sum problem is to determine a labeling of graph G in a cycle such that the total length of edges is as small as possible. In this paper, some upper and lower bounds on cyclic bandwidth sum of graphs are studied.

基于K-means和Label Propagation的半监督网页分类

提出基于图的半监督学习算法,即类别传播算,结合K均值算法改进,用于网页分类。该K均值类别传播方法使用欧式距离的建立带权∈NN图。在这个图中,图节点表示已标记或未标记的网页,边上的权重表示节点的相似度,已标记节点的类别沿着边向邻居节点传播,从而将网页分类问题形式化为类别在图上的传播。结合K均值方法,提高了计算速度以及图方法的归纳能力,经UCI数据集测试,结果表明,此算法比类别传播算法有更好的性能,能够有效地用于半监督网页分类。