Thesis (M.S.)--Rochester Institute of Technology, 2006. / Typescript. Includes bibliographical references (leaves 63-72).

Thesis (Ph.D.)--Hong Kong University of Science and Technology, 2007. / Includes bibliographical references (leaves 90-92). Also available in electronic version.

Thesis (Ph.D.)--Hong Kong University of Science and Technology, 2007. / Includes bibliographical references (leaves 99-109). Also available in electronic version.

Thesis (Ph. D.)--West Virginia University, 2007. / Title from document title page. Document formatted into pages; contains vi, 49 p. : ill. Includes abstract. Includes bibliographical references (p. 45-49).

The prevalence of graph-structured data in modern real-world applications has led to a rejuvenation of research on graph data management and analytics. Several database query languages have been proposed for textually querying graph databases. Unfortunately, formulating a graph query using any of these query languages often demands considerable cognitive effort and requires "programming" skill at least similar to programming in SQL. Yet, in a wide spectrum of graph applications consumers need to query graph data but are not proficient query writers. Hence, it is important to devise intuitive techniques that can alleviate the burden of query formulation and thus increase the usability of graph databases. In this dissertation, we take the first step to study the graph query autocompletion problem. We provide techniques that take a user's graph query as input and generate top-k query suggestions as output, to help to alleviate the verbose and error-prone graph query formulation process in a visual environment. Firstly, we study visual query autocompletion for graph databases. Techniques for query autocompletion have been proposed for web search and XML search. However, a corresponding capability for graph query engine is in its infancy. We propose a novel framework for graph query autocompletion (called AutoG). The novelties of AutoG are as follows: First, we formalize query composition that specifies how query suggestions are formed. Second, we propose to increment a query with the logical units called c-prime features, that are (i) frequent subgraphs and (ii) constructed from smaller c-prime features in no more than c ways. Third, we propose algorithms to rank candidate suggestions. Fourth, we propose a novel index called feature DAG (FDAG) to further optimize the ranking. Secondly, we propose user focus-based graph query autocompletion. AutoG provides suggestions that are formed by adding subgraph increments to arbitrary places of an existing user query. However, humans can only interact with a small number of recent software artifacts in hand. Hence, many such suggestions could be irrelevant. We present the GFocus framework that exploits a novel notion of user focus of graph query formulation. Intuitively, the focus is the subgraph that a user is working on. We formulate locality principles to automatically identify and maintain the focus. We propose novel monotone submodular ranking functions for generating popular and comprehensive query suggestions only at the focus. We propose efficient algorithms and an index for ranking the suggestions. Thirdly, we propose graph query autocompletion for large graphs. Graph features that have been exploited in AutoG are either absent or rare in large graphs. To address this, we present Flexible graph query autocompletion for LArge Graphs, called FLAG. We propose wildcard label for query graph and query suggestions. In particular, FLAG allows augmenting users' queries using subgraph increments with wildcard labels, which summarize query suggestions that have similar increment structures but different labels. We propose an efficient ranking algorithm and a novel index, called Suggestion Summarization DAG (SSDAG), to optimize the online suggestion ranking. Detailed problem analysis and extensive experimental studies consistently demonstrate the effectiveness and robustness of our proposed techniques in a broad range of settings.

A graph is planar if it can be drawn on the plane with vertices at unique locations and no edge intersections. Due to the wealth of interest from the computer science community, there are a number of remarkable but complex O(n) planar embedding algorithms. This dissertation presents a new method for O(n) planar graph embedding which avoids some of the complexities of previous approaches. The PC-tree method of Shih and Hsu has similarities to our algorithm, but the formulation is incorrect and not O(n) for reasons discussed in this dissertation. Our planarity algorithm operates directly on an adjacency list representation of a collection of planar biconnected components, adding one edge at a time to the embedding until the entire graph is embedded or until a non-planarity condition arises. If the graph is not planar, a new O(n) algorithm is presented that simplifies the extraction of a Kuratowski subgraph (a subgraph homeomorphic to [special characters omitted]). The results are then extended to outerplanar graphs, which are planar graphs that can be embedded with every vertex along the external face. In linear time, the algorithms find an outerplanar embedding or a minimal obstructing subgraph homeomorphic to [special characters omitted]. Finally, modifications to the outerplanarity and planarity obstruction isolators are presented, resulting in O(n) methods for identifying a subgraph homeomorphic to [special characters omitted]. / Graduate

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.

