A graph G is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. Murty and Simon conjectured that the number of edges in a diameter-2-critical graph G of order n is at most ⌊n2/4⌋ and that the extremal graphs are the complete bipartite graphs K⌊n/2⌋,⌈n/2⌉. A graph is t-edge-critical, abbreviated 3tEC, if its total domination number is 3 and the addition of any edge decreases the total domination number. It is known that proving the Murty–Simon Conjecture is equivalent to proving that the number of edges in a 3tEC graph of order n is greater than ⌈n(n-2)/4⌉. We study a family F of 3tEC graphs of diameter 2 for which every pair of nonadjacent vertices dominates the graph. We show that the graphs in F are precisely the bull-free 3tEC graphs and that the number of edges in such graphs is at least ⌊(n2-4)/4⌋, proving the conjecture for this family. We characterize the extremal graphs, and conjecture that this improved bound is in fact a lower bound for all 3tEC graphs of diameter 2. Finally we slightly relax the requirement in the definition of F—instead of requiring that all pairs of nonadjacent vertices dominate to requiring that only most of these pairs dominate—and prove the Murty–Simon equivalent conjecture for these 3tEC graphs.

A graph G is diameter 2-critical if its diameter is two and the deletion of any edge increases the diameter. Murty and Simon conjectured that the number of edges in a diameter 2-critical graph of order n is at most n2/4 and that the extremal graphs are complete bipartite graphs with equal size partite sets. We use an important association with total domination to prove the conjecture for the graphs whose complements have vertex connectivity k for k∈1,2,3.

