32918943
Bounds on the number of isolates in sum graph labeling
A simple undirected graph H is called a sum graph if there is a labeling L of the vertices of H into distinct positive integers such that any two vertices u and v of H are adjacent if and only if there is a vertex w with label L(w )= L(u )+ L(v). The sum number � (G) of a graph G =( V; E) is the least integer r such that the graph H consisting of G and r isolated vertices is a sum graph. It is clear that � (G)6|E|. In this paper, we discuss general upper and lower bounds on the sum number. In particular, we prove that, over all graphs G =( V; E) with 5xed |V |?3 and |E|, the average of � (G) is at least |E |− 3|V |(log|V |)=[log(( |V | 2 )=|E|)] −| V |− 1. In other words, for most graphs, � (G) ∈ (|E|). c � 2001 Elsevier Science B.V. All rights reserved.
1634653
A characterization of strongly chordal graphs
Abstract In this paper, we present a simple charactrization of strongly chordal graphs. A chordal graph is strongly chordal if and only if every cycle on six or more vertices has an induced triangle with exactly two edges of the triangle as the chords of the cycle.
16296646
A Note on Constructing Large Cayley Graphs of Given Degree and Diameter by Voltage Assignments
Voltage graphs are a powerful tool for constructing large graphs (called lifts ) with prescribed properties as covering spaces of small base graphs. This makes them suitable for application to the degree/diameter problem , which is to determine the largest order of a graph with given degree and diameter. Many currently known largest graphs of degree $\le 15$ and diameter $\le 10$ have been found by computer search among Cayley graphs of semidirect products of cyclic groups. We show that all of them can in fact be described as lifts of smaller Cayley graphs of cyclic groups, with voltages in (other) cyclic groups. This opens up a new possible direction in the search for large vertex-transitive graphs of given degree and diameter.
33503104
Almost Moore digraphs are diregular
Abstract An almost Moore digraph is a digraph of diameter k⩾2 , maximum out-degree d⩾2 and order n=d+d 2 +⋯+d k , that is, one less than the Moore bound. It is easy to show that the out-degree of an almost Moore digraph is constant (=d) . In this note we prove that also the in-degree of an almost Moore digraph is constant (=d) , that is, every almost Moore digraph is diregular of degree d .
1914740
Complete characterization of almost Moore digraphs of degree three
It is well known that Moore digraphs do not exist except for trivial cases (degree 1 or diameter 1), but there are digraphs of diameter two and arbitrary degree which miss the Moore bound by one. No 2004 Wiley Periodicals, Inc.
28891049
Connected graphs which are not mod sum graphs
Abstract In this paper we prove that no wheel with the exception of W 4 can be a mod sum graph. We also give the unique (up to multiplication by positive integers) mod sum labelling of W 4 . We also prove that the symmetric complete bipartite graph K n . n is not a mod sum graph.
1871640
Exploring the Energy-Latency Trade-Off for Broadcasts in Energy-Saving Sensor Networks
Networking protocols for multi-hop wireless sensor networks (WSNs) are required to simultaneously minimize resource usage as well as optimize performance metrics such as latency and reliability. This paper explores the energy-latency-reliability trade-off for broadcast in multi-hop WSNs, by presenting a new protocol called PBBF (probability-based broadcast forwarding). PBBF works at the MAC layer and can be integrated into any sleep scheduling protocol. For a given application-defined level of reliability for broadcasts, the energy required and latency obtained are found to be inversely related to each other. Our analysis and simulation study quantify this relationship at the reliability boundary, as well as performance numbers to be expected from a deployment. PBBF essentially offers a WSN application designer considerable flexibility in choice of desired operation points
15423783
Group Actions, Homeomorphisms, and Matching: A General Framework
This paper constructs metrics on the space of images I defined as orbits under group actions G. The groups studied include the finite dimensional matrix groups and their products, as well as the infinite dimensional diffeomorphisms examined in Trouvé (1999, Quaterly of Applied Math.) and Dupuis et al. (1998). Quaterly of Applied Math. Left-invariant metrics are defined on the product G × I thus allowing the generation of transformations of the background geometry as well as the image values. Examples of the application of such metrics are presented for rigid object matching with and without signature variation, curves and volume matching, and structural generation in which image values are changed supporting notions such as tissue creation in carrying one image to another.
15772070
Hilbert-Schmidt Lower Bounds for Estimators on Matrix Lie Groups for ATR
Deformable template representations of observed imagery model the variability of target pose via the actions of the matrix Lie groups on rigid templates. In this paper, we study the construction of minimum mean squared error estimators on the special orthogonal group, SO(n), for pose estimation. Due to the nonflat geometry of SO(n), the standard Bayesian formulation of optimal estimators and their characteristics requires modifications. By utilizing Hilbert-Schmidt metric defined on GL(n), a larger group containing SO(n), a mean squared criterion is defined on SO(n). The Hilbert-Schmidt estimate (HSE) is defined to be a minimum mean squared error estimator, restricted to SO(n). The expected error associated with the HSE is shown to be a lower bound, called the Hilbert-Schmidt bound (HSB), on the error incurred by any other estimator. Analysis and algorithms are presented for evaluating the HSE and the HSB in cases of both ground-based and airborne targets.
5303657
Consecutive magic graphs
Let G be a graph of order n and size e. A vertex-magic total labeling is an assignment of the integers 1,2,...,n+e to the vertices and the edges of G, so that at each vertex, the vertex label and the labels on the edges incident at that vertex, add to a fixed constant, called the magic number of G. Such a labeling is a-vertex consecutive magic if the set of the labels of the vertices is {a+1,a+2,...,a+n}, and is b-edge consecutive magic if the set of labels of the edges is {b+1,b+2,...,b+e}. In this paper we prove that if an a-vertex consecutive magic graph has isolated vertices then the order and the size satisfy (n-1)^2+n^2=(2e+1)^2. Moreover, we show that every tree with even order is not a-vertex consecutive magic and, if a tree of odd order is a-vertex consecutive then a=n-1. Furthermore, we show that every a-vertex consecutive magic graph has minimum degree at least two if a=0, or both 2e>=6n^2-2n+1 and 2a==10n^2-6n+1+4a and 2a=
6659707
Landmark matching via large deformation diffeomorphisms
This paper describes the generation of large deformation diffeomorphisms phi:Omega=[0,1]3<-->Omega for landmark matching generated as solutions to the transport equation dphi(x,t)/dt=nu(phi(x,t),t),epsilon[0,1] and phi(x,0)=x, with the image map defined as phi(.,1) and therefore controlled via the velocity field nu(.,t),epsilon[0,1]. Imagery are assumed characterized via sets of landmarks {xn, yn, n=1, 2, ..., N}. The optimal diffeomorphic match is constructed to minimize a running smoothness cost parallelLnu parallel2 associated with a linear differential operator L on the velocity field generating the diffeomorphism while simultaneously minimizing the matching end point condition of the landmarks. Both inexact and exact landmark matching is studied here. Given noisy landmarks xn matched to yn measured with error covariances Sigman, then the matching problem is solved generating the optimal diffeomorphism phi;(x,1)=integral0(1)nu(phi(x,t),t)dt+x where nu(.)=argmin(nu.)integral1(0) integralOmega parallelLnu(x,t) parallel2dxdt +Sigman=1N[yn-phi(xn,1)] TSigman(-1)[yn-phi(xn,1)]. Conditions for the existence of solutions in the space of diffeomorphisms are established, with a gradient algorithm provided for generating the optimal flow solving the minimum problem. Results on matching two-dimensional (2-D) and three-dimensional (3-D) imagery are presented in the macaque monkey.