Réalisé avec le support financier du Conseil de recherches en sciences naturelles et en génie du Canada (CRSNG) et du Fonds de Recherche du Québec – Nature et technologies (FRQNT). / Ce mémoire étudie le jeu de policiers-voleur et contient trois articles, chacun portant sur une classe de graphes spécifique. Dans le premier chapitre, la notation et les définitions de base de la théorie de graphe qui nous serons utiles sont introduites. Bien que chaque article comporte une introduction citant les concepts et résultats pertinents, le premier chapitre de ce mémoire contient aussi une introduction générale au jeu de policiers-voleur et présente certains des résultats majeurs sur ce jeu. Le deuxième chapitre contient l’article écrit avec Seyyed Aliasghar Hosseini et Peter Bradshaw portant sur le jeu de policiers-voleurs sur les graphes de Cayley abéliens. Nous améliorons la borne supérieure sur le cop number de ces graphes en raffinant les méthodes utilisées précédemment par Hamidoune, Frankl et Bradshaw. Le troisième chapitre présente l’article concernant le cop number des graphes 2K2-libres. Plus précisément, il est prouvé que 2 policiers peuvent toujours capturer le voleur sur ces graphes, prouvant ainsi la conjecture de Sivaraman et Testa. Finalement, le quatrième chapitre est l’article écrit avec Samuel Yvon et porte sur les graphes qui ont cop number 4. Nous montrons que tous ces graphes ont au moins 19 sommets. En d’autres mots, 3 policiers peuvent toujours capturer le voleur sur tout graphe avec au plus 18 sommets, ce qui répond par la négative à une question de Andreae formulée en 1986. Un pan important de la preuve est faite par ordinateur; ce mémoire contient donc une annexe comprenant le code utilisé. / This thesis studies the game of cops and robbers and consists of three articles, each considering a specific class of graphs. In the first chapter, notation and basic definitions of graph theory are introduced. Al- though each article has an introduction citing the relevant concepts and results, the first chapter of this thesis also contains a general introduction to the game of cops and robbers and presents some of its major results. The second chapter contains the paper written with Seyyed Aliasghar Hosseini and Peter Bradshaw on the game of cops and robbers on abelian Cayley graphs. We improve the upper bound on the cop number of these graphs by refining the methods used previously by Hamidoune, Frankl and Bradshaw. The third chapter presents the paper concerning the cop number of 2K2-free graphs. More precisely, it is proved that 2 cops can always catch the robber on these graphs, proving a conjecture of Sivaraman and Testa. Finally, the fourth chapter is the paper written with Samuel Yvon which deals with graphs of cop number 4. We show that such graphs have at least 19 vertices. In other words, 3 cops can always catch the robber on any graph with at most 18 vertices, which answers in the negative a question by Andreae from 1986. An important part of the proof is by computer; this thesis thus has an appendix containing the code used.

This study examined how online social networking (OSN) leads to increased communication and collaboration across inter-firm boundaries. This online social networking behaviour represents significant opportunities to firms in the form of improved problem-solving, increased collaborative innovation and enhanced engagement with stakeholders. There are also risks inherent in the widespread use of OSNs, such as the loss of control over information flows to individuals outside the organization, potential damage to the reputation of brands and organizations, and loss of productivity due to excessive usage of OSNs during work hours. In particular, this study sought to test four research propositions, specifically, that usage of one particular OSN, LinkedIn (LI), results in: 1) an increased number of inter-firm connections; 2) an improved ability to communicate across inter-firm boundaries; 3) greater access to problem solving or innovation collaborators; 4) increased organizational problem solving or innovation ability. The study methodology involved both quantitative and qualitative research. The quantitative portion of the study involved survey research among over 500 LinkedIn (LI) users to determine changes they reported in various dimensions related to inter-firm relationship-forming, information-sharing and collaborative problem solving since using LI. The sampling approach was purposive and the sample frame consisted of the researcher’s own extended LI network, and an effort was also made to make the survey link available to all LI members through public posting in the site’s Q&A section. Though no individual or group was systematically excluded from the opportunity to take the survey, some limitations are inherent in the approach taken. The survey respondents were self-selecting, which makes it difficult to confirm that the sample is reflective of all LI users. Also, the use of the researcher’s own LI network as a key source of survey respondents may have biased the study toward more open networkers, since the researcher’s network was built up over time by practicing open networking behaviours. As a result, the sample may tend to under-represent more closed or restrictive networkers. Notwithstanding these limitations, no one particular group of respondents was excluded from the opportunity to take the survey, and the resulting data suggests that there were significant numbers of respondents who considered themselves closed networkers. Also, the spread of respondents by geographic area, occupation and age was found to resemble published statistics from LI on its user base, so it appears that the data is reasonably reflective of the LI user base, though this would be difficult to verify or measure. Qualitative research was also undertaken among senior managers at companies that have embraced the use of OSNs by staff to determine their experiences along similar dimensions. The findings from the quantitative survey showed that users of LI have experienced an increased number of social connections with individuals as a result of using LI, and that these connections are often with people in other organizations, including competitors and customers. Survey respondents also reported that they have been able to draw upon their LI networks in order to solve problems and be more innovative in their work. Analysis of the qualitative research yielded a list of suggested best practices that could be adopted by firms wishing to harness the collaborative power of OSNs. These suggested best practices have been grouped under the areas of strategy, listening, communication, guidelines, training, diffusion and measurement. Some suggested areas for future research included: the role of performance measurement and reward systems in managing OSN usage behaviour; the organizational risks of centralized versus decentralized control of messaging via OSNs; the role of training in the effective deployment of OSNs in an organizational context; and the organizational risk of increased connectedness with competitors resulting from OSN relationships. / Business Management / D.B.L.