A set S of vertices of a graph G = (V, E) is a dominating set if every vertex in V - S is adjacent to some vertex in 3. The domination number γ(G) is the minimum cardinality of a dominating set of G, and the domination subdivision number sdγ(G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the domination number. In June 2000, Arumugam conjectured that 1 ≤ sdγ(G) ≤ 3 for any graph G. However, a counterexample to this conjecture given in [6] suggests the modified conjecture that 1 ≤ sdγ(G) ≤ 4 for any graph G. It is also conjectured in [6] that for every graph G with minimum degree δ(G) ≥ 2, sdγ(G) ≤ δ(G) + 1. In this paper we extend several previous results and consider evidence in support of these two conjectures.

A set S of vertices of a graph G is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γt(G) is the minimum cardinality of a total dominating set of G. Let G be a connected spanning subgraph of Ks,s, and let H be the complement of G relative to Ks,s; that is, Ks,s, = G ⊕ H is a factorization of Ks,s. The graph G is k-supercritical relative to Ks,s, if γt(G) = k and γ1(G + e) = k - 2 for all e ∈ E(H). Properties of k-supercritical graphs are presented, and k-supercritical graphs are characterized for small k.

A set S of vertices in a graph G is a global dominating set of G if 5 simultaneously dominates both G and its complement G. The minimum cardinality of a global dominating set of G is the global domination number of G. We study the graphs for which removing any arbitrary edge from G and adding it to G decreases the global domination number.

La thèse porte sur l'étude théorique des propriétés électroniques à la surface de l’oxyde de métal de transition SrTiO3. Ce matériau est la pierre angulaire de l'électronique des oxydes, un nouveau domaine de recherche qui a pour but d'enquêter sur les oxydes de métaux de transition en tant que candidats post-silicium pour une émergence future de nouveaux composants électroniques. Le SrTiO3 est en soi un système étonnant : dans sa plus pure composition chimique, c’est un bon isolant avec une large bande interdite. Cependant, en le dopant avec de petites quantités d'autres éléments, il se transforme en un métal à haute mobilité d'électrons. Le SrTiO3 a également saisi l'attention en raison de sa capacité à accueillir des gaz d'électrons bidimensionnels (2DEGs) quand il est interfacé avec certains oxydes polaires. Ces 2DEGs présentent des propriétés fascinantes, la plus visible étant la coexistence du magnétisme et de la supraconductivité.La surface du SrTiO3 peut également accueillir des 2DEGs, sans avoir besoin de s'interfacer avec d'autres matériaux ; dans ce cas, les électrons participant aux transports sont générés par des lacunes d'oxygène créées à la surface. Cette observation est remarquable, car le SrTiO3 offre une structure simple où les propriétés des 2DEGs peuvent être étudiées.Cette thèse s’articule autour des deux axes. Tout d'abord, elle étudie la bicouche STO orientée 111, formée de seulement deux cellules unitaires. Deuxièmement, elle analyse les puits quantiques générés par les postes vacants de l'oxygène à la surface 111 du STO. Les deux sujets sont abordés en utilisant des modèles de liaison forte, dans lesquels le Hamiltonien incorpore différents termes liés aux énergies sur place, aux interactions de saut et au couplage spin-orbite. A partir de ces calculs, j’ai réalisé une analyse exhaustive des propriétés, du caractère et de la parité des orbitaux des bandes de valence et de conduction, ainsi que des états de bord dans la bicouche 111. / The thesis is focused on the theoretical study of the electronic properties at the surface of the transition metal oxide STO. This material is the cornerstone of oxide electronics, an emerging research area that has the goal of investigating transition metal oxides as post-silicon candidates for a future emerging new electronics. STO is in itself an astounding system; in its purest chemical composition is a good ban-insulator with a wide bandgap. Nevertheless, upon doing it with tiny amounts of other elements it transforms itself in a metal with high electron mobility. Even more remarkably, at the lowest temperatures, typically below 300mK, it goes superconductor. And adding to these properties, strain induces also ferroelectricity in this material. Over the last years, STO has also grabbed attention because of its ability of hosting two-dimensional electron gas (2DEGs) when it is interfaced with some polar oxides. Such 2DEGs exhibit fascinating properties, the most conspicuous is the coexistence of magnetism and superconductivity.The surface of STO can host 2DEGs too, without need of interfacing it to other materials; in this case the electrons participating in transport are generated by oxygen vacancies created at the surface. This is remarkable observation, as it affords a simpler structure where the 2DEGs properties can be studied. In spite of the accumulated knowledge, still a better fundamental comprehension is required of the electronic structure of the quantum wells at the surfaces oriented along the 111 direction, for which the perovskite structure is reminiscent of the celebrated honeycomb-like structure of graphene. Contrary to the latter, in which electrons are in s- and p- states, 111 quantum wells in STO would host electrons in d-bands. Higher electronic correlations are then expected, that may bring new fascinating physics.The outline of this Thesis has two main branches: first, it studies the 111-oriented STO bilayer, formed by just two unit cells; secondly it analyzes the quantum wells generated by Oxygen vacancies at the 111-surface of STO. Both subjects are approached using tight-binding models in which the Hamiltonian incorporates different terms related to on-site energies, hopping interactions or spin-orbit coupling. From these calculations, I have carried out an exhaustive analysis of the orbital character and parity properties of valence and conduction bands, as well as edge states in the 111 bilayer. Tight-binding calculations have also shed light on the orbital character, space location and extension and energy of electronic states generated by oxygen vacancies at the 001 surface of STO.

There are high demands of effective and high-performance of collaborations between mobile devices in the places where traditional Internet connections are unavailable, unreliable, or significantly overburdened, such as on a battlefield, disaster zones, isolated rural areas, or crowded public venues. To enable collaboration among the devices in opportunistic networks, code offloading and Remote Method Invocation are the two major mechanisms to ensure code portions of applications are successfully transmitted to and executed on the remote platforms. Although these domains are highly enjoyed in research for a decade, the limitations of multi-device connectivity, system error handling or cross platform compatibility prohibit these technologies from being broadly applied in the mobile industry. To address the above problems, we designed and developed UMSEF - an Universal Mobile Service Execution Framework, which is an innovative and radical approach for mobile computing in opportunistic networks. Our solution is built as a component-based mobile middleware architecture that is flexible and adaptive with multiple network topologies, tolerant for network errors and compatible for multiple platforms. We provided an effective algorithm to estimate the resource availability of a device for higher performance and energy consumption and a novel platform for mobile remote method invocation based on declarative annotations over multi-group device networks. The experiments in reality exposes our approach not only achieve the better performance and energy consumption, but can be extended to large-scaled ubiquitous or IoT systems.

abstract: Emerging from years of research and development, the Internet-of-Things (IoT) has finally paved its way into our daily lives. From smart home to Industry 4.0, IoT has been fundamentally transforming numerous domains with its unique superpower of interconnecting world-wide devices. However, the capability of IoT is largely constrained by the limited resources it can employ in various application scenarios, including computing power, network resource, dedicated hardware, etc. The situation is further exacerbated by the stringent quality-of-service (QoS) requirements of many IoT applications, such as delay, bandwidth, security, reliability, and more. This mismatch in resources and demands has greatly hindered the deployment and utilization of IoT services in many resource-intense and QoS-sensitive scenarios like autonomous driving and virtual reality. I believe that the resource issue in IoT will persist in the near future due to technological, economic and environmental factors. In this dissertation, I seek to address this issue by means of smart resource allocation. I propose mathematical models to formally describe various resource constraints and application scenarios in IoT. Based on these, I design smart resource allocation algorithms and protocols to maximize the system performance in face of resource restrictions. Different aspects are tackled, including networking, security, and economics of the entire IoT ecosystem. For different problems, different algorithmic solutions are devised, including optimal algorithms, provable approximation algorithms, and distributed protocols. The solutions are validated with rigorous theoretical analysis and/or extensive simulation experiments. / Dissertation/Thesis / Doctoral Dissertation Computer Science 2019

Le fond diffus cosmologique (CMB) est la première lumière libérée par l’Univers.À ce titre, elle constitue la photographie la plus ancienne à laquelle nous ayons accès.Ces photons recèlent des trésors d’informations capables de nous renseigner tant sur le contenu énergétique de l’Univers que sur son histoire. En retraçant son évolution jusqu’aujourd’hui, on est capable d’établir des scénarios quant à la période qui a précédé l’émission du CMB, inaccessible aux observations. Plus particulièrement,la plupart des modèles s’accordent à dire que l’Univers aurait connu juste après le Big Bang une période d’expansion exponentielle qualifiée d’inflation. L’un des défis majeurs de la cosmologie consiste à confirmer et contraindre ces modèles en cherchant sur le CMB les empreintes théoriques laissées par l’inflation : un motif de polarisation qualifié de mode B. Cependant, ce signal est attendu à un niveau très faible, sa détection requiert donc la mise en place d’instruments extrêmement sensibles. Cette thèse s’inscrit dans l’effort technologique mené au sein du projet QUBIC pour cette quête. Dans cette optique on s’est intéressé aux détecteurs, des matrices de plusieurs centaines de bolomètres supraconducteurs. Dans un premier temps, on a défini une méthode permettant de dimensionner les détecteurs et la matrice pour répondre au mieux à nos attentes à travers l’ajustement de paramètres pertinents. Puis on a mené pour la première fois dans la collaboration toute la réalisation d’une matrice de 256détecteurs sur laquelle on a par la suite effectué et exposé des tests préliminaires prometteurs pour la future implémentation du plan focal de QUBIC. / The cosmic microwave background (CMB) is the very first light of the Uni- verse and thus constitutes the oldest picture of its initial state. These photons carry valuable information constraining both the energy content and the history of the Universe. CMB observations allow us to reconstruct what occurred before the CMB anisotropies were imprinted. The most promising theoretical models all postulate an epoch of exponential expansion known as inflation just after the Big Bang. One of the major challenges of observational cosmology is hence to confirm or falsify inflation as well as to discover how inflation was realized in a particular model by searching for its imprint on the CMB polarization B-mode. This signal is however expected to be extremely weak and its detection requires a very sensitive experiment. This thesis reports on contributions to the technology development for the innovative QUBIC instrument, focusing on the perfection of an array of several hundreds of supercon- ducting bolometric detectors. A method was defined to design the detector array through tuning the relevant parameters to best meet our requirements. Then a 256- detector prototype array was fully manufactured and characterized. The preliminary characterization gave promising results for the forthcoming implementation of the QUBIC focal plane.

La présence de structures filamentaires est souvent rapportée dans plusieurs machines de fusion nucléaire à confinement magnétique, spécialement sur lequel s'appelle Tokamak. Etant porteurs de grandes quantités des particules et chaleur, la présence des filaments dans le bord du tokamak (le scrape-off layer, SOL) pourraient poser des dangers aux superficies solides du tokamak. Pour mieux comprendre leur comportement, dans le cadre de cette thèse doctorale, les filaments sont étudiés par les expériences numériques en utilisant un modèle 3D fluide istherme, TOKAM3X en les considerant comme structures isolées et structures spontanées. Cette manière de les étudier permet de faire divers analyses paramétriques – par exemple la resistivité parallèle du plasma et la présence d'un cisaïllement magnétique, et au même temps les propriétés du filaments (comme sa longeur parallèle, et son intensité de densité). Ces études montrent un impact fort de la resistivité parallèle sur la velocité des filaments et en conséquence peut modifier leur temps de vie dans le bord de la machine. Les résultats des simulations sur le cisaïllement magnétique et la séparatrice indiquent qu'ils sont des ingrédients clés pour la destruction et génération des filaments. En plus, la comparaison entre les filaments initialisés (seeded) et les filaments formés spontanément montre qu'ils ne sont pas parreils dans leur comportement, bien que leurs characteristiques moyennées en temps sont bien conservées. / Filamentary transport has been experimentally observed in a multitude of magnetically confined fusion devices, especially of the tokamak type. Filaments are carriers of large quantities of particles and heat and as such, their presence in the SOL has implications for the target surface design in future fusion reactors. To better understand their nature, this doctoral thesis studies filaments through computer simulations as isolated structures and spontaneously forming structures, using a 3D fluid model called the TOKAM3X. Parametric studies using the model for studying the effect of the plasma's parallel resistivity and magnetic shear, and also the filament's parallel extension and size/density amplitude are performed and analysed. The studies reveal the strong impact of the parallel resistivity on filament velocities and hence their lifetimes in the SOL. The doctoral work also looked at the impact of strong local magnetic shear and the separatrix on the motion and generation of filaments. The results from the simulations performed reveal that strong shear mechanisms may be key to the destruction and formation of filaments. Further, a comparison of spontaneously forming and seeded filaments shows that seeded filaments do not behave completely the same way as spontaneously forming ones. But their mean velocity characteristics are still retained to a good degree.