Chapter I begins with a brief history of the topic of greatest common subgraphs. Then we provide a summaiy of the work done on some variations of greatest common subgraphs. Finally, in this chapter we present results previously obtained on greatest common divisors and least common multiples of graphs. In Chapter II the concepts of prime graphs, prime divisors of graphs, and primeconnected graphs are presented. We show the existence of prime trees of any odd size and the existence of prime-connected trees that are not prime having any odd composite size. Then the number of prime divisors in a graph is studied. Finally, we present several results involving the existence of graphs whose size satisfies some prescribed condition and which contains a specified number of prime divisors. Chapter III presents properties of greatest common divisors and least common multiples of graphs. Then graphs with a prescribed number of greatest common divisors or least common multiples are studied. In Chapter IV we study the sizes of greatest common divisors and least common multiples of specified graphs. We find the sizes of greatest common divisors and least common multiples of stars and that of stripes. Then the size of greatest common divisors and least common multiples of paths and complete graphs are investigated. In particular, the size of least common multiples of paths versus K3 or K4 are determined. Then we present the greatest common divisor index of a graph and we determine this parameter for several classes of graphs. iii In Chapter V greatest common divisors and least common multiples of digraphs are introduced. The existence of least common mutliples of two stars is established, and the size of a least common multiple is found for several pairs of stars. Finally, we present the concept of greatest common divisor index of a digraph and determine it for several classes of digraphs. iv / Mathematical Sciences / Ph. D. (Mathematical sciences)

Ph.D. / In Chapter 1 we will give a brief historical account of domination theory and define the necessary concepts which we use in the remainder of the thesis. In Chapter 2 we establish a lower bound for the minus k-subdomination number of trees and characterize those trees which achieve this lower bound. We also compute the value of Yks-101 for comets and for cycles. We then show that the decision problem corresponding to the computation of Yks-101 is NP-complete, even for bipartite graphs. In Chapter 3 we characterize those trees T which achieve the lower bound of Cockayne and Mynhardt, thus generalizing the results of [11] and [2]. We also compute Yks-11 for comets and cycles. In Chapter 4 we study the partial signed domination number of a graph. In particular, we establish a lower bound on Yc/d for regular graphs and prove that the decision problem corresponding to the computation of the partial signed domination number is NP-complete. Chapter 5 features the minus bondage number b- (G) of a nonempty graph G, which is defined as the minimum cardinality of a set of edges whose removal increases the minus domination number of G. We show that the minus bondage and ordinary bondage numbers of a graph are incomparable. Exact values for certain well known classes of graphs are computed and an upper bound for b- is given for trees. Finally, we show that the decision problem corresponding to the computation of b- is N P - hard, even for bipartite graphs. We conclude, in Chapter 6, by discussing possible directions for future research.

Let μ be an eigenvalue of the graph G with multiplicity k. A star set corresponding to μ in G is a subset of V(G) such that [x] = k and μ is not an eigenvalue of G - X. It is always the case that the vertex set of G can be partitioned into star sets corresponding to the distinct eigenvalues of G. Such a partition is called a star partition. We give some examples of star partitions and investigate the dominating properties of the set V (G) \ X when μ ε {-I, a}. The induced subgraph H = G - X is called a star complement for μ in G. The Reconstruction Theorem states that for a given eigenvalue μ of G, knowledge of a star complement corresponding to μ, together with knowledge of the edge set between X and its complement X, is sufficient to reconstruct G. Pursuant to this we explore the idea that the adjacencies of pairs of vertices in X is determined by the relationship between the H-neighbourhoods of these vertices. We give some new examples of cubic graphs in this context. For a given star complement H the range of possible values for the corresponding eigenvalue μ is constrained by the condition that μ must be a simple eigenvalue of some one-vertex extension of H, and a double eigenvalue of some two-vertex extension of H. We apply the Reconstruction Theorem to the generic form of a two-vertex extension of H, thereby obtaining sufficient information to construct a graph containing H as a star complement for one of the possible eigenvalues. We give examples of graph characterizations arising in the case where the star complement is (to within isolated vertices) a complete bipartite graph.