Largest connected component of a star graph with faulty vertices

In order to make a full evaluation of an interconnection network, it is essential to estimate the minimum size of a largest connected component of this network provided the faulty vertices in the network may break its connectedness. Star graphs are recognized as promising candidates for interconnection networks. This article addresses the size of a largest connected component of a faulty star graph. We prove that, in an n-star graph (n >= 3) with up to 2n-4 faulty vertices, all fault-free vertices but at most two form a connected component. Moreover, all fault-free vertices but exactly two form a connected component if and only if the set of all faulty vertices is equal to the neighbourhood of a pair of fault-free adjacent vertices. These results show that star graphs exhibit excellent fault-tolerant abilities in the sense that there exists a large functional network in a faulty star graph.

The cohomological invariant E'(G,W) and some properties

Let G be a group, W a nonempty G-set and M a Z2G-module. Consider the restriction map resG W : H1(G,M) → Pi wi∈E H1(Gwi,M), [f] → (resGG wi [f])i∈I , where E = {wi, i ∈ I} is a set of orbit representatives in W and Gwi = {g ∈ G | gwi = wi} is the G-stabilizer subgroup (or isotropy subgroup) of wi, for each wi ∈ E. In this work we analyze some results presented in Andrade et al [5] about splittings and duality of groups, using the point of view of Dicks and Dunwoody [10] and the invariant E'(G,W) := 1+dimkerresG W, defined when Gwi is a subgroup of infinite index in G for all wi in E, andM = Z2 (where dim = dimZ2). We observe that the theory of splittings of groups (amalgamated free product and HNN-groups) is inserted in the combinatory theory of groups which has many applications in graph theory (see, for example, Serre [12] and Dicks and Dunwoody [10]).

Analyzing the Complexity and Reliability of Switch-Frequency-Reconfigurable Antennas Using Graph Models

This paper addresses the functional reliability and the complexity of reconfigurable antennas using graph models. The correlation between complexity and reliability for any given reconfigurable antenna is defined. Two methods are proposed to reduce failures and improve the reliability of reconfigurable antennas. The failures are caused by the reconfiguration technique or by the surrounding environment. These failure reduction methods proposed are tested and examples are given which verify these methods.

Cyclic automorphic graph decompositions

Chapter 1 introduces the tools and mechanics necessary for this report. Basic definitions and topics of graph theory which pertain to the report and discussion of automorphic decompositions will be covered in brief detail. An automorphic decomposition D of a graph H by a graph G is a G-decomposition of H such that the intersection of graph (D) @H. H is called the automorhpic host, and G is the automorphic divisor. We seek to find classes of graphs that are automorphic divisors, specifically ones generated cyclically. Chapter 2 discusses the previous work done mainly by Beeler. It also discusses and gives in more detail examples of automorphic decompositions of graphs. Chapter 2 also discusses labelings and their direct relation to cyclic automorphic decompositions. We show basic classes of graphs, such as cycles, that are known to have certain labelings, and show that they also are automorphic divisors. In Chapter 3, we are concerned with 2-regular graphs, in particular rCm, r copies of the m-cycle. We seek to show that rCm has a ρ-labeling, and thus is an automorphic divisor for all r and m. we discuss methods including Skolem type difference sets to create cycle systems and their correlation to automorphic decompositions. In the Appendix, we give classes of graphs known to be graceful and our java code to generate ρ-labelings on rCm.

ANALYSIS AND VISUALIZATION OF FLOW FIELDS USING INFORMATION-THEORETIC TECHNIQUES AND GRAPH-BASED REPRESENTATIONS

