Graphs are powerful tools for a wide range of real applications, from Biological and Chemical Databases, Social Networks, Citation Networks to Knowledge Bases. Large graph data repositories have been consistently found in recent applications. Due to the high complexity of graph queries, e.g., NP-Completeness of subgraph query, and the lack of IT expertise, hosting efficient graph query services for the owners of graph data has been a technically challenging task. And hence, they may prefer to outsource their services to third-party service providers (SPs) for scalability, elasticity and efficiency. Unfortunately, SPs may not always be trusted. Security, typically the integrity and confidentiality, of the data, has been recognized as one of the critical attributes of Quality of Services (QoS). This directly influences the willingness of both data owners and query clients to use SP’s services. To address these concerns, this thesis proposes novel techniques to solve both authentication-aware and privacy-aware subgraph query. Firstly, we study authenticated subgraph query services (Chapter 3). To support the service, we propose Merkle IFTree (MIFTree) where Merkle hash trees are applied into our Intersection-aware Feature-subgraph Tree (IFTree). IFTree aims to minimize I/O in a well-received subgraph query paradigm namely the filtering-and-verification framework. The structures required to be introduced to verification objects (VOs) and the authentication time are minimized. Subsequently, the overall response time is minimized. For optimizations, we propose an enhanced authentication method on MIFTree. Secondly, we propose structure-preserving subgraph query services (Chapter 4). A crucial step of this part is to transform the seminal subgraph isomorphism algorithm (the Ullmann’s algorithm) into a series of matrix operations. We propose a novel cyclic group based encryption (CGBE) method for private matrix operations. We propose a protocol that involves the query client and static indexes for optimizations. We prove that the structural information of both query graph and data graph are preserved under CGBE and analyze the privacy preservation in the presence of the optimizations. Thirdly, we propose asymmetric structure-preserving subgraph query processing (Chapter 5), where the data graph is publicly known and the query structure/topology is kept secret. Unlike other previous methods for subgraph queries, this part proposes a series of novel optimizations that only exploit graph structures, not the queries. Further, we propose a robust query encoding and adopt our proposed cyclic group based encryption method, so that the query processing can be transformed into a series of private matrix operations and performed securely. The effectiveness and efficiency of all the techniques presented in this thesis are experimentally evaluated with both real-world and synthetic dataset

abstract: A tiling is a collection of vertex disjoint subgraphs called tiles. If the tiles are all isomorphic to a graph $H$ then the tiling is an $H$-tiling. If a graph $G$ has an $H$-tiling which covers all of the vertices of $G$ then the $H$-tiling is a perfect $H$-tiling or an $H$-factor. A goal of this study is to extend theorems on sufficient minimum degree conditions for perfect tilings in graphs to directed graphs. Corrádi and Hajnal proved that every graph $G$ on $3k$ vertices with minimum degree $delta(G)ge2k$ has a $K_3$-factor, where $K_s$ is the complete graph on $s$ vertices. The following theorem extends this result to directed graphs: If $D$ is a directed graph on $3k$ vertices with minimum total degree $delta(D)ge4k-1$ then $D$ can be partitioned into $k$ parts each of size $3$ so that all of parts contain a transitive triangle and $k-1$ of the parts also contain a cyclic triangle. The total degree of a vertex $v$ is the sum of $d^-(v)$ the in-degree and $d^+(v)$ the out-degree of $v$. Note that both orientations of $C_3$ are considered: the transitive triangle and the cyclic triangle. The theorem is best possible in that there are digraphs that meet the minimum degree requirement but have no cyclic triangle factor. The possibility of added a connectivity requirement to ensure a cycle triangle factor is also explored. Hajnal and Szemerédi proved that if $G$ is a graph on $sk$ vertices and $delta(G)ge(s-1)k$ then $G$ contains a $K_s$-factor. As a possible extension of this celebrated theorem to directed graphs it is proved that if $D$ is a directed graph on $sk$ vertices with $delta(D)ge2(s-1)k-1$ then $D$ contains $k$ disjoint transitive tournaments on $s$ vertices. We also discuss tiling directed graph with other tournaments. This study also explores minimum total degree conditions for perfect directed cycle tilings and sufficient semi-degree conditions for a directed graph to contain an anti-directed Hamilton cycle. The semi-degree of a vertex $v$ is $min{d^+(v), d^-(v)}$ and an anti-directed Hamilton cycle is a spanning cycle in which no pair of consecutive edges form a directed path. / Dissertation/Thesis / Ph.D. Mathematics 2013

