28355264
Minimum Diameter of Diregular Digraphs of Degree 2
Etude de certaines relations entre le nombre de sommets, degre et diametre de graphes finis diregulaires. Les trois problemes consideres sont N(d,k), K(u,d) et D(u, k) ou, autrement dit, trouver le nombre maximum possible de sommets etant donnes le degre d et le diametre k; trouver le diametre minimum possible etant donnes le nombre de sommets n et le degre d et trouver le degre minimum possible etant donnes le nombre de sommets n et le diametre k respectivement
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.
41148524
Vertex-Magic Total Labelings Of Generalized Petersen Graphs
A vertex-magic total labeling of a graph G=(V, E) with v vertices and e edges is an assignment of the integers from 1 to v + e to the vertices and edges of G with the property that the sum of the label on a vertex and the labels on its incident edges is a constant, independent of the choice of the vertex. In this paper we give a vertex-magic total labeling for the generalized Petersen graphs P(n, m) for all n@3,1@m⌊(n−1)/2⌋.
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.
37078414
Generalized Domination in Chordal Graphs
We discuss the computational complexity of generalized domination problems, which were introduced in [J.A.Telle: Complexity of domination-type problems in graphs, Nordic Journal of Computing 1 (1994), 157-171], restricted to chordal and interval graphs. The existence problem, parametrized by two sets of nonnegative integers σ and ρ, asks for the existence of a set S of vertices of a given graph such that for every vertex u ∈ S (or u ∉ S), the number of neighbors of u which are in S is in σ (in ρ, respectively). Telle proved that this problem is NP-complete for general graphs, provided both σ and ρ are finite and 0 ∉ ρ. One of our main results shows that in such cases, the existence problem is polynomially solvable for interval graphs. On the other hand, for chordal graphs, the complexity of the existence problem varies significantly even when σ and ρ contain one element each.
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
7684635
Information-Theoretic Bounds on Target Recognition Performance Based on Degraded Image Data
This paper derives bounds on the performance of statistical object recognition systems, wherein an image of a target is observed by a remote sensor. Detection and recognition problems are modeled as composite hypothesis testing problems involving nuisance parameters. We develop information-theoretic performance bounds on target recognition based on statistical models for sensors and data, and examine conditions under which these bounds are tight. In particular, we examine the validity of asymptotic approximations to probability of error in such imaging problems. Problems involving Gaussian, Poisson, and multiplicative noise, and random pixel deletions are considered, as well as least-favorable Gaussian clutter. A sixth application involving compressed sensor image data is considered in some detail. This study provides a systematic and computationally attractive framework for analytically characterizing target recognition performance under complicated, non-Gaussian models and optimizing system parameters.
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.
46718511
Capability-Based Financial Instruments
Every novel cooperative arrangement of mutually suspicious parties interacting electronically -- every smart contract -- effectively requires a new cryptographic protocol. However, if every new contract requires new cryptographic protocol design, our dreams of cryptographically enabled electronic commerce would be unreachable. Cryptographic protocol design is too hard and expensive, given our unlimited need for new contracts.Just as the digital logic gate abstraction allows digital circuit designers to create large analog circuits without doing analog circuit design, we present cryptographic capabilities as an abstraction allowing a similar economy of engineering effort in creating smart contracts. We explain the E system, which embodies these principles, and show a covered-call-option as a smart contract written in a simple security formalism independent of cryptography, but automatically implemented as a cryptographic protocol coordinating five mutually suspicious parties.
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.