Acyclic 5-Choosability of Planar Graphs Without Adjacent Short Cycles

The conjecture claiming that every planar graph is acyclic 5-choosable[Borodin et al., 2002] has been verified for several restricted classes of planargraphs. Recently, O. V. Borodin and A. O. Ivanova, [Journal of Graph Theory,68(2), October 2011, 169-176], have shown that a planar graph is acyclically 5-choosable if it does not contain an i-cycle adjacent to a j-cycle, where 3<=j<=5 if i=3 and 4<=j<=6 if i=4. We improve the above mentioned result and prove that every planar graph without an i-cycle adjacent to a j-cycle with3<=j<=5 if i=3 and 4<=j<=5 if i=4 is acyclically 5-choosable.

Edge-choosability of Planar Graphs

According to the List Colouring Conjecture, if G is a multigraph then χ' (G)=χl' (G) . In this thesis, we discuss a relaxed version of this conjecture that every simple graph G is edge-(∆ + 1)-choosable as by Vizing’s Theorem ∆(G) ≤χ' (G)≤∆(G) + 1. We prove that if G is a planar graph without 7-cycles with ∆(G)≠5,6 , or without adjacent 4-cycles with ∆(G)≠5, or with no 3-cycles adjacent to 5-cycles, then G is edge-(∆ + 1)-choosable.

Properties and Algorithms of the KCube Graphs

The KCube interconnection topology was rst introduced in 2010. The KCube graph is a compound graph of a Kautz digraph and hypercubes. Compared with the at- tractive Kautz digraph and well known hypercube graph, the KCube graph could accommodate as many nodes as possible for a given indegree (and outdegree) and the diameter of interconnection networks. However, there are few algorithms designed for the KCube graph. In this thesis, we will concentrate on nding graph theoretical properties of the KCube graph and designing parallel algorithms that run on this network. We will explore several topological properties, such as bipartiteness, Hamiltonianicity, and symmetry property. These properties for the KCube graph are very useful to develop efficient algorithms on this network. We will then study the KCube network from the algorithmic point of view, and will give an improved routing algorithm. In addition, we will present two optimal broadcasting algorithms. They are fundamental algorithms to many applications. A literature review of the state of the art network designs in relation to the KCube network as well as some open problems in this field will also be given.

Social competence following mild head injury and moderate traumatic brain injury: Investigating the neuropsychological relationships between arousal, social decision-making and depression

Client-directed long-term rehabilitative goals and life satisfaction following head injury emphasize the importance of social inclusion, rather than cognitive or physical, outcomes. However, very little research has explored the socio-emotional factors that pose as barriers to social reintegration following injury. This study investigates social barriers following head injury (i.e., decision-making - Iowa Gambling Task [IGT] and mood – depression) and possible amelioration of those challenges (through treatment) in both highly functioning university students with and without mild head injury (MHI) and in individuals with moderate traumatic brain injury (TBI). An arousal manipulation using emotionally evocative stimuli was introduced to manipulate the subject’s physiological arousal state. Seventy-five university students (37.6% reporting a MHI) and 11 patients with documented moderate TBI were recruited to participate in this quasi-experimental study. Those with head injury were found to be physiologically underaroused (on measures of electrodermal activation [EDA] and pulse) and were less sensitive to the negative effects of punishment (i.e., losses) in the gambling task than those without head injury, with greater impairment being observed for the moderate TBI group. The arousal manipulation, while effective, was not able to maintain a higher state of arousal in the injury groups across trials (i.e., their arousal state returned to pre-manipulation levels more quickly than their non-injured cohort), and, subsequently, a performance improvement was not observed on the IGT. Lastly, head injury was found to contribute to the relationship between IGT performance and depressive symptom acknowledgment and mood status in persons with head injury. This study indicates the possible important role of physiological arousal on socio- emotional behaviours (decision-making, mood) in persons with even mild, non-complicated head injuries and across the injury severity continuum.

Educational Technology Decision-Making: A Case Study on Technology Acquisition for 746,000 Ontario Students

Very little research has examined K–12 educational technology decision-making in Canada. This collective case study explores the technology procurement process in Ontario’s publicly funded school districts to determine if it is informed by the relevant research, grounded in best practices, and enhances student learning. Using a qualitative approach, 10 senior leaders (i.e., chief information officers, superintendents, etc.) were interviewed. A combination of open-ended and closed-ended questions were used to reveal the most important factors driving technology acquisition, research support, governance procedures, data use, and assessment and return on investment (ROI) measures utilized by school districts in their implementation of educational technology. After participants were interviewed, the data were transcribed, member checked, and then submitted to “Computer-assisted NCT analysis” (Friese, 2014) using ATLAS.ti. The findings show that senior leaders are making acquisitions that are not aligned with current scholarship and not with student learning as the focus. It was also determined that districts struggle to use data-driven decision-making to support the governance of educational technology spending. Finally, the results showed that districts do not have effective assessment measures in place to determine the efficacy or ROI of a purchased technology. Although data are limited to the responses of 10 senior leaders, findings represent the technology leadership for approximately 746,000 Ontario students. The study is meant to serve as an informative resource for senior leaders and presents strategic and research-validated approaches to technology procurement. Further, the study has the potential to refine technology decision-making, policies, and practices in K–12 education.