M.Sc. (Computer Science) / In this thesis a study is made of graphs, graph grammars as well as grammars which represent structures in three dimensions. Structure graphs are defined for the first time in this thesis. The definition thereof is based upon that of ordinary graphs, they differ however in that certain geometric properties are assigned to the arcs of the graphs, Two different types of structure graph grammars are defined. Structure graph grammars derive structure graphs as language. The geometric properties of the structure graphs appear as context's in the grammars. A study is mode of the properties of· the structure graph grammars. A comparison between the two types of grammars is also given. The properties of the languages derived by each are also discussed. Existing computer systems which model chemical processes are also discussed. Finally a discussion is given of a software system which was developed as part of this study.

University of Macau / Faculty of Science and Technology / Department of Computer and Information Science

The main focus of this thesis is to evaluate .k_r(n,\delta)., the minimal number of $r$-cliques in graphs with $n$ vertices and minimum degree~$\delta$. A fundamental result in Graph Theory states that a triangle-free graph of order $n$ has at most $n 2/4$ edges. Hence, a triangle-free graph has minimum degree at most $n/2$, so if $k_3(n,\delta) =0$ then $\delta \le n/2$. For $n/2 \leq \delta \leq 4n/5$, I have evaluated $k_r(n,\delta)$ and determined the structures of the extremal graphs. For $\delta \ge 4n/5$, I give a conjecture on $k_r(n,\delta)$, as well as the structures of these extremal graphs. Moreover, I have proved various partial results that support this conjecture. Let $k_r �(n, \delta)$ be the analogous version of $k_r(n,\delta)$ for regular graphs. Notice that there exist $n$ and $\delta$ such that $k_r(n, \delta) =0$ but $k_r �(n, \delta) >0$. For example, a theorem of Andr{\'a}sfai, Erd{\H}s and S{\'o}s states that any triangle-free graph of order $n$ with minimum degree greater than $2n/5$ must be bipartite. Hence $k_3(n, \lfloor n/2 \rfloor) =0$ but $k_3 �(n, \lfloor n/2 \rfloor) >0$ for $n$ odd. I have evaluated the exact value $k_3 �(n, \delta)$ for $\delta$ between $2n/5+12 \sqrt{n}/5$ and $n/2$ and determined the structure of these extremal graphs. At the end of the thesis, I investigate a question in Ramsey Theory. The Ramsey number $R_k(G)$ of a graph $G$ is the minimum number $N$, such that any edge colouring of $K_N$ with $k$ colours contains a monochromatic copy of $G$. The constrained Ramsey number $f(G,T)$ of two graphs $G$ and $T$ is the minimum number $N$ such that any edge colouring of $K_N$ with any number of colours contains a monochromatic copy of $G$ or a rainbow copy of $T$. It turns out that these two quantities are closely related when $T$ is a matching. Namely, for almost all graphs $G$, $f(G,tK_2) =R_{t-1}(G)$ for $t \geq 2$.

No description available.

The solution for the edge-isoperimetric problem (EIP) of the square tessellation of plane is investigated and solved. Summaries of the stabilization theory and previous research dealing with the EIP are stated. These techniques enable us to solve the EIP of the cubical tessellation.

abstract: The chromatic number $\chi(G)$ of a graph $G=(V,E)$ is the minimum number of colors needed to color $V(G)$ such that no adjacent vertices receive the same color. The coloring number $\col(G)$ of a graph $G$ is the minimum number $k$ such that there exists a linear ordering of $V(G)$ for which each vertex has at most $k-1$ backward neighbors. It is well known that the coloring number is an upper bound for the chromatic number. The weak $r$-coloring number $\wcol_{r}(G)$ is a generalization of the coloring number, and it was first introduced by Kierstead and Yang \cite{77}. The weak $r$-coloring number $\wcol_{r}(G)$ is the minimum integer $k$ such that for some linear ordering $L$ of $V(G)$ each vertex $v$ can reach at most $k-1$ other smaller vertices $u$ (with respect to $L$) with a path of length at most $r$ and $u$ is the smallest vertex in the path. This dissertation proves that $\wcol_{2}(G)\le23$ for every planar graph $G$. The exact distance-$3$ graph $G^{[\natural3]}$ of a graph $G=(V,E)$ is a graph with $V$ as its set of vertices, and $xy\in E(G^{[\natural3]})$ if and only if the distance between $x$ and $y$ in $G$ is $3$. This dissertation improves the best known upper bound of the chromatic number of the exact distance-$3$ graphs $G^{[\natural3]}$ of planar graphs $G$, which is $105$, to $95$. It also improves the best known lower bound, which is $7$, to $9$. A class of graphs is nowhere dense if for every $r\ge 1$ there exists $t\ge 1$ such that no graph in the class contains a topological minor of the complete graph $K_t$ where every edge is subdivided at most $r$ times. This dissertation gives a new characterization of nowhere dense classes using generalized notions of the domination number. / Dissertation/Thesis / Doctoral Dissertation Mathematics 2020

The direct sum of a finite number of graph classes H_1, ..., H_k is defined as the set of all graphs formed by taking the union of graphs from each of the H_i. The join of these graph classes is similarly defined as the set of all graphs formed by taking the join of graphs from each of the H_i. In this paper we show that if each H_i has a forbidden subgraph characterization then the direct sum and join of these H_i also have forbidden subgraph characterizations. We provide various results which in many cases allow us to exactly determine the minimal forbidden subgraphs for such characterizations. As we develop these results we are led to study the minimal graphs which are universal over a given list of graphs, or those which contain each graph in the list as an induced subgraph. As a direct application of our results we give an alternate proof of a theorem of Barrett and Loewy concerning a forbidden subgraph characterization problem.

A $(m,n)$-mixed graph is a mixed graph whose edges are assigned one of $m$ colours, and whose arcs are assigned one of $n$ colours. Let $G$ be a $(m,n)$-mixed graph and $\pi=(\alpha,\beta,\gamma_1,\gamma_2,\ldots,\gamma_n)$ be a $(n+2)$-tuple of permutations from $S_m \times S_n \times S_2^n$. We define \emph{switching at a vertex $v$ with respect to $\pi$} as follows. Replace each edge $vw$ of colour $\phi$ by an edge $vw$ of colour $\alpha(\phi)$, and each arc $vx$ of colour $\phi$ by an arc $\gamma_\phi(vx)$ of colour $\beta(\phi)$. In this thesis, we study the complexity of the question: ``Given a $(m,n)$-mixed graph $G$, is there a sequence of switches at vertices of $G$ with respect to the fixed group $\Gamma$ so that the resulting $(m,n)$-mixed graph admits a homomorphism to some $(m,n)$-mixed graph on $2$ vertices?'' We show the following: (1) When restricted to $(m,0)$-mixed graphs $H$ on at most $2$ vertices, the $\Gamma$-switchable homomorphism decision problem is solvable in polynomial time; (2) for each bipartite $(0,n)$-mixed graph $H$, there is a bipartite $(2n,0)$-mixed graph such that the respective $\Gamma$-switchable homomorphism decision problems are polynomially equivalent; (3) For all $(m,n)$-mixed graphs and groups, when $H$ has at most $2$ vertices, the $\Gamma$-switchable homomorphism decision problem is polynomial time solvable; (4) For a yes-instance of the $\Gamma$-switchable homomorphism problem for $(m,0)$-mixed graphs, we can find in quadratic time a sequence of switches on $G$ such that the resulting $(m,0)$-mixed graph admits a homomorphism to $H$. By proving (1)-(4), we show that the $\Gamma$-switchable $2$-colouring problem for $(m,n)$-mixed graphs is solvable in polynomial time for all finite permutation groups $\Gamma$ and provide a step towards a dichotomy theorem for the complexity of the $\Gamma$-switchable homomorphism decision problem. / Graduate