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.
2423429
On d-antimagic labelings of prisms
24203387
Characterization of eccentric digraphs
The eccentric digraphED(G) of a digraph G represents the binary relation, defined on the vertex set of G, of being 'eccentric'; that is, there is an arc from u to v in ED(G) if and only if v is at maximum distance from u in G. A digraph G is said to be eccentric if there exists a digraph H such that G=ED(H). This paper is devoted to the study of the following two questions: what digraphs are eccentric and when the relation of being eccentric is symmetric. We present a characterization of eccentric digraphs, which in the undirected case says that a graph G is eccentric iff its complement graph G@? is either self-centered of radius two or it is the union of complete graphs. As a consequence, we obtain that all trees except those with diameter 3 are eccentric digraphs. We also determine when ED(G) is symmetric in the cases when G is a graph or a digraph that is not strongly connected.
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.
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.
30156520
Mod sum number of wheels
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
1692281
A stochastic model for studying the laminar structure of cortex from MRI
The human cerebral cortex is a laminar structure about 3 mm thick, and is easily visualized with current magnetic resonance (MR) technology. The thickness of the cortex varies locally by region, and is likely to be influenced by such factors as development, disease and aging. Thus, accurate measurements of local cortical thickness are likely to be of interest to other researchers. We develop a parametric stochastic model relating the laminar structure of local regions of the cerebral cortex to MR image data. Parameters of the model include local thickness, and statistics describing white, gray and cerebrospinal fluid (CSF) image intensity values as a function of the normal distance from the center of a voxel to a local coordinate system anchored at the gray/white matter interface. Our fundamental data object, the intensity-distance histogram (IDH), is a two-dimensional (2-D) generalization of the conventional 1-D image intensity histogram, which indexes voxels not only by their intensity value, but also by their normal distance to the gray/white interface. We model the IDH empirically as a marked Poisson process with marking process a Gaussian random field model of image intensity indexed against normal distance. In this paper, we relate the parameters of the IDH model to the local geometry of the cortex. A maximum-likelihood framework estimates the parameters of the model from the data. Here, we show estimates of these parameters for 10 volumes in the posterior cingulate, and 6 volumes in the anterior and posterior banks of the central sulcus. The accuracy of the estimates is quantified via Cramer-Rao bounds. We believe that this relatively crude model can be extended in a straightforward fashion to other biologically and theoretically interesting problems such as segmentation, surface area estimation, and estimating the thickness distribution in a variety of biologically relevant contexts.
18206108
Proving Facts about "|"
We study the Knights and Knaves problem, and find that for a proper treatment via theorem-proving, an interaction with natural language processing research is helpful. In particular, we discuss Ohlbach's claim that first-order logic is not well suited to handling this problem. Then we provide another interpretation of the problem using indexicals, and axiomatize it so that the desired result follows. We conclude by suggesting a broader context for dealing with "self-utterances" in automatic theorem-proving. Fuller details of automated proofs are given in a longer paper.
14414468
Information measures for object recognition accommodating signature variability
This paper presents measures characterizing the information content of remote observations of ground scenes imaged via optical and infrared sensors. Object recognition is posed in the context of deformable templates; the special Euclidean group is used to accommodate geometric variation of object pose. Principal component analysis of object signatures is used to represent and efficiently accommodate variation in object signature due to changes in the thermal state of the object surface. Mutual information measures, which are independent of the recognition system, are calculated quantifying both the information gain due to remote observations of the scene and the information loss due to signature variability. Signature model mismatch is quantitatively examined using the Kullback-Leibler divergence. Expressions are derived quadratically approximating the posterior conditional entropy on the orthogonal group for high signal-to-noise ratio. It is demonstrated that quadratic modules accurately characterize the posterior entropy for broad ranges of signal-to-mise ratio. Information gain in multiple-sensor scenarios is quantified, and it is demonstrated that the cost of signature uncertainty for the Comanche series of FLIR images collected by the US Army Night Vision Electronic Sensors Directorate is approximately 0.8 bits with an associated near doubling of mean-squared error uncertainty in pose.
7955941
Leveraging Channel Diversity for Key Establishment in Wireless Sensor Networks
As the use of sensor networks increases, security in this domain becomes a very real concern. One fundamental aspect of providing confidentiality and authentication is key distribution. While public-key encryption has provided these properties historically, sensors are resource constrained and benefit from symmetric key approaches. In this work, we propose a novel protocol for symmetric key distribution that uses the multiple channels available on sensor hardware. This channel diversity, along with spatial diversity of device locations, allows neighboring sensors to establish secure link keys from plaintext keys that are broadcast by sensors in their neighborhood. In particular, we show that using even one extra channel during the initialization procedure significantly improves the security of key establishment. Via analysis and simulation, we show that our protocol performs well in terms of network connectivity and resilience to colluding malicious devices, when compared to previous work. We show that our protocol can achieve over 90% connectivity among neighboring sensors with link keys that are uncompromised even when 80% of the devices in the network are malicious and collude. Finally, we present a thorough discussion of the comparative advantages and disadvantages of our approach compared to previous techniques.