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 75 for “"Regular Graph"”.
-
Coverage probabilities of edges in a regular graph by a random walk
… a random walk covers a given edge in a connected regular network. For a complete graph or a circle graph, we obtain an explicit expression of the coverage probability by using the walk generating function. Alternatively, for any fixed connected regular network, we use the largest eigenvalue of the …
-
Properties of random graphs
… new results for several problems in random graph theory. The first problem relates to the uniform random graph model in the supercritical phase; i.e. a graph, uniformly distributed, on $n$ vertices and $M=n/2+s$ edges for $s=s(n)$ satisfying $n^{2/3}=o(s)$ and $s=o(n)$. The property studied …
-
Produto funcional de grafos :propriedades e aplicações
… thesis, we approach the functional product of graphs, their properties, and applications. We study associativity, and show that, in the set of graphs, the relation “to have the same sequence of degrees” is an equivalence relation and the functional product is associative in the equivalence …
-
Nested (2,r)-regular graphs and their network properties.
A graph G is a (t, r)-regular graph if every collection of t independent vertices is collectively adjacent to exactly r vertices. If a graph G is (2, r)-regular where p, s, and m are positive integers, and m ≥ 2, then when n is sufficiently large, then G is isomorphic to G = Ks+mKp, where 2(p-1)+s …
-
On Properties of r<sub>w</sub>-Regular Graphs
If every vertex in a graph G has the same degree, then the graph is called a regular graph. That is, if deg(v) = r for all vertices in the graph, then it is denoted as an r-regular graph. A graph G is said to be vertex-weighted if all of the vertices are assigned weights. A generalized definition …
-
PARTITIONING STRONGLY REGULAR GRAPHS (BALANCED INCOMPLETE BLOCK DESIGNS, ASSOCIATION SCHEMES).
A strongly regular graph can be design partitioned if the vertices of the graph can be partitioned into two sets V and B such that V is a coclique and every vertex in B is adjacent to the same number of vertices in V. In this case, a balanced incomplete block design can be defined by taking …
-
On the Embeddings of the Semi-Strong Product Graph
… lot has been written about the three more common graph products (Cartesian product, Direct product and the Strong product), as all three of these are commutative products. This thesis investigates a non-commutative product graph, H, G, we call the Semi-Strong graph product, also referred in the …
-
A Characterization of Large (<em>t,r</em>)-Regular Graphs.
A graph G is a (t,r)-regular graph if every collection of t independent vertices is collectively adjacent to exactly r vertices. In this thesis, we will present a complete characterization of (t,r)-regular graphs of order n if n is sufficiently large. Furthermore, we will show that all graphs of …
-
A greedy algorithm enhancing cage search
<p>A cubic cage is a regular graph of degree three with given girth and a minimum number of vertices. Current information about cubic cages is surveyed. A greedy algorithm that permits extremely sparse descriptions of known cages is presented. A number of methods for enhancing the algorithm …
-
Matchings, Connectivity, and Eigenvalues in Regular Graphs
We study extremal and structural problems in regular graphs involving various parameters. In Chapter 2, we obtain the best lower bound for the matching number over $n$-vertex connected regular graphs in terms of edge-connectedness and determine when the matching number is minimized. We also …
-
Thresholds and the structure of sparse random graphs
… non-3-colourability threshold of sparse random graphs and we investigate the structure of random graphs near the region where the transition from 3-colourability to non-3-colourability seems to occur. It has been observed that, as for many other properties, the property of non-3-colourability of …
-
Viewing extremal and structural problems through a probabilistic lens
… similar results for permutations, uniform hypergraphs, and vector spaces are obtained. In 2006, Barát and Thomassen conjectured that the edges of every planar 4-edge-connected 4-regular graph can be decomposed into disjoint copies of $S_3$, the star with three leaves. Shortly afterward, Lai …
-
On strongly regular graphs
Strongly regular graphs are regular graphs with the additional property that the number of common neighbours for two vertices depends only on whether the vertices are adjacent or non-adjacent. From an algebraic point of view, a graph is strongly regular if its adjacency matrix has exactly three …
-
Aspects of Quantum Field Theory in Enumerative Graph Theory
… these partitioned chord diagrams and four-regular maps with marked Euler tours. The second problem comes from the CHY integral formulation of tree-level Feynman integrals in supersymmetric Yang-Mills theory, but amounts to the enumeration of ways to decompose 4-regular graphs into pairs of …
-
On matchings and factors of graphs /
… sketch of matching and factor theory of graphs, and also introduce some necessary definitions and notation. In Section 2, we present a sufficient condition for the existence of a (g, f)-factor in graphs with the odd-cycle property, which is simpler than that of Lovasz's (g, f)-Factor …
-
Graph factors and Hamiltonian decompositions.
… sufficient condition is obtained for a bipartite graph to have an f-factor which includes a designated set of edges and is disjoint from another designated set of edges. Various other characterizations are obtained for similar subgraph structures, and a characterization is obtained for a bipartite …
-
Properties of graphs with large girth
… a class of iterative probabilistic algorithms in regular graphs, called locally greedy algorithms, which will provide bounds for graph functions in regular graphs with large girth. This class is useful because, by conveniently setting the parameters associated with it, we may derive algorithms for …
-
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 …
-
Polynomials of the Adjacency Matrix of a Graph (distance-Transitive, Distance-Regular, Orbit)
Given graphs (GAMMA) and (DELTA), and a real polynomial r(x), we will say that (DELTA) is generated from (GAMMA) by r(x) if r(A((GAMMA))) = A((DELTA)) where A((GAMMA)) and A((DELTA)) are adjacency matrices. For several interesting classes of graphs it is possible to determine all of the graphs …
-
Randomised algorithms for low temperature spin systems
… a general framework in which the vertices of a graph are assigned spins from a finite set. The local interactions between neighbouring spins give rise to a global weight, which describes the probability that the system is in the given configuration. Spin systems provide a framework for sampling …
Page 1 of 4