Three-dimensional flow visualization plays an essential role in many areas of science and engineering, such as aero- and hydro-dynamical systems which dominate various physical and natural phenomena. For popular methods such as the streamline visualization to be effective, they should capture the underlying flow features while facilitating user observation and understanding of the flow field in a clear manner. My research mainly focuses on the analysis and visualization of flow fields using various techniques, e.g. information-theoretic techniques and graph-based representations. Since the streamline visualization is a popular technique in flow field visualization, how to select good streamlines to capture flow patterns and how to pick good viewpoints to observe flow fields become critical. We treat streamline selection and viewpoint selection as symmetric problems and solve them simultaneously using the dual information channel [81]. To the best of my knowledge, this is the first attempt in flow visualization to combine these two selection problems in a unified approach. This work selects streamline in a view-independent manner and the selected streamlines will not change for all viewpoints. My another work [56] uses an information-theoretic approach to evaluate the importance of each streamline under various sample viewpoints and presents a solution for view-dependent streamline selection that guarantees coherent streamline update when the view changes gradually. When projecting 3D streamlines to 2D images for viewing, occlusion and clutter become inevitable. To address this challenge, we design FlowGraph [57, 58], a novel compound graph representation that organizes field line clusters and spatiotemporal regions hierarchically for occlusion-free and controllable visual exploration. We enable observation and exploration of the relationships among field line clusters, spatiotemporal regions and their interconnection in the transformed space. Most viewpoint selection methods only consider the external viewpoints outside of the flow field. This will not convey a clear observation when the flow field is clutter on the boundary side. Therefore, we propose a new way to explore flow fields by selecting several internal viewpoints around the flow features inside of the flow field and then generating a B-Spline curve path traversing these viewpoints to provide users with closeup views of the flow field for detailed observation of hidden or occluded internal flow features [54]. This work is also extended to deal with unsteady flow fields. Besides flow field visualization, some other topics relevant to visualization also attract my attention. In iGraph [31], we leverage a distributed system along with a tiled display wall to provide users with high-resolution visual analytics of big image and text collections in real time. Developing pedagogical visualization tools forms my other research focus. Since most cryptography algorithms use sophisticated mathematics, it is difficult for beginners to understand both what the algorithm does and how the algorithm does that. Therefore, we develop a set of visualization tools to provide users with an intuitive way to learn and understand these algorithms.

Beyond the tree of texts: Building an empirical model of scribal variation through graph analysis of texts and stemmata

Stemmatology, or the reconstruction of the transmission history of texts, is a field that stands particularly to gain from digital methods. Many scholars already take stemmatic approaches that rely heavily on computational analysis of the collated text (e.g. Robinson and O’Hara 1996; Salemans 2000; Heikkilä 2005; Windram et al. 2008 among many others). Although there is great value in computationally assisted stemmatology, providing as it does a reproducible result and allowing access to the relevant methodological process in related fields such as evolutionary biology, computational stemmatics is not without its critics. The current state-of-the-art effectively forces scholars to choose between a preconceived judgment of the significance of textual differences (the Lachmannian or neo-Lachmannian approach, and the weighted phylogenetic approach) or to make no judgment at all (the unweighted phylogenetic approach). Some basis for judgment of the significance of variation is sorely needed for medieval text criticism in particular. By this, we mean that there is a need for a statistical empirical profile of the text-genealogical significance of the different sorts of variation in different sorts of medieval texts. The rules that apply to copies of Greek and Latin classics may not apply to copies of medieval Dutch story collections; the practices of copying authoritative texts such as the Bible will most likely have been different from the practices of copying the Lives of local saints and other commonly adapted texts. It is nevertheless imperative that we have a consistent, flexible, and analytically tractable model for capturing these phenomena of transmission. In this article, we present a computational model that captures most of the phenomena of text variation, and a method for analysis of one or more stemma hypotheses against the variation model. We apply this method to three ‘artificial traditions’ (i.e. texts copied under laboratory conditions by scholars to study the properties of text variation) and four genuine medieval traditions whose transmission history is known or deduced in varying degrees. Although our findings are necessarily limited by the small number of texts at our disposal, we demonstrate here some of the wide variety of calculations that can be made using our model. Certain of our results call sharply into question the utility of excluding ‘trivial’ variation such as orthographic and spelling changes from stemmatic analysis.

ADDPLOT: Stata module to add twoway plot objects to an existing twoway graph

addplot adds twoway plot objects to an existing twoway graph. This is useful if you want to add additional objects such as titles or extra data points to a twoway graph after it has been created. Most of what addplot can do, can also be done by rerunning the original graph command including additional options or plot statements. addplot, however, might be useful if you have to modify a graph for which you cannot rerun the original command, for example, because you only have the graph file but not the data that were used to create the graph. Furthermore, addplot can do certain things that would be difficult to achieve in a single graph command (e.g. customizing individual subgraphs within a by-graph). addplot also provides a substitute for some of the functionality of the graph editor.

Embedding partial G-designs where G is a 4-cycle with a pendant edge

Let D denote the graph consisting of a cycle of length 4 with a pendant edge. In this paper, two very different small embeddings of partial D-designs are presented. (c) 2005 Elsevier B.V. All rights reserved.

Linked knowledge sources for topic classification of microposts:a semantic graph-based approach