This study examined how online social networking (OSN) leads to increased communication and collaboration across inter-firm boundaries. This online social networking behaviour represents significant opportunities to firms in the form of improved problem-solving, increased collaborative innovation and enhanced engagement with stakeholders. There are also risks inherent in the widespread use of OSNs, such as the loss of control over information flows to individuals outside the organization, potential damage to the reputation of brands and organizations, and loss of productivity due to excessive usage of OSNs during work hours. In particular, this study sought to test four research propositions, specifically, that usage of one particular OSN, LinkedIn (LI), results in: 1) an increased number of inter-firm connections; 2) an improved ability to communicate across inter-firm boundaries; 3) greater access to problem solving or innovation collaborators; 4) increased organizational problem solving or innovation ability. The study methodology involved both quantitative and qualitative research. The quantitative portion of the study involved survey research among over 500 LinkedIn (LI) users to determine changes they reported in various dimensions related to inter-firm relationship-forming, information-sharing and collaborative problem solving since using LI. The sampling approach was purposive and the sample frame consisted of the researcher’s own extended LI network, and an effort was also made to make the survey link available to all LI members through public posting in the site’s Q&A section. Though no individual or group was systematically excluded from the opportunity to take the survey, some limitations are inherent in the approach taken. The survey respondents were self-selecting, which makes it difficult to confirm that the sample is reflective of all LI users. Also, the use of the researcher’s own LI network as a key source of survey respondents may have biased the study toward more open networkers, since the researcher’s network was built up over time by practicing open networking behaviours. As a result, the sample may tend to under-represent more closed or restrictive networkers. Notwithstanding these limitations, no one particular group of respondents was excluded from the opportunity to take the survey, and the resulting data suggests that there were significant numbers of respondents who considered themselves closed networkers. Also, the spread of respondents by geographic area, occupation and age was found to resemble published statistics from LI on its user base, so it appears that the data is reasonably reflective of the LI user base, though this would be difficult to verify or measure. Qualitative research was also undertaken among senior managers at companies that have embraced the use of OSNs by staff to determine their experiences along similar dimensions. The findings from the quantitative survey showed that users of LI have experienced an increased number of social connections with individuals as a result of using LI, and that these connections are often with people in other organizations, including competitors and customers. Survey respondents also reported that they have been able to draw upon their LI networks in order to solve problems and be more innovative in their work. Analysis of the qualitative research yielded a list of suggested best practices that could be adopted by firms wishing to harness the collaborative power of OSNs. These suggested best practices have been grouped under the areas of strategy, listening, communication, guidelines, training, diffusion and measurement. Some suggested areas for future research included: the role of performance measurement and reward systems in managing OSN usage behaviour; the organizational risks of centralized versus decentralized control of messaging via OSNs; the role of training in the effective deployment of OSNs in an organizational context; and the organizational risk of increased connectedness with competitors resulting from OSN relationships. / Business Management / D.B.L.