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.
30156520
Mod sum number of wheels
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.
30300287
Digraphs of degree two which miss the Moore bound by two
Abstract It is well known that Moore digraphs do not exist except for trivial cases (degree one or diameter one). Consequently, for a given maximum out-degree d and a given diameter, we wish to find a digraph whose order misses the Moore bound by the smallest possible ‘defect’. For diameter two and arbitrary degree there are digraphs which miss the Moore bound by one. No examples of such digraphs of diameter at least three are known, although several necessary conditions for their existence have been obtained. In the case of degree two, it has been shown that there are no digraphs of diameter greater than two and defect one. There are five nonisomorphic digraphs of degree two, diameter two and defect two. In this paper we prove that digraphs of degree two and diameter k ⩾3 which miss the Moore bound by two do not exist.
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 .
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.
35322596
On the degrees of a strongly vertex-magic graph
Let G=(V,E) be a finite graph, where |V|=n>=2 and |E|=e>=1. A vertex-magic total labeling is a bijection @l from V@?E to the set of consecutive integers {1,2,...,n+e} with the property that for every v@?V, @l(v)+@?"w"@?"N"("v")@l(vw)=h for some constant h. Such a labeling is strong if @l(V)={1,2,...,n}. In this paper, we prove first that the minimum degree of a strongly vertex-magic graph is at least two. Next, we show that if 2e>=10n^2-6n+1, then the minimum degree of a strongly vertex-magic graph is at least three. Further, we obtain upper and lower bounds of any vertex degree in terms of n and e. As a consequence we show that a strongly vertex-magic graph is maximally edge-connected and hamiltonian if the number of edges is large enough. Finally, we prove that semi-regular bipartite graphs are not strongly vertex-magic graphs, and we provide strongly vertex-magic total labeling of certain families of circulant graphs.
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=
2224181
Dynamic Programming Generation of Curves on Brain Surfaces
Dynamic programming algorithms are presented for automated generation of length minimizing geodesics and curves of extremal curvature on the neocortex of the macaque and the visible human. Probabilistic models of curve variation are constructed in terms of the variability in speed, curvature, and torsion in the Frenet representation.
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.
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.