ﻻ يوجد ملخص باللغة العربية
We investigate a special case of hereditary property in graphs, referred to as {em robustness}. A property (or structure) is called robust in a graph $G$ if it is inherited by all the connected spanning subgraphs of $G$. We motivate this definition using two different settings of dynamic networks. The first corresponds to networks of low dynamicity, where some links may be permanently removed so long as the network remains connected. The second corresponds to highly-dynamic networks, where communication links appear and disappear arbitrarily often, subject only to the requirement that the entities are temporally connected in a recurrent fashion ({it i.e.} they can always reach each other through temporal paths). Each context induces a different interpretation of the notion of robustness. We start by motivating the definition and discussing the two interpretations, after what we consider the notion independently from its interpretation, taking as our focus the robustness of {em maximal independent sets} (MIS). A graph may or may not admit a robust MIS. We characterize the set of graphs forallMIS in which {em all} MISs are robust. Then, we turn our attention to the graphs that {em admit} a robust MIS (existsMIS). This class has a more complex structure; we give a partial characterization in terms of elementary graph properties, then a complete characterization by means of a (polynomial time) decision algorithm that accepts if and only if a robust MIS exists. This algorithm can be adapted to construct such a solution if one exists.
The robustness of a network is depending on the type of attack we are considering. In this paper we focus on the spread of viruses on networks. It is common practice to use the epidemic threshold as a measure for robustness. Because the epidemic thre
We investigate a special case of hereditary property that we refer to as {em robustness}. A property is {em robust} in a given graph if it is inherited by all connected spanning subgraphs of this graph. We motivate this definition in different contex
Using three supercomputers, we broke a record set in 2011, in the enumeration of non-isomorphic regular graphs by expanding the sequence of A006820 in Online Encyclopedia of Integer Sequences (OEIS), to achieve the number for 4-regular graphs of orde
Despite providing similar functionality, multiple network services may require the use of different interfaces to access the functionality, and this problem will only get worse with the widespread deployment of ubiquitous computing environments. One
Small-worlds represent efficient communication networks that obey two distinguishing characteristics: a high clustering coefficient together with a small characteristic path length. This paper focuses on an interesting paradox, that removing links in