Convex extendable trees

The concept of convex extendability is introduced to answer the problem of finding the smallest distance convex simple graph containing a given tree. A problem of similar type with respect to minimal path convexity is also discussed.

Hardness of approximation results for the problem of finding the stopping distance in Tanner graphs

Tanner Graph representation of linear block codes is widely used by iterative decoding algorithms for recovering data transmitted across a noisy communication channel from errors and erasures introduced by the channel. The stopping distance of a Tanner graph T for a binary linear block code C determines the number of erasures correctable using iterative decoding on the Tanner graph T when data is transmitted across a binary erasure channel using the code C. We show that the problem of finding the stopping distance of a Tanner graph is hard to approximate within any positive constant approximation ratio in polynomial time unless P = NP. It is also shown as a consequence that there can be no approximation algorithm for the problem achieving an approximation ratio of 2(log n)(1-epsilon) for any epsilon > 0 unless NP subset of DTIME(n(poly(log n))).

On Distance Energy of Graphs

The D-eigenvalues of a graph G are the eigenvalues of its distance matrix D, and the D-energy ED(G) is the sum of the absolute values of its D-eigenvalues. Two graphs are said to be D-equienergetic if they have the same D-energy. In this note we obtain bounds for the distance spectral radius and D-energy of graphs of diameter 2. Pairs of equiregular D-equienergetic graphs of diameter 2, on p = 3t + 1 vertices are also constructed.

ON DISTANCE ENERGY OF GRAPHS

The D-eigenvalues of a graph G are the eigenvalues of its distance matrix D, and the D-energy ED(G) is the sum of the absolute values of its D-eigenvalues. Two graphs are said to be D-equienergetic if they have the same D-energy. In this note we obtain bounds for the distance spectral radius and D-energy of graphs of diameter 2. Pairs of equiregular D-equienergetic graphs of diameter 2, on p = 3t + 1 vertices are also constructed.

Algorithms for Maximum Independent Set in Convex Bipartite Graphs

A bipartite graph G = (V, W, E) is convex if there exists an ordering of the vertices of W such that, for each v. V, the neighbors of v are consecutive in W. We describe both a sequential and a BSP/CGM algorithm to find a maximum independent set in a convex bipartite graph. The sequential algorithm improves over the running time of the previously known algorithm and the BSP/CGM algorithm is a parallel version of the sequential one. The complexity of the algorithms does not depend on |W|.

A educação a distância e a formação continuada de professores de matemática: contribuições de um contexto formativo para a base de conhecimento docente

Pós-graduação em Educação - FCT

Structuring representations of continuous data through investigations in grade 1

The study of data modelling with elementary students involves the analysis of a developmental process beginning with children’s investigations of meaningful contexts: visualising, structuring, and representing data and displaying data in simple graphs (English, 2012; Lehrer & Schauble, 2005; Makar, Bakker, & Ben-Zvi, 2011). A 3-year longitudinal study investigated young children’s data modelling, integrating mathematical and scientific investigations. One aspect of this study involved a researcher-led teaching experiment with 21 mathematically able Grade 1 students. The study aimed to describe explicit developmental features of students’ representations of continuous data...

Diagonal forms, linear algebraic methods and Ramsey-type problems

This thesis focuses mainly on linear algebraic aspects of combinatorics. Let N_t(H) be an incidence matrix with edges versus all subhypergraphs of a complete hypergraph that are isomorphic to H. Richard M. Wilson and the author find the general formula for the Smith normal form or diagonal form of N_t(H) for all simple graphs H and for a very general class of t-uniform hypergraphs H.

As a continuation, the author determines the formula for diagonal forms of integer matrices obtained from other combinatorial structures, including incidence matrices for subgraphs of a complete bipartite graph and inclusion matrices for multisets.

One major application of diagonal forms is in zero-sum Ramsey theory. For instance, Caro's results in zero-sum Ramsey numbers for graphs and Caro and Yuster's results in zero-sum bipartite Ramsey numbers can be reproduced. These results are further generalized to t-uniform hypergraphs. Other applications include signed bipartite graph designs.

Research results on some other problems are also included in this thesis, such as a Ramsey-type problem on equipartitions, Hartman's conjecture on large sets of designs and a matroid theory problem proposed by Welsh.

Development of selection methods for steels and their heat treatments

