Das Gewicht einer Kante e = xy eines Graphen G = (V, E) ist definiert als Summe der Grade seiner Endpunkte und das Gewicht des Graphen als MInimum über alle Kantengewichte. Wir suchen für positive ganze Zahlen n,m und eine Grapheneigenschaft P den Wert: w(n,m, P) := max{w(G) : |V(G)| = n, |E(G)| = m,G in P}. Der ungarische Mathematiker Erdös formulierte 1990 auf dem Czecheslovak Symposium on Combinatorics, Graphs and Complexity die Problemstellung w(n,m, I) zu bestimmen, für die allgemeinste aller Graphenklassen I. Dieses Problem wurde zuerst teilweise von Invančo and Jendrol’ und dann endgültig von Jendrol’ and Schiermeyer gelöst. Sei G in der Graphenklasse C genau dann wenn G zusammenhängend ist. In dieser Arbeit werden Ansätze zur Bestimmung von w(n,m,C) vorgestellt. Im Speziellen betrachten wir Graphen mit bis zu 3n − 6 Kanten, sowie sehr dichte Graphen. Außerdem diskutieren wir einige verallgemeinerte Fragestellungen.

In this dissertation, a problem related to Hadwiger's conjecture has been studied. We first proved a conjecture of Jakobsen from 1983 which states that every simple graphs on $n$ vertices and at least (11n-35)/2 edges either has a minor isomorphic to K_8 with one edge deleted or is isomorphic to a graph obtained from disjoint copies of K_{1, 2, 2, 2, 2} and/or K_7 by identifying cliques of size five. We then studied the extremal functions for complete minors. We proved that every simple graph on nge9 vertices and at least 7n-27 edges either has a minor, or is isomorphic to K_{2, 2, 2, 3, 3}, or is isomorphic to a graph obtained from disjoint copies of K_{1, 2, 2, 2, 2, 2} by identifying cliques of size six. This result extends Mader's theorem on the extremal function for K_p minors, where ple7. We discussed the possibilities of extending our methods to K_{10} and K_{11} minors. We have also found the extremal function for K_7 plus a vertex minor.

In the process of urbanization, the population and economy are rapidly growing. To achieve the demand of urbanization, natural areas are developed into construction areas in the city. Nature areas began to shrink and fragment, causing a great deal of damage, such as species extinction. The ability of nature to control the flood, adjust the rain, and filter pollution has been lost. This study is based on the city of Kaohsiung and Kaohsiung County. The study uses a large scale to re-examine the spatial structure of this area to propose an effective and reasonable planning policy for the environment and ecosystem. The study introduces the concept of green infrastructure to develop a green network system for the city. Green infrastructure is a network connecting natural areas and open spaces that can save ecological value and retain the ecosystem function. A green infrastructure network consists of hubs and links, and the network pattern can be made for different purposes. The study chose green land with an area of more than twenty hectares for the hubs and chose the terrestrial animal for the target species. The study uses the least-cost path analysis to plan the links for the terrestrial animal. The least-cost path, which is the path of least resistance when the terrestrial animal passes through the landscape. All the hubs generated 903 links. To create the green infrastructure networks, this study uses the gravity model to evaluate which corridor is the most important. Using the graph theory, the study developed three plans for a green infrastructure network to meet different demands: the Paul Revere, Traveling Salesman, and Least Cost to User networks. Planners can see different demands dictating the choice between different green infrastructure networks. Finally, the study discusses the three-network structure, finding the important hubs and links for the terrestrial animal. These areas should be protected to maintain the green infrastructure network.

