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.
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.
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.
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.
44565534
On the sum number of wheels
A graph G=(V,E) is a sum graph if there exists a labelling of the vertices of G with distinct positive integers so that uv∈E if and only if the sum of the labels assigned to u and v is the label of a vertex of G. The sum number of a graph is the minimum number of isolated vertices that, together with the given graph, form a sum graph. Sum graph labellings of wheels have been examined previously by other investigators. The sum number of an n spoked wheel, σ(Wn),n⩾5, has been found to be n when n is odd and n2+2 when n is even; however the proofs of these results are incomplete. In this paper we provide a complete proof and affirm that these previous results are correct.
2078197
Collaborative Agents for C2 Teamwork Simulation
Existing team training software often requires that trainees be organized as physical teams and the members of the same team be trained at the same time. To demonstrate that team training software can be made more flexible, this paper presents an approach to incorporating software agents into the distributed command-and-control (C2) simulation software DDD, which supports only human players. Based on the multi-agent architecture CAST, the software agents are designed as a team to perform C2 tasks in the DDD. By associating the agents with the same basic capabilities as the DDD provides its human users, we illustrate how to specify the teamwork knowledge for the agent team, and how to make agents efficiently reason about the dynamic, partially observable environment. Different methods of communication and coordination among agents are also briefly described.
12989752
Asymptotic performance analysis of Bayesian target recognition
This article investigates the asymptotic performance of Bayesian target recognition algorithms using deformable-template representations. Rigid computer-aided design (CAD) models represent the underlying targets; low-dimensional matrix Lie-groups (rotation and translation) extend them to particular instances. Remote sensors observing the targets are modeled as projective transformations, converting three-dimensional scenes into random images. Bayesian target recognition corresponds to hypothesis selection in the presence of nuisance parameters; its performance is quantified as the Bayes' error. Analytical expressions for this error probability in small noise situations are derived, yielding asymptotic error rates for exponential error probability decay.
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=
9373292
Deformable templates using large deformation kinematics
A general automatic approach is presented for accommodating local shape variation when mapping a two-dimensional (2-D) or three-dimensional (3-D) template image into alignment with a topologically similar target image. Local shape variability is accommodated by applying a vector-field transformation to the underlying material coordinate system of the template while constraining the transformation to be smooth (globally positive definite Jacobian). Smoothness is guaranteed without specifically penalizing large-magnitude deformations of small subvolumes by constraining the transformation on the basis of a Stokesian limit of the fluid-dynamical Navier-Stokes equations. This differs fundamentally from quadratic penalty methods, such as those based on linearized elasticity or thin-plate splines, in that stress restraining the motion relaxes over time allowing large-magnitude deformations. Kinematic nonlinearities are inherently necessary to maintain continuity of structures during large-magnitude deformations, and are included in all results. After initial global registration, final mappings are obtained by numerically solving a set of nonlinear partial differential equations associated with the constrained optimization problem. Automatic regridding is performed by propagating templates as the nonlinear transformations evaluated on a finite lattice become singular. Application of the method to intersubject registration of neuroanatomical structures illustrates the ability to account for local anatomical variability.
35339559
Two new families of large compound graphs
A question of special interest in graph theory is the design of large graphs. Specifically, we want to find constructions of graphs with order as large as possible for a given degree and diameter D . Two generalizations of two large compound graphs are proposed in this article. Three particular cases of these families of graphs presented here allow us to improve the order for the entries (15, 7), (13, 10), and (15, 10) in the table of the largest known ( , D)-graphs. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 47(3), 140–146 2006