Backbone Colouring of Graphs

Consider an undirected graph G and a subgraph of G, H. A q-backbone k-colouring of (G,H) is a mapping f: V(G) {1, 2, ..., k} such that G is properly coloured and for each edge of H, the colours of its endpoints differ by at least q. The minimum number k for which there is a backbone k-colouring of (G,H) is the backbone chromatic number, BBCq(G,H). It has been proved that backbone k-colouring of (G,T) is at most 4 if G is a connected C4-free planar graph or non-bipartite C5-free planar graph or Cj-free, j∈{6,7,8} planar graph without adjacent triangles. In this thesis we improve the results mentioned above and prove that 2-backbone k-colouring of any connected planar graphs without adjacent triangles is at most 4 by using a discharging method. In the second part of this thesis we further improve these results by proving that for any graph G with χ(G) ≥ 4, BBC(G,T) = χ(G). In fact, we prove the stronger result that a backbone tree T in G exists, such that ∀ uv ∈ T, |f(u)-f(v)|=2 or |f(u)-f(v)| ≥ k-2, k = χ(G). For the case that G is a planar graph, according to Four Colour Theorem, χ(G) = 4; so, BBC(G,T) = 4.

Using PageRank Algorithm in Analyzing Dictionary Graphs and PageRank in Dynamic Graphs

In this thesis we are going to analyze the dictionary graphs and some other kinds of graphs using the PagerRank algorithm. We calculated the correlation between the degree and PageRank of all nodes for a graph obtained from Merriam-Webster dictionary, a French dictionary and WordNet hypernym and synonym dictionaries. Our conclusion was that PageRank can be a good tool to compare the quality of dictionaries. We studied some artificial social and random graphs. We found that when we omitted some random nodes from each of the graphs, we have not noticed any significant changes in the ranking of the nodes according to their PageRank. We also discovered that some social graphs selected for our study were less resistant to the changes of PageRank.

GA approach for finding Rough Set decision rules based on bireducts

Feature selection plays an important role in knowledge discovery and data mining nowadays. In traditional rough set theory, feature selection using reduct - the minimal discerning set of attributes - is an important area. Nevertheless, the original definition of a reduct is restrictive, so in one of the previous research it was proposed to take into account not only the horizontal reduction of information by feature selection, but also a vertical reduction considering suitable subsets of the original set of objects. Following the work mentioned above, a new approach to generate bireducts using a multi--objective genetic algorithm was proposed. Although the genetic algorithms were used to calculate reduct in some previous works, we did not find any work where genetic algorithms were adopted to calculate bireducts. Compared to the works done before in this area, the proposed method has less randomness in generating bireducts. The genetic algorithm system estimated a quality of each bireduct by values of two objective functions as evolution progresses, so consequently a set of bireducts with optimized values of these objectives was obtained. Different fitness evaluation methods and genetic operators, such as crossover and mutation, were applied and the prediction accuracies were compared. Five datasets were used to test the proposed method and two datasets were used to perform a comparison study. Statistical analysis using the one-way ANOVA test was performed to determine the significant difference between the results. The experiment showed that the proposed method was able to reduce the number of bireducts necessary in order to receive a good prediction accuracy. Also, the influence of different genetic operators and fitness evaluation strategies on the prediction accuracy was analyzed. It was shown that the prediction accuracies of the proposed method are comparable with the best results in machine learning literature, and some of them outperformed it.

Diagrams (charts and graphs) made into a booklet with a newspaper cover

Diagrams (charts and graphs) made into a booklet with a newspaper cover. This booklet contains cross sections of the back ditch on the south side of the Welland Canal feeder, west of the Marshville culverts (45 pages, hand drawn). This was created by Fred Holmes, Oct. 3, 1857.

Charts and graphs of cross sections from Brown’s ditch culvert to the main drain

Charts and graphs of cross sections from Brown’s ditch culvert to the main drain, cross sections from the feeder on the road allowance between lots 26 and 27 in the 5th concession of Humberstone, Cross sections of the main drain from Lyons Creek culvert to the road allowance between lots 7 and 8 in Wainfleet and cross selections of the old ditch on the west side of the road allowance between lots 17 and 18 in the 3rd concession in Wainfleet (8 pages, hand drawn), n.d.