Power industry is undergoing a transition from the traditional regulated environment to the competitive power market. To have a reliable state estimator (SE) in the power market environment, two major challenges are emerging, i.e. to keep SE running reliably even under a contingency and to run SE over a grid with extremely large size. The objective of this dissertation is to use graph theory to address the above two challenges. To keep SE running reliably under a contingency, a novel topological approach is first proposed to identify critical measurements and examine network observability under a contingency. To advance the classical topological observability analysis, a new concept of contingency observability graph (COG) is introduced and it is proven that a power system network maintains its observability under a contingency if and only if its COG satisfies some conditions. As an application of COG, a two-stage heuristic topological approach is further developed based on the new concept of qualified COG (QCOG) to minimize the number of measurements and RTUs under the constraint that the system remains observable under any single contingency. To overcome the disadvantages of existing SE over extremely large networks, a textured distributed state estimator (DSE), which consists of the off-line textured architecture design and the on-line textured computation, is proposed based on COG and a new concept of Bus Credibility Index (BCI). The textured DSE is non-recursive, asynchronous and avoids central controlling node. Numerical tests verify that the performance of the new textured DSE algorithm improves greatly compared with existing DSE algorithms in respect of bad data detection and identification. Furthermore, the software implementation for DSE is formulated as an information integration problem over regional power markets, and is very challenging because of its size and complexity. A new concept of semantic knowledge warehouse (SKW), together with the proposed concepts of semantic reasoning software component (SRSC) and deduction credibility, is developed to implement such an information integration system.

We consider several related problems arising in geometric graphs. In particular, we investigate the computational complexity and approximability properties of several optimization problems in unit ball graphs and develop algorithms to find exact and approximate solutions. In addition, we establish complexity-based theoretical justifications for several greedy heuristics. Unit ball graphs, which are defined in the three dimensional Euclidian space, have several application areas such as computational geometry, facility location and, particularly, wireless communication networks. Efficient operation of wireless networks involves several decision problems that can be reduced to well known optimization problems in graph theory. For instance, the notion of a \virtual backbone" in a wire- less network is strongly related to a minimum connected dominating set in its graph theoretic representation. Motivated by the vastness of application areas, we study several problems including maximum independent set, minimum vertex coloring, minimum clique partition, max-cut and min-bisection. Although these problems have been widely studied in the context of unit disk graphs, which are the two dimensional version of unit ball graphs, there is no established result on the complexity and approximation status for some of them in unit ball graphs. Furthermore, unit ball graphs can provide a better representation of real networks since the nodes are deployed in the three dimensional space. We prove complexity results and propose solution procedures for several problems using geometrical properties of these graphs. We outline a matching-based branch and bound solution procedure for the maximum k-clique problem in unit disk graphs and demonstrate its effectiveness through computational tests. We propose using minimum bottleneck connected dominating set problem in order to determine the optimal transmission range of a wireless network that will ensure a certain size of "virtual backbone". We prove that this problem is NP-hard in general graphs but solvable in polynomial time in unit disk and unit ball graphs. We also demonstrate work on theoretical foundations for simple greedy heuristics. Particularly, similar to the notion of "best" approximation algorithms with respect to their approximation ratios, we prove that several simple greedy heuristics are "best" in the sense that it is NP-hard to recognize the gap between the greedy solution and the optimal solution. We show results for several well known problems such as maximum clique, maximum independent set, minimum vertex coloring and discuss extensions of these results to a more general class of problems. In addition, we propose a "worst-out" heuristic based on edge contractions for the max-cut problem and provide analytical and experimental comparisons with a well known "best-in" approach and its modified versions.

This dissertation studies the causes and mechanism of power system cascading outages and proposes the improved interactive scheme between system-wide and local levels of monitoring and control to quickly detect, classify and mitigate the cascading outages in power system. A novel method for evaluating the vulnerability of individual components as well as the whole power system, which is named as weighted vulnerability analysis, is developed. Betweenness centrality is used to measure the importance of each bus and transmission line in the modeled power system network, which is in turn used to determine the weights for the weighted vulnerability index. It features fast reaction time and achieves higher accuracy when dealing with the cascading outage detection, classification and mitigation over the traditional methods. The overload problem due to power flow redistribution after one line tripped is a critical factor contributing to the cascading outages. A parallel corridor searching method is proposed to quickly identify the most vulnerable components after tripping a transmission line. The power system topology model can be simplified into state graph after searching the domains for each generator, the commons for each bus, and links between the commons. The parallel corridor will be determined by searching the links and commons in system topology graph for the given state of power system operation. During stressed operating state, either stable or unstable power swing may have impacts on distance relay judgment and lead to relay misoperation, which will result in the power system lines being tripped and as a consequence power system operating state becoming even more stressful. At the local level, an enhanced fault detection tool during power system swing is developed to reduce the chance of relay misoperation. Comprehensive simulation studies have been implemented by using the IEEE 39-bus and 118-bus test systems. The results are promising because: The results from weighted vulnerability analysis could provide better system situational awareness and accurate information about the disturbance; The results form parallel corridor search method could identify the most vulnerable lines after power re-distribution, which will give operator time to take remedial actions; The results from new travelling wave and wavelet transform based fault detection could reduce the impact of relay misoperation.

