To see the other types of publications on this topic, follow the link: Regular graphs.
Dissertations / Theses on the topic 'Regular graphs'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Regular graphs.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Hoffmann, Arne. "Regular factors in graphs." [S.l.] : [s.n.], 2002. http://deposit.ddb.de/cgi-bin/dokserv?idn=965227979.
Full text
2
Macon, Lisa. "ALMOST REGULAR GRAPHS AND EDGE FACE COLORINGS OF PLANE GRAPHS." Doctoral diss., University of Central Florida, 2009. http://digital.library.ucf.edu/cdm/ref/collection/ETD/id/2480.
Full textAbstract:
Regular graphs are graphs in which all vertices have the same degree. Many properties of these graphs are known. Such graphs play an important role in modeling network configurations where equipment limitations impose a restriction on the maximum number of links emanating from a node. These limitations do not enforce strict regularity, and it becomes interesting to investigate nonregular graphs that are in some sense close to regular. This dissertation explores a particular class of almost regular graphs in detail and defines generalizations on this class. A linear-time algorithm for the creation of arbitrarily large graphs of the discussed class is provided, and a polynomial-time algorithm for recognizing graphs in the class is given. Several invariants for the class are discussed. The edge-face chromatic number χef of a plane graph G is the minimum number of colors that must be assigned to the edges and faces of G such that no edge or face of G receives the same color as an edge or face with which it is incident or adjacent. A well-known result for the upper bound of χef exists for graphs with maximum degree Δ ≥ 10. We present a tight upper bound for plane graphs with Δ = 9.Ph.D.
Department of Mathematics
Sciences
Mathematics PhD
3
Mortada, Maidoun. "The b-chromatic number of regular graphs." Thesis, Lyon 1, 2013. http://www.theses.fr/2013LYO10116.
Full textAbstract:
Les deux problèmes majeurs considérés dans cette thèse : le b-coloration problème et le graphe emballage problème. 1. Le b-coloration problème : Une coloration des sommets de G s'appelle une b-coloration si chaque classe de couleur contient au moins un sommet qui a un voisin dans toutes les autres classes de couleur. Le nombre b-chromatique b(G) de G est le plus grand entier k pour lequel G a une b-coloration avec k couleurs. EL Sahili et Kouider demandent s'il est vrai que chaque graphe d-régulier G avec le périmètre au moins 5 satisfait b(G) = d + 1. Blidia, Maffray et Zemir ont montré que la conjecture d'El Sahili et de Kouider est vraie pour d ≤ 6. En outre, la question a été résolue pour les graphes d-réguliers dans des conditions supplémentaires. Nous étudions la conjecture d'El Sahili et de Kouider en déterminant quand elle est possible et dans quelles conditions supplémentaires elle est vrai. Nous montrons que b(G) = d + 1 si G est un graphe d-régulier qui ne contient pas un cycle d'ordre 4 ni d'ordre 6. En outre, nous fournissons des conditions sur les sommets d'un graphe d-régulier G sans le cycle d'ordre 4 de sorte que b(G) = d + 1. Cabello et Jakovac ont prouvé si v(G) ≥ 2d3 - d2 + d, puis b(G) = d + 1, où G est un graphe d-régulier. Nous améliorons ce résultat en montrant que si v(G) ≥ 2d3 - 2d2 + 2d alors b(G) = d + 1 pour un graphe d-régulier G. 2. Emballage de graphe problème : Soit G un graphe d'ordre n. Considérer une permutation σ : V (G) → V (Kn), la fonction σ* : E(G) → E(Kn) telle que σ *(xy) = σ *(x) σ *(y) est la fonction induite par σ. Nous disons qu'il y a un emballage de k copies de G (dans le graphe complet Kn) s'il existe k permutations σi : V (G) → V (Kn), où i = 1, …, k, telles que σi*(E(G)) ∩ σj (E(G)) = ɸ pour i ≠ j. Un emballage de k copies d'un graphe G est appelé un k-placement de G. La puissance k d'un graphe G, noté par Gk, est un graphe avec le même ensemble de sommets que G et une arête entre deux sommets si et seulement si le distance entre ces deux sommets est au plus k. Kheddouci et al. ont prouvé que pour un arbre non-étoile T, il existe un 2-placement σ sur V (T). Nous introduisons pour la première fois le problème emballage marqué de graphe dans son graphe puissanceTwo problems are considered in this thesis: the b-coloring problem and the graph packing problem. 1. The b-Coloring Problem : A b-coloring of a graph G is a proper coloring of the vertices of G such that there exists a vertex in each color class joined to at least a vertex in each other color class. The b-chromatic number of a graph G, denoted by b(G), is the maximum number t such that G admits a b-coloring with t colors. El Sahili and Kouider asked whether it is true that every d-regular graph G with girth at least 5 satisfies b(G) = d + 1. Blidia, Maffray and Zemir proved that the conjecture is true for d ≤ 6. Also, the question was solved for d-regular graphs with supplementary conditions. We study El Sahili and Kouider conjecture by determining when it is possible and under what supplementary conditions it is true. We prove that b(G) = d+1 if G is a d-regular graph containing neither a cycle of order 4 nor of order 6. Then, we provide specific conditions on the vertices of a d-regular graph G with no cycle of order 4 so that b(G) = d + 1. Cabello and Jakovac proved that if v(G) ≥ 2d3 - d2 + d, then b(G) = d + 1, where G is a d-regular graph. We improve this bound by proving that if v(G) ≥ 2d3 - 2d2 + 2d, then b(G) = d+1 for a d-regular graph G. 2. Graph Packing Problem : Graph packing problem is a classical problem in graph theory and has been extensively studied since the early 70's. Consider a permutation σ : V (G) → V (Kn), the function σ* : E(G) → E(Kn) such that σ *(xy) = σ *(x) σ *(y) is the function induced by σ. We say that there is a packing of k copies of G into the complete graph Kn if there exist k permutations σ i : V (G) → V (Kn), where i = 1,…, k, such that σ*i (E(G)) ∩ σ*j (E(G)) = ɸ for I ≠ j. A packing of k copies of a graph G will be called a k-placement of G. The kth power Gk of a graph G is the supergraph of G formed by adding an edge between all pairs of vertices of G with distance at most k. Kheddouci et al. proved that for any non-star tree T there exists a 2-placement σ on V (T). We introduce a new variant of graph packing problem, called the labeled packing of a graph into its power graph
4
Wu, Taoyang. "Regular configurations and TBR graphs." Thesis, Queen Mary, University of London, 2009. http://qmro.qmul.ac.uk/xmlui/handle/123456789/138.
Full textAbstract:
This thesis consists of two parts: The first one is concerned with the theory and applications of regular configurations; the second one is devoted to TBR graphs. In the first part, a new approach is proposed to study regular configurations, an extremal arrangement of necklaces formed by a given number of red beads and black beads. We first show that this concept is closely related to several other concepts studied in the literature, such as balanced words, maximally even sets, and the ground states in the Kawasaki-Ising model. Then we apply regular configurations to solve the (vertex) cycle packing problem for shift digraphs, a family of Cayley digraphs. TBR is one of widely used tree rearrangement operationes, and plays an important role in heuristic algorithms for phylogenetic tree reconstruction. In the second part of this thesis we study various properties of TBR graphs, a family of graphs associated with the TBR operation. To investigate the degree distribution of the TBR graphs, we also study -index, a concept introduced to measure the shape of trees. As an interesting by-product, we obtain a structural characterization of good trees, a well-known family of trees that generalizes the complete binary trees.
5
Macon, Lisa Fischer. "Almost regular graphs and edge-face colorings of plane graphs." Orlando, Fla. : University of Central Florida, 2009. http://purl.fcla.edu/fcla/etd/CFE0002507.
Full text
6
High, David. "On 4-Regular Planar Hamiltonian Graphs." TopSCHOLAR®, 2006. http://digitalcommons.wku.edu/theses/277.
Full textAbstract:
In order to research knots with large crossing numbers, one would like to be able to select a random knot from the set of all knots with n crossings with as close to uniform probability as possible. The underlying graph of a knot diagram can be viewed as a 4-regular planar graph. The existence of a Hamiltonian cycle in such a graph is necessary in order to use the graph to compute an upper bound on rope length for a given knot. The algorithm to generate such graphs is discussed and an exact count of the number of graphs is obtained. In order to allow for the existence of such a count, a somewhat technical definition of graph equivalence is used. The main result of the thesis is the asymptotic results of how fast the number of graphs with n vertices (crossings) grows with n.
7
Janmark, Jonatan. "Quantum Search on Strongly Regular Graphs." Thesis, KTH, Teoretisk fysik, 2013. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-126266.
Full text
8
Beis, Michail. "Greedy algorithms for random regular graphs." Thesis, University of Liverpool, 2006. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.427021.
Full text
9
Gasquoine, Sarah Louise. "Finite and infinite extensions of regular graphs." Thesis, Queen Mary, University of London, 1999. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.313750.
Full text
10
Davies, Ewan. "Extremal and probabilistic results for regular graphs." Thesis, London School of Economics and Political Science (University of London), 2017. http://etheses.lse.ac.uk/3615/.
Full textAbstract:
In this thesis we explore extremal graph theory, focusing on new methods which apply to different notions of regular graph. The first notion is dregularity, which means each vertex of a graph is contained in exactly d edges, and the second notion is Szemerédi regularity, which is a strong, approximate version of this property that relates to pseudorandomness. We begin with a novel method for optimising observables of Gibbs distributions in sparse graphs. The simplest application of the method is to the hard-core model, concerning independent sets in d-regular graphs, where we prove a tight upper bound on an observable known as the occupancy fraction. We also cover applications to matchings and colourings, in each case proving a tight bound on an observable of a Gibbs distribution and deriving an extremal result on the number of a relevant combinatorial structure in regular graphs. The results relate to a wide range of topics including statistical physics and Ramsey theory. We then turn to a form of Szemerédi regularity in sparse hypergraphs, and develop a method for embedding complexes that generalises a widely-applied method for counting in pseudorandom graphs. We prove an inheritance lemma which shows that the neighbourhood of a sparse, regular subgraph of a highly pseudorandom hypergraph typically inherits regularity in a natural way. This shows that we may embed complexes into suitable regular hypergraphs vertex-by-vertex, in much the same way as one can prove a counting lemma for regular graphs. Finally, we consider the multicolour Ramsey number of paths and even cycles. A well-known density argument shows that when the edges of a complete graph on kn vertices are coloured with k colours, one can find a monochromatic path on n vertices. We give an improvement to this bound by exploiting the structure of the densest colour, and use the regularity method to extend the result to even cycles.
11
Gosnell, Shannon Leah. "A Characterization of Large (t,r)-Regular Graphs." Digital Commons @ East Tennessee State University, 2000. https://dc.etsu.edu/etd/7.
Full textAbstract:
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 this type are isomorphic to Ks + mKp where t(p - 1) + s = r.
12
Madden, Yale. "Loop Edge Estimation in 4-Regular Hamiltonian Graphs." TopSCHOLAR®, 2007. http://digitalcommons.wku.edu/theses/406.
Full textAbstract:
In knot theory, a knot is defined as a closed, non-self-intersecting curve embedded in three-dimensional space that cannot be untangled to produce a simple planar loop. A mathematical knot is essentially a conventional knot tied with rope where the ends of the rope have been glued together. One way to sample large knots is based on choosing a 4-regular Hamiltonian planar graph. A method for generating rooted 4-regular Hamiltonian planar graphs with n vertices is discussed in this thesis. In the generation process of these graphs, some vertices are introduced that can be easily eliminated from the resulting knot diagram. The main result of this thesis is the estimation of the expected number of loop edges in a 4-regular Hamiltonian planar graphs of n vertices; in particular, it is shown that the expected number of loop edges L(n) in such a graph has asymptotic order n/6.
13
Wong, Wiseley. "Spanning trees, toughness, and eigenvalues of regular graphs." Thesis, University of Delaware, 2013. http://pqdtopen.proquest.com/#viewpdf?dispub=3595000.
Full textAbstract:
Spectral graph theory is a branch of graph theory which finds relationships between structural properties of graphs and eigenvalues of matrices corresponding to graphs. In this thesis, I obtain sufficient eigenvalue conditions for the existence of edge-disjoint spanning trees in regular graphs, and I show this is best possible. The vertex toughness of a graph is defined as the minimum value of [special characters omitted], where S runs through all subsets of vertices that disconnect the graph, and c(G\S ) denotes the number of components after deleting S. I obtain sufficient eigenvalue conditions for a regular graph to have toughness at least 1, and I show this is best possible. Furthermore, I determine the toughness value for many families of graphs, and I classify the subsets S of each family for when this value is obtained.
14
Requilé, Clément [Verfasser]. "Asymptotic study of regular planar graphs / Clément Requilé." Berlin : Freie Universität Berlin, 2019. http://d-nb.info/1181098114/34.
Full text
15
Haslegrave, John George Ernest. "Extremal results on hypergraphs, trees and regular graphs." Thesis, University of Cambridge, 2011. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.609876.
Full text
16
Skees, James. "Bounds on k-Regular Ramanujan Graphs and Separator Theorems." TopSCHOLAR®, 2007. http://digitalcommons.wku.edu/theses/379.
Full textAbstract:
Expander graphs are a family of graphs that are highly connected. Finding explicit examples of expander graphs which are also sparse is a difficult problem. The best type of expander graph in a. certain sense is a Ramanujan graph. Families of graphs that have separator theorems fail to be Ramanujan if the vertex set gets sufficiently large. Using separator theorems to get an estimate on the expanding constant of graphs, we get bounds 011 the number of vertices for such fc-regular graphs in order for them to be Ramanujan.
17
Ascigil, Mehmet. "An Algorithm to Generate 4-Regular Planar Hamiltonian Graphs." TopSCHOLAR®, 2006. http://digitalcommons.wku.edu/theses/440.
Full textAbstract:
In this paper, the problem of randomly generating 4-regular planar Hamiltonian graphs is discussed and a solution is described. An algorithm which efficiently generates the graphs in linear time and in a near-uniform manner is given. In addition, a formula is provided that determines the total number of such graphs. The generation of graphs starts with forming the Hamiltonian cycle of the final graph. Each vertex is randomly assigned to be connected with zero. one. Or two edges in the area bounded by the Hamiltonian cycle. A positive prefix vector is used to determine all the edges in the area bounded by the Hamiltonian cycle. Another positive prefix vector is used for determining the edges in the area not bounded by the Hamiltonian cycle, forming the final graph.
18
Samani, Franklina. "On Properties of rw-Regular Graphs." Digital Commons @ East Tennessee State University, 2015. https://dc.etsu.edu/etd/2601.
Full textAbstract:
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 for degree regularity for vertex-weighted graphs can be stated as follows: A vertex-weighted graph is said to be rw-regular if the sum of the weights in the neighborhood of every vertex is rw. If all vertices are assigned the unit weight of 1, then this is equivalent to the definition for r-regular graphs. In this thesis, we determine if a graph has a weighting scheme that makes it a weighted regular graph or prove no such scheme exists for a number of special classes of graphs such as paths, stars, caterpillars, spiders and wheels.
19
Brooks, Josh Daniel. "Nested (2,r)-regular graphs and their network properties." Digital Commons @ East Tennessee State University, 2012. https://dc.etsu.edu/etd/1471.
Full textAbstract:
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 = r. A nested (2,r)-regular graph is constructed by replacing selected cliques with a (2,r)-regular graph and joining the vertices of the peripheral cliques. For example, in a nested 's' graph when n = s + mp, we obtain n = s1+m1p1+mp. The nested 's' graph is now of the form Gs = Ks1+m1Kp1+mKp. We examine the network properties such as the average path length, clustering coefficient, and the spectrum of these nested graphs.
20
Liu, Xiangwei 1976. "Spectrum of some regular graphs with widely spaced modifications." Thesis, Massachusetts Institute of Technology, 2001. http://hdl.handle.net/1721.1/8224.
Full textAbstract:
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2001.Includes bibliographical references (p. 71-72).
This thesis has two parts. The first part studies the spectrum of a family of growing trees, we show that the eigenvalues of the adjacency matrix and Laplacian matrix have high multiplicities. As the trees grow, the graphs of those eigenvalues approach a piecewise-constant "Cantor function", which is different from the corresponding properties of the infinite tree. The second part studies the effect of "widely spaced" modifications on the spectrum of some type of structured matrices. We show that by applying those modifications, new eigenvectors that are localized near the components that correspond to the modified rows appear. By knowing the approximate form of those eigenvectors, we also determine a very close (and simple) approximation to the eigenvalues, and then we show that this approximation is indeed the limit as the matrix grows.
by Xiangwei Liu.
Ph.D.
21
Wang, Zeying. "Skew Hadamard difference sets, strongly regular graphs and bent functions." Access to citation, abstract and download form provided by ProQuest Information and Learning Company; downloadable PDF file, 127 p, 2009. http://proquest.umi.com/pqdweb?did=1654490981&sid=2&Fmt=2&clientId=8331&RQT=309&VName=PQD.
Full text
22
Bougard, Nicolas. "Regular graphs and convex polyhedra with prescribed numbers of orbits." Doctoral thesis, Universite Libre de Bruxelles, 2007. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/210688.
Full textAbstract:
Etant donné trois entiers k, s et a, nous prouvons dans le premier chapitre qu'il existe un graphe k-régulier fini (resp. un graphe k-régulier connexe fini) dont le groupe d'automorphismes a exactement s orbites sur l'ensemble des sommets et a orbites sur l'ensemble des arêtes si et seulement si(s,a)=(1,0) si k=0,
(s,a)=(1,1) si k=1,
s=a>0 si k=2,
0< s <= 2a <= 2ks si k>2.
(resp.
(s,a)=(1,0) si k=0,
(s,a)=(1,1) si k=1 ou 2,
s-1<=a<=(k-1)s+1 et s,a>0 si k>2.)
Nous étudions les polyèdres convexes de R³ dans le second chapitre. Pour tout polyèdre convexe P, nous notons Isom(P) l'ensemble des isométries de R³ laissant P invariant. Si G est un sous-groupe de Isom(P), le f_G-vecteur de P est le triple d'entiers (s,a,f) tel que G ait exactement s orbites sur l'ensemble sommets de P, a orbites sur l'ensemble des arêtes de P et f orbites sur l'ensemble des faces de P. Remarquons que (s,a,f) est le f_{id}-vecteur (appelé f-vecteur dans la littérature) d'un polyèdre si ce dernier possède exactement s sommets, a arêtes et f faces. Nous généralisons un théorème de Steinitz décrivant tous les f-vecteurs possibles. Pour tout groupe fini G d'isométries de R³, nous déterminons l'ensemble des triples (s,a,f) pour lesquels il existe un polyèdre convexe ayant (s,a,f) comme f_G-vecteur. Ces résultats nous permettent de caractériser les triples (s,a,f) pour lesquels il existe un polyèdre convexe tel que Isom(P) a s orbites sur l'ensemble des sommets, a orbites sur l'ensemble des arêtes et f orbites sur l'ensemble des faces.
La structure d'incidence I(P) associée à un polyèdre P consiste en la donnée de l'ensemble des sommets de P, l'ensemble des arêtes de P, l'ensemble des faces de P et de l'inclusion entre ces différents éléments (la notion de distance ne se trouve pas dans I(P)). Nous déterminons également l'ensemble des triples d'entiers (s,a,f) pour lesquels il existe une structure d'incidence I(P) associée à un polyèdre P dont le groupe d'automorphismes a exactement s orbites de sommets, a orbites d'arêtes et f orbites de sommets.
Doctorat en sciences, Spécialisation mathématiques
info:eu-repo/semantics/nonPublished
23
Conine, Grant Mcneil. "Topological Data Analysis of Properties of Four-Regular Rigid Vertex Graphs." Scholar Commons, 2014. https://scholarcommons.usf.edu/etd/5202.
Full textAbstract:
Homologous DNA recombination and rearrangement has been modeled with a class of four-regular rigid vertex graphs called assembly graphs which can also be represented by double occurrence words. Various invariants have been suggested for these graphs, some based on the structure of the graphs, and some biologically motivated.
In this thesis we use a novel method of data analysis based on a technique known as partial-clustering analysis and an algorithm known as Mapper to examine the relationships between these invariants. We introduce some of the basic machinery of topological data analysis, including the construction of simplicial complexes on a data set, clustering analysis, and the workings of the Mapper algorithm. We define assembly graphs and three specific invariants of these graphs: assembly number, nesting index, and genus range. We apply Mapper to the set of all assembly graphs up to 6 vertices and compare relationships between these three properties. We make several observations based upon the results of the analysis we obtained. We conclude with some suggestions for further research based upon our findings.
24
Niu, Liang. "The Vertex Primitive and Vertex Bi-primitive s-arc regular graphs." The Ohio State University, 2008. http://rave.ohiolink.edu/etdc/view?acc_num=osu1221597829.
Full text
25
Wanzambi, Ellinor, and Stina Andersson. "Quantum Computing: Implementing Hitting Time for Coined Quantum Walks on Regular Graphs." Thesis, Uppsala universitet, Institutionen för informationsteknologi, 2021. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-444818.
Full textAbstract:
In recent years, quantum walks have been widely researched and haveshown exciting properties. One such is a quadratic speed-up in hittingtime compared to its classical counterpart. In this paper, we design aquantum circuit for the MNRS algorithm, which finds a marked node in agraph with a quantum walk, and use it to find a hitting time for themarked nodes in the walk. We do this by implementing the circuit on IBMquantum simulators and show that the execution on a noise-free simulatorresults in hitting times that agree with the theoretical expectations.We also run the algorithm on a mock backend that simulates the noise ofthe IBM Melbourne computer. As expected, the noise has an extensiveimpact on the output, resulting in outcomes far from the noise-freesimulation.IT 21
26
Rahm, Ludwig. "Generating functions and regular languages of walks with modular restrictions in graphs." Thesis, Linköpings universitet, Matematik och tillämpad matematik, 2017. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-138117.
Full textAbstract:
This thesis examines the problem of counting and describing walks in graphs, and the problem when such walks have modular restrictions on how many timesit visits each vertex. For the special cases of the path graph, the cycle graph, the grid graph and the cylinder graph, generating functions and regular languages for their walks and walks with modular restrictions are constructed. At the end of the thesis, a theorem is proved that connects the generating function for walks in a graph to the generating function for walks in a covering graph.
27
Sivaraman, Vaidyanathan. "Some Topics concerning Graphs, Signed Graphs and Matroids." The Ohio State University, 2012. http://rave.ohiolink.edu/etdc/view?acc_num=osu1354645035.
Full text
28
Izsak, Alexander. "The second eigenvalue and random walks in random regular graphs with increasing girth." Thesis, University of British Columbia, 2009. http://hdl.handle.net/2429/12649.
Full textAbstract:
The goal of this thesis is to upper bound the expected value of the second largest eigenvalue in magnitude of random regular graphs with a given minimum girth.
Having a small upper bound implies such random graphs are likely to be expanders and thus have several combinatorial properties useful in
various fields of computer science. The best possible upper bound asymptotically on the second eigenvalue has already been proven for random regular graphs
without conditions on the girth. Finding this upper bound though required long and complicated analysis due to tangles, which are certain small subgraphs that contain cycles. This thesis thus hypothesizes that specifying a minimum girth large enough will prevent tangles from occurring in random graphs and thus proving an optimal upper bound on the second eigenvalue can avoid the difficult analysis required in order to handle tangles.
To find such an upper bound on random regular graphs with specified minimum girth we consider the probability that a random walk in such a random graph returns to the first vertex of the walk in the k-th step of the walk. We prove for 2-regular graphs that the random walk is more likely to visit any given vertex not in the walk
than the starting vertex of the walk on the k-th step, and bound how much more likely this event is. We also analyze the d-regular case and we believe our findings will
lead to a similar result in this case.
29
Diego, Víctor. "On some spectral and combinatorial properties of distance-regular graphs and their generalizations." Doctoral thesis, Universitat Politècnica de Catalunya, 2017. http://hdl.handle.net/10803/461632.
Full textAbstract:
In this work we present the study we did in Graph Theory. In the firsts chapteres of the tesis we study the pieces of information that can be obtained from a graph: the spectrum of the adjacency matrix, the preintersection numbers, the predistance polynomials and the average number of closed walks. Some of this pieces of information are direct generalizations of the intersection numbers or the predistance polynomials defined in the distance-regular graphs. We prove that the multiple properties that these pieces of information have in distance-regular graphs hold also in their generalizations, and these properties can be applied to any other graph.
We also prove that the distinct pieces of information (even if their nature is algebraic or combinatorial) are equivalent. That is, we can obtain each one of the pieces in terms of each other; proving in this way that the properties of the graph derived from each one of the pieces can be also obtained in terms of each one of the other. We dedicate a chapter of the tesis to describe completly the especific procedures with which obtain each piece of inforation in terms of the others.
In this tesis we introduce the "distance mean-regular" graphs. These graphs are a generalization of the distance-regular graphs. In this occasion, we demand to the graph combinatorial properties and we generalizate the algebraic properties of the distance-regular graphs. We generalizate the spectrum of a graph to introduce the "pseudo-spectrum" and we generalizate the Bose-Mesner algebra in distinct matrix algebras. The study of these generalizations, as well as the study of the relation between them, give us combinatorial and algebraic properties.
In the final part of the tesis we study the vertex-isoperimetric problem in the Johnson Graph J(n,m). We solve completly the problem for some particular cases: J(n,1), J(n,2), J(2m-2,m), as well as their symetrics J(n,n-2) and J(2m+2,m). The solution for these cases are the initial segments of the colexicographic order. This order is also the solution for small cardinals in every graph of this family, as well as for the asymptotic behaviour of the parameters n and m.
However, this solution is not the optimal solution for every cardinal in every graph J(n,m). We prove and give an infinity family of counterexamples for which the initial segment of the colexicographic order is not optimal in terms of the vertex-isoperimetric problem.En este documento presentamos el estudio realizado en Teoría de Grafos. En los primeros capítulos de la tesis estudiamos las distinetas piezas de información que se pueden obtener de un grafo: el espectro de su matriz de adyacencia, los números de preintersección, los polinomios predistancia o la cantidad media de caminos cerrados. Algunos de estas piezas de información son generalizaciones directas de los números de intersección o los pollinomios distancia definidos en los grafos distancia-regulares. Demostramos que las múltiples propiedades que tienen estas piezas de información en los grafos distancia-regulares se mantienen también en sus generalizaciones, pudiendo aplicar estas propiedades a todo tipo de grafos. Demostramos también que las ditintas piezas de información (ya sean de naturaleza algebraica o combinatoria) son equivalentes. Es decir, podemos obtener cada una de estas piezas en términos de cada una de las otras; probando así que las propiedades del grafo derivadas de cada una de estas piezas puede ser obtenida en términos de cada una de las otras. Dedicamos uno de los capítulos de la tesis a describir cuáles son los procesos específicos completos mediante los cuales obtener cada pieza de información en función de las otras. En esta tesis introducimos también los grafos distance mean-regular. Estos grafos son una generalización de los grafos distancia-regulares. En esta ocasión, al grafo se le exigen propiedades combinatorias y generalizamos las propiedades algebraicas de los grafos distancia-regulares. Generalizamos el espectro de un grafo para introducir el "pseudo-espectro" y generalizamos el álgebra de Bose-Mesner en distintas álgebras de matrices. El estudio de estas generalizaciones, así cómo su relación entre ellas nos proporciona propiedades combinatorias y algebraicas del grafo. En la parte final de la tesis estudiamos el problema isoperimétrico de vértices en el Grafo de Johnson J(n,m). Solucionamos el problema completamente para varios casos particulares: J(n,1), J(n,2) y J(2m-2,m), así como sus simétricos J(n,n-2) y J(2m+2,m). La solución para estos casos son los segmentos iniciales del orden colexicográfico. Este orden es también la solución para cardinales pequeños en todos los grafos de esta familia, así como para el comportamiento asimptótico de los parámetros n y m. Sin embargo, esta solución no es la solución óptima en todos cardinales de todos los grafos J(n,m). Demostramos y damos una familia infinita de contraejemplos para los cuales el segmento inicial de orden colexicográfico no es óptimo en términos del problema isoperimétrico de vértices
30
Carey, Rachael Marie. "Graph automatic semigroups." Thesis, University of St Andrews, 2016. http://hdl.handle.net/10023/8645.
Full textAbstract:
In this thesis we examine properties and constructions of graph automatic semigroups, a generalisation of both automatic semigroups and finitely generated FA-presentable semigroups. We consider the properties of graph automatic semigroups, showing that they are independent of the choice of generating set, have decidable word problem, and that if we have a graph automatic structure for a semigroup then we can find one with uniqueness. Semigroup constructions and their effect on graph automaticity are considered. We show that finitely generated direct products, free products, finitely generated Rees matrix semigroup constructions, zero unions, and ordinal sums all preserve unary graph automaticity, and examine when the converse also holds. We also demonstrate situations where semidirect products, Bruck-Reilly extensions, and semilattice constructions preserve graph automaticity, and consider the conditions we may impose on such constructions in order to ensure that graph automaticity is preserved. Unary graph automatic semigroups, that is semigroups which have graph automatic structures over a single letter alphabet, are also examined. We consider the form of an automaton recognising multiplication by generators in such a semigroup, and use this to demonstrate various properties of unary graph automatic semigroups. We show that infinite periodic semigroups are not unary graph automatic, and show that we may always find a uniform set of normal forms for a unary graph automatic semigroup. We also determine some necessary conditions for a semigroup to be unary graph automatic, and use this to provide examples of semigroups which are not unary graph automatic. Finally we consider semigroup constructions for unary graph automatic semigroups. We show that the free product of two semigroups is unary graph automatic if and only if both semigroups are trivial; that direct products do not always preserve unary graph automaticity; and that Bruck-Reilly extensions are never unary graph automatic.
31
Wagner, Andrew. "On the Existence of a Second Hamilton Cycle in Hamiltonian Graphs With Symmetry." Thèse, Université d'Ottawa / University of Ottawa, 2013. http://hdl.handle.net/10393/30290.
Full textAbstract:
In 1975, Sheehan conjectured that every simple 4-regular hamiltonian graph has a second Hamilton cycle. If Sheehan's Conjecture holds, then the result can be extended to all simple d-regular hamiltonian graphs with d at least 3.
First, we survey some previous results which verify the existence of a second Hamilton cycle if d is large enough. We will then demonstrate some techniques for finding a second Hamilton cycle that will be used throughout this paper. Finally, we use these techniques and show that for certain 4-regular Hamiltonian graphs whose automorphism group is large enough, a second Hamilton cycle exists.
32
Eshghi, Kourosh. "The existence and construction of Ã-valuations of 2-regular graphs with three components." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1997. http://www.collectionscanada.ca/obj/s4/f2/dsk2/ftp02/NQ27919.pdf.
Full text
33
Reich, Alexander [Verfasser], and Ekkehard [Akademischer Betreuer] Köhler. "Cycle bases of graphs and spanning trees with many leaves - complexity results on planar and regular graphs / Alexander Reich. Betreuer: Ekkehard Köhler." Cottbus : Universitätsbibliothek der BTU Cottbus, 2014. http://d-nb.info/1051310636/34.
Full text
34
Coja-Oghlan, Amin, Andreas Goerdt, and André Lanka. "Spectral Partitioning of Random Graphs with Given Expected Degrees - Detailed Version." Universitätsbibliothek Chemnitz, 2009. http://nbn-resolving.de/urn:nbn:de:bsz:ch1-200900426.
Full textAbstract:
It is a well established fact, that – in the case of classical random graphs like variants of Gn,p or random regular graphs – spectral methods yield efficient algorithms for clustering (e. g. colouring or bisec- tion) problems. The theory of large networks emerging recently provides convincing evidence that such networks, albeit looking random in some sense, cannot sensibly be described by classical random graphs. A vari- ety of new types of random graphs have been introduced. One of these types is characterized by the fact that we have a fixed expected degree sequence, that is for each vertex its expected degree is given. Recent theoretical work confirms that spectral methods can be success- fully applied to clustering problems for such random graphs, too – pro- vided that the expected degrees are not too small, in fact ≥ log6 n. In this case however the degree of each vertex is concentrated about its expectation. We show how to remove this restriction and apply spectral methods when the expected degrees are bounded below just by a suitable constant. Our results rely on the observation that techniques developed for the classical sparse Gn,p random graph (that is p = c/n) can be transferred to the present situation, provided we consider a suitably normalized ad- jacency matrix: We divide each entry of the adjacency matrix by the product of the expected degrees of the incident vertices. Given the host of spectral techniques developed for Gn,p this observation should be of independent interest.
35
Schacht, Mathias. "Regular partitions of hypergraphs and property testing." Doctoral thesis, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II, 2010. http://dx.doi.org/10.18452/13975.
Full textAbstract:
Die Regularitätsmethode für Graphen wurde vor über 30 Jahren von Szemerédi, für den Beweis seines Dichteresultates über Teilmengen der natürlichen Zahlen, welche keine arithmetischen Progressionen enthalten, entwickelt. Grob gesprochen besagt das Regularitätslemma, dass die Knotenmenge eines beliebigen Graphen in konstant viele Klassen so zerlegt werden kann, dass fast alle induzierten bipartiten Graphen quasi-zufällig sind, d.h. sie verhalten sich wie zufällige bipartite Graphen mit derselben Dichte. Das Regularitätslemma hatte viele weitere Anwendungen, vor allem in der extremalen Graphentheorie, aber auch in der theoretischen Informatik und der kombinatorischen Zahlentheorie, und gilt mittlerweile als eines der zentralen Hilfsmittel in der modernen Graphentheorie. Vor wenigen Jahren wurden Regularitätslemmata für andere diskrete Strukturen entwickelt. Insbesondere wurde die Regularitätsmethode für uniforme Hypergraphen und dünne Graphen verallgemeinert. Ziel der vorliegenden Arbeit ist die Weiterentwicklung der Regularitätsmethode und deren Anwendung auf Probleme der theoretischen Informatik. Im Besonderen wird gezeigt, dass vererbbare (entscheidbare) Hypergrapheneigenschaften, das sind Familien von Hypergraphen, welche unter Isomorphie und induzierten Untergraphen abgeschlossen sind, testbar sind. D.h. es existiert ein randomisierter Algorithmus, der in konstanter Laufzeit mit hoher Wahrscheinlichkeit zwischen Hypergraphen, welche solche Eigenschaften haben und solchen die „weit“ davon entfernt sind, unterscheidet.About 30 years ago Szemerédi developed the regularity method for graphs, which was a key ingredient in the proof of his famous density result concerning the upper density of subsets of the integers which contain no arithmetic progression of fixed length. Roughly speaking, the regularity lemma asserts, that the vertex set of every graph can be partitioned into a constant number of classes such that almost all of the induced bipartite graphs are quasi-random, i.e., they mimic the behavior of random bipartite graphs of the same density. The regularity lemma had have many applications mainly in extremal graph theory, but also in theoretical computer science and additive number theory, and it is considered one of the central tools in modern graph theory. A few years ago the regularity method was extended to other discrete structures. In particular extensions for uniform hypergraphs and sparse graphs were obtained. The main goal of this thesis is the further development of the regularity method and its application to problems in theoretical computer science. In particular, we will show that hereditary, decidable properties of hypergraphs, that are properties closed under isomorphism and vertex removal, are testable. I.e., there exists a randomised algorithm with constant running time, which distinguishes between Hypergraphs displaying the property and those which are “far” from it.
36
Bello, Jason. "Cyclic Particle Systems on Finite Graphs and Cellular Automata on Rooted, Regular Trees and Galton-Watson Trees." The Ohio State University, 2021. http://rave.ohiolink.edu/etdc/view?acc_num=osu1618833498993715.
Full text
37
Tortop, Tugba. "7th-grade Students." Master's thesis, METU, 2011. http://etd.lib.metu.edu.tr/upload/12613092/index.pdf.
Full textAbstract:
The purpose of this study was to investigate 7th-grade students&rsquotypical errors and possible misconceptions in graphs concept before and after the regular mathematics instruction. The study was conducted in an elementary school in the 2nd semester of 2009-2010 academic year in Afyonkarahisar. A mathematics teacher and 71 7th-grade students participated in the study. The data were collected through achievement tests administered to the students before and after the instruction and interviews conducted with the teachers and the selected eight students based on the results of the pretest and posttest. The teacher&rsquo
s instruction was also observed. Students were not exposed to a special treatment, but rather the influence of regular mathematics instruction on a group of 7th-grade students from the four classes taught by the same teacher was investigated. The results of data analysis indicated that 7th-grade students had common typical errors and possible misconceptions about the usage, construction, reading, and interpretation of line, bar, and circle graphs before and after the regular instruction. The comparison of pretest and posttest results showed that while there were differences between the students&rsquo
errors and misconceptions in pretest and posttest, some misconceptions were decreased or increased, or did not change from pretest to posttest. The interviews conducted with the selected students addressed that the students had errors and misconceptions in graphs concept. Findings of the observation of teacher&rsquo
s instruction showed that the teacher did not fully discover and prevent students&rsquo
typical errors and possible misconceptions. Moreover, the findings of the interview conducted with the teacher indicated that her knowledge of students&rsquo
errors and misconceptions were limited. The results of this study showed that teachers&rsquo
planning was important in understanding students&rsquo
typical errors and possible misconceptions. Inservice training of teachers should put more emphasize in effective planning and understanding students&rsquo
typical errors and possible misconceptions.
38
Castets, Mathieu. "Pavages réguliers et modélisation des dynamiques spatiales à base de graphes d'interaction : conception, implémentation, application." Thesis, Montpellier, 2015. http://www.theses.fr/2015MONTS241/document.
Full textAbstract:
La modélisation et la simulation de dynamiques spatiales, en particulier pour l'étude de l'évolution de paysages ou de problématiques environnementales pose la question de l'intégration des différentes formes de représentation de l'espace au sein d'un même modèle. Ocelet est une approche de modélisation de dynamiques spatiales basée sur le concept original de graphe d'interaction. Le graphe porte à la fois la structure d'une relation entre entités d’un modèle et la sémantique décrivant son évolution. Les relations entre entités spatiales sont ici traduites en graphes d'interactions et ce sont ces graphes que l'on fait évoluer lors d'une simulation. Les concepts à la base d'Ocelet peuvent potentiellement manipuler les deux formes de représentation spatiale connues, celle aux contours définis (format vecteur) ou la discrétisation en grille régulière (format raster). Le format vecteur est déjà intégré dans la première version d'Ocelet. L'intégration du format raster et la combinaison des deux restaient à étudier et à réaliser. L'objectif de la thèse est d'abord étudier les problématiques liées à l'intégration des champs continus et leur représentation discrétisée en pavage régulier, à la fois dans le langage Ocelet et dans les concepts sur lesquels il repose. Il a fallu notamment prendre en compte les aspects dynamiques de cette intégration, et d'étudier les transitions entre données géographiques de différentes formes et graphe d'interactions à l'aide de concepts formalisés. Il s'est agi ensuite de réaliser l'implémentation de ces concepts dans la plateforme de modélisation Ocelet, en adaptant à la fois son compilateur et son moteur d'exécution. Enfin, ces nouveaux concepts et outils ont été mis à l'épreuve dans trois cas d'application très différents : deux modèles sur l’île de la Réunion, le premier simulant le ruissellement dans le bassin versant de la Ravine Saint Gilles s'écoulant vers la Côte Ouest de l'île, l’autre simulant la diffusion de plantes invasives dans les plaines des hauts à l'intérieur du Parc National de La Réunion. Le dernier cas décrit la spatialisation d'un modèle de culture et est appliqué ici pour simuler les rendements de cultures céréalières sur l’ensemble de l’Afrique de l’Ouest, dans le contexte d'un système d'alerte précoce de suivi des cultures à l'échelle régionaleThe modelling and simulation of spatial dynamics, particularly for studying landscape changes or environmental issues, raises the question of integrating different forms of spatial representation within the same model. Ocelet is an approach for modelling spatial dynamics based on the original concept of interaction graph. Such a graph holds both the structure of a relation between entities of a model and the semantics describing its evolution. The relationships between spatial entities are here translated into interaction graphs and these graphs are made to evolve during a simulation. The concepts on which Ocelet is based can potentially handle two known forms of spatial representation: shapes with contours (vector format) or regular grid cells (raster). The vector format is already integrated in the first version of Ocelet. The integration of raster and the combination of the two remained to be studied and carried out. The aim of the thesis is to first study the issues related to the integration of continuous fields and their representation by regular tiling, both in the Ocelet language and the concepts on which it is based. The dynamic aspects of this integration had to be taken into account and transitions between different forms of geographic data and interaction graphs had to be studied in the light of the concepts formalized. The concepts were then implemented in the Ocelet modelling platform, with the adaptation of both its compiler and runtime. Finally, these new concepts and tools were tested in three very different cases: two models on Reunion Island, the first simulating runoff in Ravine Saint Gilles watershed in the West Coast of the island, the other simulating the spread of invasive plants in the high plains inside the Reunion National Park. The last case describes the spatialisation of a crop model and is applied here to simulate the cereal crop yields in West Africa, in the context of an early warning system for regional crop monitoring
39
Le, Masson Etienne. "Ergodicité et fonctions propres du laplacien sur les grands graphes réguliers." Phd thesis, Université Paris Sud - Paris XI, 2013. http://tel.archives-ouvertes.fr/tel-00866843.
Full textAbstract:
Dans cette thèse, nous étudions les propriétés de concentration des fonctions propres du laplacien discret sur des graphes réguliers de degré fixé dont le nombre de sommets tend vers l'infini. Cette étude s'inspire de la théorie de l'ergodicité quantique sur les variétés. Par analogie avec cette dernière, nous développons un calcul pseudo-différentiel sur les arbres réguliers : nous définissons des classes de symboles et des opérateurs associés, et nous prouvons un certain nombre de propriétés de ces classes de symboles et opérateurs. Nous montrons notamment que les opérateurs sont bornés dans L², et nous donnons des formules de l'adjoint et du produit. Nous nous servons ensuite de cette théorie pour montrer un théorème d'ergodicité quantique pour des suites de graphes réguliers dont le nombre de sommets tend vers l'infini. Il s'agit d'un résultat de délocalisation de la plupart des fonctions propres dans la limite des grands graphes réguliers. Les graphes vérifient une hypothèse d'expansion et ne comportent pas trop de cycles courts, deux hypothèses vérifiées presque sûrement par des suites de graphes réguliers aléatoires.
40
Yahiaoui, Said. "Algorithmes et applications pour la coloration et les alliances dans les graphes." Thesis, Lyon 1, 2013. http://www.theses.fr/2013LYO10274.
Full textAbstract:
Dans cette thèse, nous nous intéressons aux aspects algorithmiques et applications de deux problèmes de graphes, à savoir, la coloration et les alliances. La première partie concerne deux variantes de la coloration de graphes, la coloration Grundy et la coloration forte stricte. Nous commençons par l'étude du nombre Grundy des graphes réguliers. Nous donnons une condition fixe k, nous fournissons une condition nécessaire et suffisante pour que le nombre Grundy d'un graphe régulier soit au moins égal k. Nous caractérisons la classe des graphes cubiques (3-réguliers) pour laquelle le nombre Grundy est égal à 4, et nous présentons un algorithme linéaire pour déterminer le nombre Grundy d'un graphe cubique quelconque. Par ailleurs, en se basant sur la coloration forte stricte pour décomposer les arbres en petites composantes, nous présentons un nouvel algorithme pour l'appariement d'arbres étiquetés, non-ordonnés non-enracinés. Nous montrons que la distance calculée entre deux arbres est une pseudo-métrique. Nos expérimentations sur de larges bases synthétiques et des bases de données réelles confirment nos résultats analytiques et montrent que la distance proposée est précise et son algorithme est scalable. La seconde partie de cette thèse est consacrée aux alliances dans les graphes. Nous proposons un algorithme distribué autostabilisant pour la construction d'alliance offensive globale minimale dans un graphe arbitraire. Nous démontrons que cet algorithme converge sous le démon synchrone en temps linéaire. Ensuite, nous donnons le premier algorithme distribué autostabilisant pour le problème de l'alliance forte globale minimale dans un graphe quelconque. Nous prouvons que cet algorithme est polynomial sous le démon inéquitable distribué. Nous montrons par la suite, comment cet algorithme peut être adapté pour des généralisations du problème, comme la k-alliance forte et l'alliance forte pondérée. Enfin, en se basant sur les propriétés structurelles de l'alliance offensive, nous présentons une solution pour décentraliser le protocole de signalisation SIP. Ceci rend possible son déploiement dans un réseau mobile ad hocThis thesis investigates the algorithmic aspects and applications of two graph problems, namely, colorings and alliances. In the first part, we focus on two variants of the proper vertex coloring, the Grundy coloring and the strict strong coloring. We start by the study of Grundy number for regular graphs. We give a sufficient condition for d-regular graphs with sufficiently large girth to have Grundy number equals d + 1. Then, using graph homomorphism, we obtain a necessary and sufficient condition for d-regular graphs to have Grundy number at least k. Moreover, we characterize cubic graphs (3-regular) for which the Grundy number is d + 1, and present a linear-time algorithm to determine the Grundy number of any arbitrary cubic graph. Subsequently, based on the strict strong coloring, we present an approach for the problem of matching labeled trees. Using this coloring, we propose a new algorithm to deterministically decompose a tree into small components. This leads to an efficient algorithm to measure an accurate distance between unrooted unordered labeled trees. The second part is devoted to the alliances in graphs. We first propose a linear-time self-stabilizing algorithm for the minimal global offensive alliance set problem, under the synchronous distributed scheduler. Then, we give the first self-stabilizing algorithm for the minimal global powerful alliance set problem in arbitrary graphs. Moreover, we show how this algorithm can be adapted to find the minimal global powerful k-alliance and the minimal weighted global powerful alliance sets. We prove that all these algorithms converge in polynomial-time under the unfair distributed scheduler. Finally, based on the structural properties of the offensive alliance, we propose a solution to decentralize the signaling protocol SIP. This enables SIP applications in mobile ad hoc networks
41
Berger, Sacha. "Regular Rooted Graph Grammars." Diss., lmu, 2008. http://nbn-resolving.de/urn:nbn:de:bvb:19-80623.
Full text
42
Curado, Manuel. "Structural Similarity: Applications to Object Recognition and Clustering." Doctoral thesis, Universidad de Alicante, 2018. http://hdl.handle.net/10045/98110.
Full textAbstract:
In this thesis, we propose many developments in the context of Structural Similarity. We address both node (local) similarity and graph (global) similarity. Concerning node similarity, we focus on improving the diffusive process leading to compute this similarity (e.g. Commute Times) by means of modifying or rewiring the structure of the graph (Graph Densification), although some advances in Laplacian-based ranking are also included in this document. Graph Densification is a particular case of what we call graph rewiring, i.e. a novel field (similar to image processing) where input graphs are rewired to be better conditioned for the subsequent pattern recognition tasks (e.g. clustering). In the thesis, we contribute with an scalable an effective method driven by Dirichlet processes. We propose both a completely unsupervised and a semi-supervised approach for Dirichlet densification. We also contribute with new random walkers (Return Random Walks) that are useful structural filters as well as asymmetry detectors in directed brain networks used to make early predictions of Alzheimer's disease (AD). Graph similarity is addressed by means of designing structural information channels as a means of measuring the Mutual Information between graphs. To this end, we first embed the graphs by means of Commute Times. Commute times embeddings have good properties for Delaunay triangulations (the typical representation for Graph Matching in computer vision). This means that these embeddings can act as encoders in the channel as well as decoders (since they are invertible). Consequently, structural noise can be modelled by the deformation introduced in one of the manifolds to fit the other one. This methodology leads to a very high discriminative similarity measure, since the Mutual Information is measured on the manifolds (vectorial domain) through copulas and bypass entropy estimators. This is consistent with the methodology of decoupling the measurement of graph similarity in two steps: a) linearizing the Quadratic Assignment Problem (QAP) by means of the embedding trick, and b) measuring similarity in vector spaces. The QAP problem is also investigated in this thesis. More precisely, we analyze the behaviour of $m$-best Graph Matching methods. These methods usually start by a couple of best solutions and then expand locally the search space by excluding previous clamped variables. The next variable to clamp is usually selected randomly, but we show that this reduces the performance when structural noise arises (outliers). Alternatively, we propose several heuristics for spanning the search space and evaluate all of them, showing that they are usually better than random selection. These heuristics are particularly interesting because they exploit the structure of the affinity matrix. Efficiency is improved as well. Concerning the application domains explored in this thesis we focus on object recognition (graph similarity), clustering (rewiring), compression/decompression of graphs (links with Extremal Graph Theory), 3D shape simplification (sparsification) and early prediction of AD.Ministerio de Economía, Industria y Competitividad (Referencia TIN2012-32839 BES-2013-064482)
43
BRITO, Adriana Priscila de. "Grafos, a fórmula de Euler e os poliedros regulares." Universidade Federal Rural de Pernambuco, 2014. http://www.tede2.ufrpe.br:8080/tede2/handle/tede2/6690.
Full textAbstract:
Submitted by (lucia.rodrigues@ufrpe.br) on 2017-03-28T12:41:18Z
No. of bitstreams: 1
Adriana Priscila de Brito.pdf: 1439366 bytes, checksum: 6c39b441ca6cf64e146c11f1a5822457 (MD5)Made available in DSpace on 2017-03-28T12:41:18Z (GMT). No. of bitstreams: 1 Adriana Priscila de Brito.pdf: 1439366 bytes, checksum: 6c39b441ca6cf64e146c11f1a5822457 (MD5) Previous issue date: 2014-08-08
This presentation provides an introduction to graph theory, making the connection between some of its concepts and the and characterization of Regular Polyhedra. Special emphasis will be given to the study of Eulerian graphs, Euler's Formula, Graphs and Planar Graphs Platonic. Finally, a proposed instructional sequence that focuses on introducing the concept of the graph elementary school students, making connections with the regular polyhedra is presented.
O presente trabalho tem como objetivo principal apresentar uma introdução à Teoria dos Grafos, fazendo a ligação entre alguns dos seus conceitos e a caracterização dos Poliedros Regulares. Será dada uma ênfase especial ao estudo dos Grafos Eulerianos, da Fórmula de Euler, dos Grafos Planares e dos Grafos Platônicos. Por fim, será apresentada uma proposta de sequência didática que tem como foco introduzir o conceito de grafo a alunos do ensino básico, fazendo ligações com os Poliedros Regulares.
44
Pierron, Théo. "Induction Schemes : From Language Separation to Graph Colorings." Thesis, Bordeaux, 2019. http://www.theses.fr/2019BORD0119/document.
Full textAbstract:
Cette thèse présente des résultats obtenus dans deux domaines : la théorie des langages, et la théorie des graphes. En théorie des langages, on s’intéresse à des problèmes de caractérisation de classes de langages réguliers. Le problème générique consiste à déterminer si un langage régulier donné peut être défini dans un certain formalisme. Les méthodes actuelles font intervenir un problème plus général appelé séparation. On présente ici deux types de contributions : une généralisation d’un résultat de décidabilité au cadre des langages de mots infinis, ainsi que des bornes inférieures pour la complexité du problème de séparation. En théorie des graphes, on considère le problème classique de coloration de graphes, où on cherche à attribuer des couleurs aux sommets d’un graphe de sorte que les sommets adjacents reçoivent des couleurs différentes, le but étant d’utiliser le moins de couleurs possible. Dans le cas des graphes peu denses, la méthode de déchargement est un atout majeur. Elle a notamment joué un rôle décisif dans la preuve du théorème des quatre couleurs. Cette méthode peut être vue comme une construction non conventionnelle d’un schéma de preuve par induction, spécifique à la classe de graphes et à la propriété considérées, et où la validité du schéma est rarement immédiate. On utilise des variantes de la méthode de déchargement pour étudier deux types de problèmes de colorationIn this thesis, we present results obtained in two fields: formal language theory and graph theory. In formal language theory, we consider some problems of characterization of classes of regular languages. The generic problem consists in determining whether a given regular language can be defined in a fixed formalism. The current approaches use a more general problem called separation. We present here two types of contributions: a generalization of a decidability result to the setting of infinite words, together with lower bounds for the complexity of the separation problem. In graph theory, we consider the classical problem of graph coloring, where we assign colors to vertices of a graph in such a way that two adjacent vertices receive different colors. The goal is to use the fewest colors. When the graphs are sparse, a crucial tool for this is the discharging method. It is most notably decisive in the proof of the Four-Color Theorem. This method can be seen as an unconventional construction of an inductive proof scheme, specific to the considered problem and graph class, where arguing the validity of the scheme is rarely immediate. We use variants of the discharging method to study two types of coloring problems
45
Barros, Tomas Edson. "Homotopia regular de grafos." [s.n.], 1991. http://repositorio.unicamp.br/jspui/handle/REPOSIP/307360.
Full textAbstract:
Orientador: Jose Carlos de Souza KiihlDissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Científica
Made available in DSpace on 2018-07-13T23:16:04Z (GMT). No. of bitstreams: 1 Barros_TomasEdson_M.pdf: 810196 bytes, checksum: d440e4d7994d16169b2c0b29745be449 (MD5) Previous issue date: 1991
Resumo: Não informado
Abstract: Not informed
Mestrado
Mestre em Matemática
46
Zighem, Ismail. "Etude d'invariants de graphes planaires." Université Joseph Fourier (Grenoble), 1998. http://www.theses.fr/1998GRE10211.
Full textAbstract:
Dans la première partie, nous construisons, à partir de relations linéaires de récurrence, des invariants de graphes planaires 4-réguliers prenant leurs valeurs dans un anneau commutatif. Ces relations représentent des règles récursives bien définies sur cette catégories de graphes, ramenant le calcul des valeurs de l'invariant en ces graphes à une combinaison linéaire d'autres graphes plus réduits. Après avoir dégagé quelques conditions nécessaires pour que ces règles soient mutuellement compatibles, nous montrons en utilisant un résultat de la théorie des systèmes de réécriture qu'elles sont aussi suffisantes. Nous terminons cette partie en évoquant la relation avec le polynôme de Kauffman et en montrant que, pour une évaluation particulière de ses variables, ce polynôme peut être défini à partir de notre invariant. Ce qui constitue une nouvelle preuve d'existence de ce polynôme. La seconde partie aborde le problème de la détermination du nombre d'absorption des graphes de type grille. Dans un premier temps, nous déterminons ce nombre pour les petites grilles croisées (graphes produit croisé de deux chaînes de longueurs k et n, avec k ≤ 33 et n ≤ 40). En utilisant la programmation dynamique, nous présentons pour k fixé un algorithme linéaire en n pour calculer ce nombre. On en déduit alors que ce nombre vérifie des formules simples en fonction de k et n. Ensuite, nous montrons par récurrence, en prenant ces valeurs comme base de récurrence, que ces formules sont vérifiées par ce nombre, pour tous k = 12 ou k ≥ 14 et n ≥ k. Finalement, nous donnons quelques bornes du nombre d'absorption de la grille carrée (graphe produit carré de deux chaînes) qui améliorent les résultats déjà connus
47
Rinke, Sebastian. "Analysis and Adaption of Graph Mapping Algorithms for Regular Graph Topologies." Master's thesis, Universitätsbibliothek Chemnitz, 2009. http://nbn-resolving.de/urn:nbn:de:bsz:ch1-200901453.
Full textAbstract:
The Message Passing Interface (MPI) standard defines virtual topologies that can be applied to systems
of cooperating processes. Among issues regarding a more convenient namespace this may be used to
optimize the placement of MPI processes in order to reduce communication time. That means, the
processes with their main communication paths represent a graph that has to be cost efficiently mapped
onto the graph representing the actual communication network. In this context, this work analyses
and compares state-of-the-art task mapping strategies with respect to running time and their quality
of solutions to the MPI mapping problem. In particular, the focus is on generic strategies that can
be used for arbitrary process/network topologies although, here, the topologies of interest are regular
ones, where the number of processes is greater than the number of processors in the underlying physical
network. Additionally, different measures of mapping quality are discussed and a close correspondence
between the most appropriate, the weighted edge cut, and program execution time is shown. In order
to investigate how mapping quality affects MPI program execution time, some mapping strategies have
been incorporated into Open MPI. Finally, benchmark results prove that optimized process-to-processor
mappings can improve program execution time by up to 60%, compared to the default mapping in many
MPI implementations (linear mapping). The findings in this work can serve as reference not only for MPI
implementors, but also for researchers investigating static process-to-processor mappings, in general.
48
Shiue, Le-Jeng. "Quasi-regular surface representation." [Gainesville, Fla.] : University of Florida, 2004. http://purl.fcla.edu/fcla/etd/UFE0006546.
Full text
49
Gebhardt, René. "Unbounded operators on Hilbert C*-modules: graph regular operators." Doctoral thesis, Universitätsbibliothek Leipzig, 2016. http://nbn-resolving.de/urn:nbn:de:bsz:15-qucosa-213767.
Full textAbstract:
Let E and F be Hilbert C*-modules over a C*-algebra A. New classes of (possibly unbounded) operators t: E->F are introduced and investigated - first of all graph regular operators. Instead of the density of the domain D(t) we only assume that t is essentially defined, that is, D(t) has an trivial ortogonal complement. Then t has a well-defined adjoint. We call an essentially defined operator t graph regular if its graph G(t) is orthogonally complemented and orthogonally closed if G(t) coincides with its biorthogonal complement. A theory of these operators and related concepts is developed: polar decomposition, functional calculus. Various characterizations of graph regular operators are given: (a, a_*, b)-transform and bounded transform. A number of examples of graph regular operators are presented (on commutative C*-algebras, a fraction algebra related to the Weyl algebra, Toeplitz algebra, C*-algebra of the Heisenberg group). A new characterization of operators affiliated to a C*-algebra in terms of resolvents is given as well as a Kato-Rellich theorem for affiliated operators. The association relation is introduced and studied as a counter part of graph regularity for concrete C*-algebras.
50
Borissova, Svetlana. "Regular Round Matroids." CSUSB ScholarWorks, 2016. https://scholarworks.lib.csusb.edu/etd/423.
Full textAbstract:
A matroid M is a finite set E, called the ground set of M, together with a notion of what it means for subsets of E to be independent. Some matroids, called regular matroids, have the property that all elements in their ground set can be represented by vectors over any field. A matroid is called round if its dual has no two disjoint minimal dependent sets. Roundness is an important property that was very useful in the recent proof of Rota's conjecture, which remained an unsolved problem for 40 years in matroid theory. In this thesis, we give a characterization of regular round matroids.