Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 99 for “"simple graph"”.
-
Degree sequences
… d2,···,dn) of nonnegative integers is said to be graphic if it is the degree sequence of a simple graph of order n and such graph is referred to as a realization of pi.;Let H be a simple graph. A graphic sequence pi is said to be potentially H-graphic if it has a realization G containing H as its …
-
On potentially (K(,4) - e)-graphic sequences.
… sequence π = (d1, d2, · · · , dn) is said to be graphic if it is the degree sequence of a simple graph G of order n, and such graph G is referred to as a realization of π. Let H be a simple graph. A graphic sequence π is said to be potentially H-graphic if it has a realization G containing H as a …
-
AN ESSAY ON DISTRIBUTIONAL APPROXIMATION IN THE CONFIGURATION MODEL VIA STEIN’S METHOD
… in the configuration model and the uniform simple graph with given vertex degrees via Stein’s method. We consider normal approximation to the numbers of two kinds of the simplest trees, isolated edges and isolated 2-stars, along with Poisson approximation to the numbers of self-loops and …
-
Selected Topics in Machine Learning
… and more attention in recent decades. Gaussian graphical model can be used to estimate the precision matrix and then construct the connection graph among a group of variables. However, existing methods may assume the strong irrepresentability condition in order to establish desirable theoretical …
-
Improved algorithms for burning graph families
In the graph burning problem, the input is an undirected, unweighted, finite, and simple graph. A fire starts at a vertex at each round, and when a particular vertex is burned, all of its adjacent vertices are burned in the next round. We assume that the rounds are synchronous and discrete. At each …
-
Independent Domination Of Subcubic Graphs
Let G be a simple graph. The independent domination number i(G) is the minimum cardinality among all maximal independent sets of G. A graph is subcubic whenever the maximum degree is at most three. In this paper, we will show that the independent domination number of a connected subcubic graph of …
-
Edge-choosability of Planar Graphs
… to the List Colouring Conjecture, if G is a multigraph then χ' (G)=χl' (G) . In this thesis, we discuss a relaxed version of this conjecture that every simple graph G is edge-(∆ + 1)-choosable as by Vizing’s Theorem ∆(G) ≤χ' (G)≤∆(G) + 1. We prove that if G is a planar graph without 7-cycles with …
-
Independence Polynomials
… we investigate the independence polynomial of a simple graph G. In addition to giving several tools for computing these polynomials and giving closed-form representations of these polynomials for common classes of graphs, we prove two results concerning the roots of independence polynomials. The …
-
The Minimum Rank Problem for Outerplanar Graphs
Given a simple graph G with vertex set V(G)={1,2,...,n} define S(G) to be the set of all real symmetric matrices A such that for all i not equal to j, the ijth entry of A is nonzero if and only if ij is in E(G). The range of the ranks of matrices in S(G) is of interest and can be determined by …
-
A collection of algorithmic and complexity results for variants of the Firefighter Problem
… models the spread and defence of a fire using a simple graph. We consider the following discrete-time process: at t = 0 some vertex of the graph begins burning. At each subsequent step we may defend a vertex from burning and the fire spreads from all burning vertices to all undefended neighbours. …
-
Bounding the Forcing Number of a Graph
… with a sparsity pattern described by the simple graph G. Simple lower and upper bounds are δ ≤ F(G) where δ is the minimum degree and F (G) ≤ n − 1 where n is the order of the graph. This thesis provides improvements on the minimum degree lower bound in the case that G has girth of at …
-
The Packing Chromatic Number of Random d-regular Graphs
Let G = (V (G),E(G)) be a simple graph of order n and let i be a positive integer. Xi superset V (G) is called an i-packing if vertices in Xi are pairwise distance more than i apart. A packing coloring of G is a partition X = {X1,X2,X3, . . . ,Xk} of V (G) such that each color class Xi is an …
-
On Eulerian subgraphs and hamiltonian line graphs
A graph {\color{black}$G$} is Hamilton-connected if for any pair of distinct vertices {\color{black}$u, v \in V(G)$}, {\color{black}$G$} has a spanning $(u,v)$-path; {\color{black}$G$} is 1-hamiltonian if for any vertex subset $S \subseteq {\color{black}V(G)}$ with $|S| \le 1$, $G - S$ has a …
-
The D-neighborhood complex of a graph
The Neighborhood complex of a graph, G, is an abstract simplicial complex formed by the subsets of the neighborhoods of all vertices in G. The construction of this simplicial complex can be generalized to use any subset of graph distances as a means to form the simplices in the associated …
-
Comparing invariants of toric ideals of bipartite graphs
Given a finite simple graph G, one can associate to G an ideal I_G, called the toric ideal of G. There are a number of algebraic invariants of ideals which are frequently studied in commutative algebra. In general, understanding these invariants is very difficult for arbitrary ideals. However, when …
-
Coloring clique hypergraphs
Let G = (V, E) be a simple graph. The clique hypergraph of G, denoted as CH( G), has V as its set of vertices, and the maximal cliques as its hyperedges. Let Sk be a set of k colors. A map c : V Sk is a proper k-coloring for CH(G) if any maximal clique of G with at least two vertices receives at …
-
Constructing Cospectral and Comatching Graphs
The matching polynomial is a graph polynomial that does not only have interesting mathematical properties, but also possesses meaningful applications in physics and chemistry. For a simple graph, the matching polynomial enumerates the number of matchings of different sizes in it. Two graphs are …
-
Can you hear the size of the vertices? An inverse spectral problem of Laplacians on weighted graphs
Let G be a simple graph with n vertices. We define a Laplacian $\Delta$ on G which depends on an assignment of a weight to each vertex of G. One of the eigenvalues of $\Delta$ will always be 0. We fix the remaining (n $-$ 1) eigenvalues and ask for which graphs we can find a set of weights which …
-
On a graph parameter related to vertex labelings and its application to minimum rank problems in graph theory
… rank and minimum positive semidefinite rank of a simple graph. A graph parameter, called the minimum labeling degree (mld), is defined in terms of the concept of a vertex labeling of a graph, and its value is calculated for a few graph classes. It is proved here that there is a conception of mld …
Page 1 of 5