Short text messages a.k.a Microposts (e.g. Tweets) have proven to be an effective channel for revealing information about trends and events, ranging from those related to Disaster (e.g. hurricane Sandy) to those related to Violence (e.g. Egyptian revolution). Being informed about such events as they occur could be extremely important to authorities and emergency professionals by allowing such parties to immediately respond. In this work we study the problem of topic classification (TC) of Microposts, which aims to automatically classify short messages based on the subject(s) discussed in them. The accurate TC of Microposts however is a challenging task since the limited number of tokens in a post often implies a lack of sufficient contextual information. In order to provide contextual information to Microposts, we present and evaluate several graph structures surrounding concepts present in linked knowledge sources (KSs). Traditional TC techniques enrich the content of Microposts with features extracted only from the Microposts content. In contrast our approach relies on the generation of different weighted semantic meta-graphs extracted from linked KSs. We introduce a new semantic graph, called category meta-graph. This novel meta-graph provides a more fine grained categorisation of concepts providing a set of novel semantic features. Our findings show that such category meta-graph features effectively improve the performance of a topic classifier of Microposts. Furthermore our goal is also to understand which semantic feature contributes to the performance of a topic classifier. For this reason we propose an approach for automatic estimation of accuracy loss of a topic classifier on new, unseen Microposts. We introduce and evaluate novel topic similarity measures, which capture the similarity between the KS documents and Microposts at a conceptual level, considering the enriched representation of these documents. Extensive evaluation in the context of Emergency Response (ER) and Violence Detection (VD) revealed that our approach outperforms previous approaches using single KS without linked data and Twitter data only up to 31.4% in terms of F1 measure. Our main findings indicate that the new category graph contains useful information for TC and achieves comparable results to previously used semantic graphs. Furthermore our results also indicate that the accuracy of a topic classifier can be accurately predicted using the enhanced text representation, outperforming previous approaches considering content-based similarity measures. © 2014 Elsevier B.V. All rights reserved.

The Eccentric Connectivity Polynomial of some Graph Operations

The eccentric connectivity index of a graph G, ξ^C, was proposed by Sharma, Goswami and Madan. It is defined as ξ^C(G) = ∑ u ∈ V(G) degG(u)εG(u), where degG(u) denotes the degree of the vertex x in G and εG(u) = Max{d(u, x) | x ∈ V (G)}. The eccentric connectivity polynomial is a polynomial version of this topological index. In this paper, exact formulas for the eccentric connectivity polynomial of Cartesian product, symmetric difference, disjunction and join of graphs are presented.

A quantum Jensen-Shannon graph kernel using discrete-time quantum walks

In this paper, we develop a new graph kernel by using the quantum Jensen-Shannon divergence and the discrete-time quantum walk. To this end, we commence by performing a discrete-time quantum walk to compute a density matrix over each graph being compared. For a pair of graphs, we compare the mixed quantum states represented by their density matrices using the quantum Jensen-Shannon divergence. With the density matrices for a pair of graphs to hand, the quantum graph kernel between the pair of graphs is defined by exponentiating the negative quantum Jensen-Shannon divergence between the graph density matrices. We evaluate the performance of our kernel on several standard graph datasets, and demonstrate the effectiveness of the new kernel.

A quantum Jensen-Shannon graph kernel using the continuous-time quantum walk

In this paper, we use the quantum Jensen-Shannon divergence as a means to establish the similarity between a pair of graphs and to develop a novel graph kernel. In quantum theory, the quantum Jensen-Shannon divergence is defined as a distance measure between quantum states. In order to compute the quantum Jensen-Shannon divergence between a pair of graphs, we first need to associate a density operator with each of them. Hence, we decide to simulate the evolution of a continuous-time quantum walk on each graph and we propose a way to associate a suitable quantum state with it. With the density operator of this quantum state to hand, the graph kernel is defined as a function of the quantum Jensen-Shannon divergence between the graph density operators. We evaluate the performance of our kernel on several standard graph datasets from bioinformatics. We use the Principle Component Analysis (PCA) on the kernel matrix to embed the graphs into a feature space for classification. The experimental results demonstrate the effectiveness of the proposed approach. © 2013 Springer-Verlag.

Packings and coverings of the complete graph with trees

In this thesis, we define the spectrum problem for packings (coverings) of G to be the problem of finding all graphs H such that a maximum G-packing (minimum G- covering) of the complete graph with the leave (excess) graph H exists. The set of achievable leave (excess) graphs in G-packings (G-coverings) of the complete graph is called the spectrum of leave (excess) graphs for G. Then, we consider this problem for trees with up to five edges. We will prove that for any tree T with up to five edges, if the leave graph in a maximum T-packing of the complete graph Kn has i edges, then the spectrum of leave graphs for T is the set of all simple graphs with i edges. In fact, for these T and i and H any simple graph with i edges, we will construct a maximum T-packing of Kn with the leave graph H. We will also show that for any tree T with k ≤ 5 edges, if the excess graph in a minimum T-covering of the complete graph Kn has i edges, then the spectrum of excess graphs for T is the set of all simple graphs and multigraphs with i edges, except for the case that T is a 5-star, for which the graph formed by four multiple edges is not achievable when n = 12.