Distributed computation of virtual coordinates for greedy routing in sensor networks

Sensor networks are emerging as a paradigm for future computing, but pose a number of challenges in the fields of networking and distributed computation. One challenge is to devise a greedy routing protocol—one that routes messages through the network using only information available at a node or its neighbors. Modeling the connectivity graph of a sensor network as a 3-connected planar graph, we describe how to compute on the network in a distributed and local manner a special geometric embedding of the graph. This embedding supports a geometric routing protocol called “greedy routing” based on the “virtual” coordinates of the nodes derived from the embedding.     

Maximizing edge-ratio is NP-complete

Given a graph G and a bipartition of its vertices, the edge-ratio is the minimum for both classes so defined of their number of internal edges divided by their number of cut edges. We prove that maximizing edge-ratio is NP-complete.     

Research problems from the BCC22

Open problems from the problem session at the 22nd British Combinatorial Conference at St Andrews, on 10 July 2009.     

The critical group of <Emphasis Type="Italic">K</Emphasis><Subscript><Emphasis Type="Italic">m</Emphasis></Subscript> × <Emphasis Type="Italic">C</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript>

In this paper, the structure of the critical group of the graph K _m × C _n is determined, where m, n ≥ 3.     

A Toughness Condition for Fractional (k,m)-deleted Graphs Revisited

In computer networks, toughness is an important parameter which is used to measure the vulnerability of the network. Zhou et al. obtains a toughness condition for a graph to be fractional (k, m)-deleted and presents an example to show the sharpness of the toughness bound. In this paper, we remark that the previous example does not work and inspired by this fact, we present a new toughness condition for fractional (k, m)-deleted graphs improving the existing one. Finally, we state an open problem.     

A class of highly symmetric graphs,symmetric cylindrical constructions and their spectra

In this article, we introduce the algebra of block-symmetric cylinders and we show that symmetric cylindrical constructions on base-graphs admitting commutative decompositions behave as generalized tensor products. We compute the characteristic polynomial of such symmetric cylindrical constructions in terms of the spectra of the base-graph and the cylinders in a general setting. This gives rise to a simultaneous generalization of some well-known results on the spectra of a variety of graph amalgams, as various graph products, graph subdivisions and generalized Petersen graph constructions. While our main result introduces a connection between spectral graph theory and commutative decompositions of graphs, we focus on commutative cyclic decompositions of complete graphs and tree-cylinders along with a subtle group labeling of trees to introduce a class of highly symmetric graphs containing the Petersen and the Coxeter graphs. Also, using techniques based on recursive polynomials we compute the characteristic polynomials of these highly symmetric graphs as an application of our main result.     

固体异质结界面结构预测方法及AutoInterface程序实现

预测材料异质结的界面原子结构对于理解界面对性能的影响至关重要.目前,从理论上预测材料界面结构仍具有极大挑战,主要是缺乏普适有效的理论计算方法.本文介绍了本课题组在异质结界面结构预测方面取得的最新进展.结合马氏体相变唯象理论、图论和随机表面行走算法,提出了界面结构的一种有效预测方法,可以实现自动化的计算预测.通过GaP/TiO2半导体异质结等展示了该方法的有效性和在催化等领域的应用前景.     

On fuzzy multi-valued functions, part 4: Fuzzy economic models

An application to fuzzy economic systems of the fuzzy multi-valued functions theory elaborated by both of us in our previous papers is presented. First, stationary and dynamic fuzzy economic models are defined. Next the optimality of fuzzy trajectories of these models is introduced and investigated.     

A fast algorithm to remove proper and homogeneous pairs of cliques (while preserving some graph invariants)

We introduce a family of reductions for removing proper and homogeneous pairs of cliques from a graph G. This family generalizes some routines presented in the literature, mostly in the context of claw-free graphs. These reductions can be embedded in a simple algorithm that in at most |E(G)| steps builds a new graph G^′ without proper and homogeneous pairs of cliques, and such that G and G^′ agree on the value of some relevant invariant (or property).     

The spum and sum-diameter of graphs: Labelings of sum graphs

A sum graph is a finite simple graph whose vertex set is labeled with distinct positive integers such that two vertices are adjacent if and only if the sum of their labels is itself another label. The spum of a graph G is the minimum difference between the largest and smallest labels in a sum graph consisting of G and the minimum number of additional isolated vertices necessary so that a sum graph labeling exists. We investigate the spum of various families of graphs, namely cycles, paths, and matchings. We introduce the sum-diameter, a modification of the definition of spum that omits the requirement that the number of additional isolated vertices in the sum graph is minimal, which we believe is a more natural quantity to study. We then provide asymptotically tight general bounds on both sides for the sum-diameter, and study its behavior under numerous binary graph operations as well as vertex and edge operations. Finally, we generalize the sum-diameter to hypergraphs.