No description available.

A Spanning tree of a graph G is a subgraph that is a tree which concludes all of the vertices of G. And a graph G is bipartite if the vertex set of G can be partitioned in to two sets A and B, such that every edge of G joins a vertex of A and a vertex of B. We can see that every tree(including spanning tree) is bipartite. We define type of a spanning tree using this idea as follows: We divide vertices of a spanning trees in to two partitions A and B by using its bipartition. Then, we define type of the spanning tree by (| A |, | B |), provided | A | less than or equal to | B |. We first identify the characteristics for a graph to have a spanning trees of a certain type. Then, implement some theorems about the type.

Doctor of Philosophy / Department of Mathematics / Nathan Albin / The concept of discrete $p$-modulus provides a general framework for understanding arbitrary families of objects on a graph. The $p$-modulus provides a sense of ``structure'' of the underlying graph, with different families of objects leading to different insight into the graph's structure. This dissertation builds on this idea, with an emphasis on the family of spanning trees and the underlying graph structure that spanning tree modulus exposes. This dissertation provides a review of the probabilistic interpretation of modulus. In the context of spanning trees, this interpretation rephrases modulus as the problem of choosing a probability mass function on the spanning trees so that two independent, identically distributed random spanning trees have expected overlap as small as possible. A theoretical lower bound on the expected overlap is shown. Graphs that attain this lower bound are called homogeneous and have the property that there exists a probability mass function that gives every edge equal likelihood to appear in a random tree. Moreover, any nonhomogeneous graph necessarily has a homogeneous subgraph (called a homogeneous core), which is shown to split the modulus problem into two smaller subproblems through a process called deflation. Spanning tree modulus and the process of deflation establish a type of hierarchical structure in the underlying graph that is similar to the concept of core-periphery structure found in the literature. Using this, one can see an alternative way of decomposing a graph into its hierarchical community components using homogeneous cores and a related concept: minimum feasible partitions. This dissertation also introduces a simple greedy algorithm for computing the spanning tree modulus that utilizes any efficient algorithm for finding minimum spanning trees. A theoretical proof of the convergence rate is provided, along with computational examples.

A network is a system that involves movement or flow of some commodities such as goods and services. In fact any structure that is in the form of a system of components some of which interact can be considered as a network. In network design the problem is often to construct economical and reliable networks which satisfy certain requirements and which are optimal according to some criterion such as cost, output or performance. Graph theory is useful when the requirements of the network can be expressed in terms of graph parameters, usually as bounds. Some of the graph parameters that have been considered include: degree; distance; diameter; and connectivity. Problems with these parameter restrictions are usually from a class of NP-complete problems with instances that require exponential computer time to solve by available algorithms.The major focus of this thesis is to develop fast and efficient heuristics for some of these NP-complete problems. The two main topics analysed are Restricted Spanning Trees and Graph Partitioning. The aim of the Restricted Spanning Trees section is to construct the most efficient spanning tree (connected network) subject to various degree constraints. These degree constraints imposed are usually in the form of an upper bound. The upper bound represents the maximum number of connections allowed on a particular vertex. The Graph Partitioning section considers the problem of clustering vertices of the graph into sets such that the overall cost of the edges in the different sets is minimised.Chapter 1 provides the notation and terminology used throughout the thesis and a review and summary of the thesis.A literature review of related work that has been carried out to date is presented in Chapter 2. Some of the more promising results are discussed. The first part of the chapter surveys work related to the Restricted Spanning Tree problem. ++ / Analysis of both exact and heuristic methods is given. The second part of Chapter 2 provides a survey of the Graph Partitioning problem. We discuss the many different approaches that have been proposed to solve this problem. The quality of computational results achieved is discussed.Chapter 3 considers the Degree Constraint Minimum Weight Spanning Tree problem. This problem arises in networks where a given terminal is only allowed connections to a maximum number of specified terminals. We consider a number of cases including: same degree constraint on each vertex; different degree constraint on some vertices; and when the degree constraint is only on one or two vertices. A number of heuristics are developed and implemented and compared against an exact Branch and Cut algorithm. Our computational results demonstrated the value of our better performing heuristics.Chapter 4 considers the complexity of the (1,k)-tree problem. This problem is defined m given a graph G with maximum degree k find a spanning tree T with all vertices having degree 1 or k. Analysis is done on graphs with maximum degree 3, 4 and 5. Results establishing that the (1,3)-tree and (1, 4)-tree problems are NP-complete are presented. Further consideration is also given to the complexity of spanning trees with degree from the set { 1, 3, 5}. Analysis is also carried out on the number of degree one vertices in the (1, k)-tree. Presentation of heuristic procedures to solve this NP-complete problem concludes the chapter.Chapter 5 is devoted to the Graph Partitioning problem. A number of heuristics are presented and extensive computational work carried out. Computational findings support the usefulness of the heuristic methods both in terms of quality and time.We conclude this thesis by detailing some future work that can be carried out.

No description available.

In this report, we study the enumeration of spanning trees in graphs, using two methods withinlinear algebra, Kirchhoff’s Matrix Tree Theorem and an alternative method, also referred to asLemma 1, derived by S. Klee and M.T Stamps in [KS20]. Along with introducing preliminary tools from linear algebra, we also study the Laplace matrix ofa graph and use its properties in the two methods to derive combinatorical expressions on spanningtree enumeration of different graph families. We discuss properties of the Laplace matrix obtainedfrom different graph structures, and determine which method is more suitable in each case, withrespect to linear algebra. Specifically, complete graphs, Ferrers graphs and Windmill graphs areconsidered.

Against the background of principal-agent and transaction-cost theoretical considerations, this study addresses the question whether relational competencies relate to trust within cooperative relationships, taking into account also situational and personal factors. In its conclusion, the study presents an experimentally confirmed model (n = 282) that shows the strong causal relationship between relational competencies and trust allowing boundary-spanning agents to exert influence on the development and maintenance of complex cooperative relationships characterized by long-term objectives.

No description available.

Real Estate Investment Trusts is suggested as an attractive addition to mixed-asset portfolio. This study develops several hypothesized portfolio and tests whether REITs can actually increase diversification benefits of investors. We use mean-variance spanning test by Kan and Zhou (2008) to examine whether adding a REITs into portfolio can significantly expand efficient frontier in either global minimum variance portfolio or tangency portfolio. We assume our investors hold portfolio in the four markets, namely Japan, Singapore, Taiwan and US markets for period from March 2005 to February 2008. Three hypotheses are tested under various assumed conditions. The first hypothesis, which is REITs can provide diversification benefit, is confirmed in all these four markets. In addition, we find, for Taiwan domestic investors, holding international REITs in their portfolio rather than only Taiwan¡¦s REITs will provide more diversification benefit. The second hypothesis, which is holding period will affect diversification benefit, is not supported. However, this could be resulted from a test of short period in this study. The final hypothesis, which is different investment portfolio will affect the diversification benefit of RETIs for Taiwan domestic investors, is confirmed. Our results also suggest that expanding of efficient frontier are mainly from global minimum variance portfolio rather than tangency portfolio.

Thesis (M.Sc.). / Written for the School of Computer Science. Title from title page of PDF (viewed 2008/01/15). Includes bibliographical references.