The design and implementation of an interactive graphics system for graph manipulation are discussed. The activation fcr such a system is examined, and the relevant literature is described and evaluated. A number of ways to improve and extend the system are presented. The system provides the basic graph drawing operations cf adding, deleting, labeling, and changing both vertices and edges. Also included are a number of graph manipulation operations which, among ether things, allow a user to subdivide edges, associate vertices, reverse the direction cf arcs, move vertices about the screen, cr even move whole graphs about the sc teen. A facility is provided whereby the screen can te divided into as many as four regions, thus allowing users tc display more than one graph at a time. Graphs can be saved on disk and later restored. The image on the graphics screen can te easily plotted tc obtain a hard copy of graphs. A few routines which perform graph-theoretic operations have teen implemented. Among these are a routine for finding the minimum and maximum degrees of a graph, and a routine fcr finding the blocks, cutnodes, and bridges cf a graph. Moreover, the system is designed to allow users to add their own routines. / Science, Faculty of / Computer Science, Department of / Graduate

M.Sc. / This thesis is concerned with one possible interplay between commutative algebra and graph theory. Specifically, we associate with a commutative ring R a graph and then set out to determine how the ring's properties influence the chromatic and clique numbers of the graph. The graph referred to is obtained by letting each ring element be represented by a vertex in the graph and joining two vertices when the product of their corresponding ring elements is equal to zero. The thesis focuses on rings that have a finite chromatic number, where the chromatic number of the ring is equal to the chromatic number of the associated graph. The nilradical of the ring plays a prominent role in these- investigations. Furthermore, the thesis also discusses conditions under which the chromatic and clique numbers of the associated graph are equal. The thesis ends with a discussion of rings with low (< 5) chromatic number and an example of a ring with clique number 5 and chromatic number 6.

Ph.D. / Please refer to full text to view abstract

The distance-two constrained labeling of graphs arises in the context of frequency assignment problem (FAP) in mobile and wireless networks. The frequency assignment problem is the problem of assigning frequencies to the stations of a network, so that interference between nearby stations is avoided or minimized while the frequency reusability is exploited. It was first formulated as a graph coloring problem by Hale, who introduced the notion of the T-coloring of a graph, and that attracts a lot of interest in graph coloring. In 1988, Roberts proposed a variation of the channel assignment problem in which “close transmitters must receive different channels and “very close transmitters must receive channels at least two apart. Motivated by this variation, Griggs and Yeh first proposed and studied the L(2, 1)-labeling of a simple graph with a condition at distance two. Because of practical and theoretical applications, the interest for distance-two constrained labeling of graphs is increasing. Since then, many aspects of the problem and related problems remain to be further explored. In this thesis, we first give an upper bound of the L(2, 1)-labeling number, or simply λ number, for a special class of graphs, the n-cubes Qn, where n = 2k k 1. Chang et al. [3] considered a generalization of L(2, 1)-labeling, namely, L(d, 1)- labeling of graphs. We study the L(1, 1)-labeling number of Qn. A lower bound onλ1(Qn) is provided and λ1(Q2k1) is determined. As a related problem, the L(2, 1)-choosability of graphs is studied. Vizing [17] and Erdos et al. [18] generalized the graph coloring problem and introduced the list coloring problem independently more than three decades ago. We shall consider a new variation of the L(2, 1)-labeling problem, the list-L(2, 1)-labeling problem. We determine the L(2, 1)-choice numbers for paths and cycles. We also study the L(2, 1)- choosability for some special graphs such as the Cartesian product graphs and the generalized Petersen graphs. We provide upper bounds of the L(2, 1)-choice numbers for the Cartesian product of a path and a spider, also for the generalized Petersen graphs. Keywords: distance-two labeling, λ-number, L(2, 1)-labeling, L(d, 1)-labeling, list-L(2, 1)-labeling, choosability, L(2, 1)-choice number, path, cycle, n-cube, spider, Cartesian product graph, generalized Petersen graph.

No description available.

No description available.

No description available.

No description available.

Defensive alliances are a way of using graphs to model the defense of resources (people, buildings, countries, etc.) against attacks where the number of potential attackers against each resource is known. The initial study of defensive alliances focused on questions of minimal defensive alliances in a graph and the minimum possible size of a defensive alliance in a graph, but in order to apply defensive alliances in modeling real-world situations, additional considerations are important. In particular, since each vertex in a defensive alliance represents some real-world object that has a cost associated with remaining in the defensive alliance, it is important to consider the value each vertex adds to the defensive alliance. In this thesis we consider a method of assessing the efficiency of a defensive alliance, including the special case of secure sets.

Attribute-rich longitudinal datasets of any kind are extremely rare. In 2012 and 2013, the SensibleDTU project created such a dataset using approximately 1,000 university students. Since then, a large number of studies have been performed using this dataset to ask various questions about social dynamics. This thesis delves into this dataset in an effort to explore previously unanswered questions. First, we define and identify social encounters in order to ask questions about face-to-face interaction networks. Next, we isolate students who send and receive disproportionately high numbers of phone calls and text messages to see how these groups compare to the overall population. Finally, we attempt to identify individual class schedules based solely on Bluetooth scans collected by smart phones. Our results from analyzing the phone call and text message logs as well as social encounters indicate that our methods are effective in studying and understanding social behavior.