Designers who want to manufacture a hardenable steel component need to select both the steel and its heat treatment. This project aims to develop a selection methodology for steels and process routes as an aid to designers. Three studies were conducted: - production of software to calculate the "equivalent diameter" and "equivalent Jominy distance" for simple shapes of a steel component; - prediction of semi-empirical Jominy curves (as-cooled) using CCT diagrams and process modelling methods, which were validated by experiment on plain carbon steels; - investigation of tempering of Jominy bars to explore the potential for semi-empirical models for the hardness after tempering.

Using Graph Components Derived from an Associative Concept Dictionary to Predict fMRI Neural Activation Patterns that Represent the Meaning of Nouns

In this study, we introduce an original distance definition for graphs, called the Markov-inverse-F measure (MiF). This measure enables the integration of classical graph theory indices with new knowledge pertaining to structural feature extraction from semantic networks. MiF improves the conventional Jaccard and/or Simpson indices, and reconciles both the geodesic information (random walk) and co-occurrence adjustment (degree balance and distribution). We measure the effectiveness of graph-based coefficients through the application of linguistic graph information for a neural activity recorded during conceptual processing in the human brain. Specifically, the MiF distance is computed between each of the nouns used in a previous neural experiment and each of the in-between words in a subgraph derived from the Edinburgh Word Association Thesaurus of English. From the MiF-based information matrix, a machine learning model can accurately obtain a scalar parameter that specifies the degree to which each voxel in (the MRI image of) the brain is activated by each word or each principal component of the intermediate semantic features. Furthermore, correlating the voxel information with the MiF-based principal components, a new computational neurolinguistics model with a network connectivity paradigm is created. This allows two dimensions of context space to be incorporated with both semantic and neural distributional representations.

Matlab self study tutorial - Graphing

These resources are designed to support students in gaining more confidence with using Matlab. The PDFs provide guidance and information; Objectives: Introduce basic syntax and data preparation for graphing with Matlab by providing some data, examples of code and some background documents. Outcomes: -how to write an m file script -the importance of syntax -how to load files -how to produce simple graphs -where to get help and further examples There are also some data files to provide example data for students to work with in producing Matlab resources.

Weighted alpha-rate dominating sets in social networks

We are looking into variants of a domination set problem in social networks. While randomised algorithms for solving the minimum weighted domination set problem and the minimum alpha and alpha-rate domination problem on simple graphs are already present in the literature, we propose here a randomised algorithm for the minimum weighted alpha-rate domination set problem which is, to the best of our knowledge, the first such algorithm. A theoretical approximation bound based on a simple randomised rounding technique is given. The algorithm is implemented in Python and applied to a UK Twitter mentions networks using a measure of individuals’ influence (klout) as weights. We argue that the weights of vertices could be interpreted as the costs of getting those individuals on board for a campaign or a behaviour change intervention. The minimum weighted alpha-rate dominating set problem can therefore be seen as finding a set that minimises the total cost and each individual in a network has at least alpha percentage of its neighbours in the chosen set. We also test our algorithm on generated graphs with several thousand vertices and edges. Our results on this real-life Twitter networks and generated graphs show that the implementation is reasonably efficient and thus can be used for real-life applications when creating social network based interventions, designing social media campaigns and potentially improving users’ social media experience.

Effects of shape Rosmarinus officinalis neighbors on resprouting of shape Erica multiflora individuals

To study the effects of competition in Mediterranean shrubland regeneration following disturbance, we used a neighborhood approach to assess the influence of mature Rosmarinus officinalis neighbors on the resprouting of Erica multiflora individuals after clipping. Sprout biomass of target plants 2 years after clipping was regressed against various measures of neighbor abundance within a 2 m radius around target E. multiflora individuals in which all vegetation except R. officinalis had been removed. The largest single influence on the biomass of sprouts produced was the previous biomass of the resprouting plant. The abundance of R. officinalis neighbors had a weak but detectable effect on resprouting of E. multiflora. Abundance of neighbors within 60 cm from target plants was the best predictor of regrowth. At this distance, two simple measures of neighbor abundance within the neighborhood, the number of neighbors and the sum of their heights, were significant in accounting for variation in resprouted biomass. None of the combinations of neighbor variables performed significantly better than single variables. The best models accounted for around 24 percent of the variation in resprout biomass. As in other studies, angular dispersion of neighbors never had a significant effect on performance of target plants. The weak but significant response of resprouting to variation in R. officinalis abundance suggests that the intensity of competition in the experiment was low because of the removal of other species.