Many interacting complex systems in biology, in physics, in technology and social systems, can be represented in a form of large networks. These large networks are mathematically represented by graphs. A graph is represented usually by the adjacency or the Laplacian matrix. Important features of the underlying structure and dynamics of them can be extracted from the analysis of the spectrum of the graphs. Spectral analysis of the so called normalized Laplacian of large networks became popular in the recent years. The Laplacian matrices of the empirical networks are in form of unstructured large sparse matrices. The aim of this thesis is the comparison of different eigenvalue solvers for large sparse symmetric matrices which arise from the graph theoretical epresentation of undirected networks. The spectrum of the normalized Laplacian is in the interval [0 2] and the multiplicity of the eigenvalue 1 plays a particularly important role for the network analysis. Moreover, the spectral analysis of protein-protein interaction networks has revealed that these networks have a different distribution type than other model networks such as scale free networks. In this respect, the eigenvalue solvers implementing the well-known implicitly restarted Arnoldi method, Lanczos method, Krylov-Schur and Jacobi Davidson methods are investigated. They exist as MATLAB routines and are included in some freely available packages. The performances of different eigenvalue solvers PEIG, AHBEIGS, IRBLEIGS, EIGIFP, LANEIG, JDQR, JDCG in MATLAB and the library SLEPc in C++ were tested for matrices of size between 100-13000 and are compared in terms of accuracy and computing time. The accuracy of the eigenvalue solvers are validated for the Paley graphs with known eigenvalues and are compared for large empirical networks using the residual plots and spectral density plots are computed.

This dissertation has two principal components: the dimension of posets with planar cover graphs, and the cartesian product of posets whose cover graphs have hamiltonian cycles that parse into symmetric chains. Posets of height two can have arbitrarily large dimension. In 1981, Kelly provided an infinite sequence of planar posets that shows that the dimension of planar posets can also be arbitrarily large. However, the height of the posets in this sequence increases with the dimension. In 2009, Felsner, Li, and Trotter conjectured that for each integer h at least 2, there exists a least positive integer c(h) so that if P is a poset with a planar cover graph (the class of posets with planar cover graphs includes the class of planar posets) and the height of P is h, then the dimension of P is at most c(h). In the first principal component of this dissertation we prove this conjecture. We also give the best known lower bound for c(h), noting that this lower bound is far from the upper bound. In the second principal component, we consider posets with the Hamiltonian Cycle--Symmetric Chain Partition (HC-SCP) property. A poset of width w has this property if its cover graph has a hamiltonian cycle which parses into w symmetric chains. This definition is motivated by a proof of Sperner's theorem that uses symmetric chains, and was intended as a possible method of attack on the Middle Two Levels Conjecture. We show that the subset lattices have the HC-SCP property by showing that the class of posets with the strong HC-SCP property, a slight strengthening of the HC-SCP property, is closed under cartesian product with a two-element chain. Furthermore, we show that the cartesian product of any two posets from this strong class has the (weak) HC-SCP property.

NASA's current plans for human spaceflight include an evolutionary series of missions based on a steady increase in capability to explore cis-lunar space, the Moon, near-Earth asteroids, and eventually Mars. Although the system architecture definition has the greatest impact on the eventual performance and cost of an exploration program, selecting an optimal architecture is a difficult task due to the lack of methods to adequately explore the architecture design space and the resource-intensive nature of architecture analysis. This research presents a modeling framework to mathematically represent and analyze the space system architecture design space using graph theory. The framework enables rapid exploration of the design space without the need to limit trade options or the need for user interaction during the exploration process. The architecture design space for three missions in a notional evolutionary exploration program, which includes staging locations, vehicle implementation, and system functionality, for each mission destination is explored. Using relative net present value of various system architecture options, the design space exploration reveals that the launch vehicle selection is the primary driver in reducing cost, and other options, such as propellant type, staging location, and aggregation strategy, provide less impact.

Thesis (M.S.) in Spatial Information Science and Engineering--University of Maine, 2009. / Includes vita. Includes bibliographical references (leaves 94-96).