32344923
Two Minimum Dominating Sets with Minimum Intersection in Chordal Graphs
We prove that the problem of finding two minimum dominating sets (connected dominating sets or clique transversals) with minimum intersection is polynomially solvable on interval graphs. Furthermore, the problem of deciding whether or not there exist two disjoint minimum dominating sets (connected dominating sets or clique transversals) is shown to be NP-hard for chordal graphs.
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.
2423429
On d-antimagic labelings of prisms
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
30156520
Mod sum number of wheels
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.
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.
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
13019795
Large deformation diffeomorphic metric mapping of fiber orientations
This paper proposes a method to match diffusion tensor magnetic resonance images (DT-MRI) through the large deformation diffeomorphic metric mapping of vector fields, focusing on the fiber orientations, considered as unit vector fields on the image volume. We study a suitable action of diffeomorphisms on such vector fields, and provide an extension of the large deformation diffeomorphic metric-mapping framework to this type of dataset, resulting in optimizing for geodesies on the space of diffeomorphisms connecting two images. Two different distance function of vector fields are considered. Existence of the minimizers under smoothness assumptions on the compared vector fields is proved, and coarse to fine hierarchical strategies are detailed, to reduce both ambiguities and computation load. This is illustrated by numerical experiments on DT-MRI heart and brain images
42482105
Logical Secrets
33086640
Rate-distortion theory applied to automatic object recognition
We consider the problem of recognizing CAD models at arbitrary orientations observed via the projective transformation on an imaging sensor with noise. Bounds on codebook size are established through the rate-distortion curve for a distortion measure derived from the Hilbert-Schmidt norm for elements of the orthogonal group.