{"id":97068,"date":"2009-06-11T00:00:00","date_gmt":"2009-06-11T00:00:00","guid":{"rendered":"https:\/\/www.deberes.net\/tesis\/sin-categoria\/fault-tolerance-results-for-some-families-of-graphs\/"},"modified":"2009-06-11T00:00:00","modified_gmt":"2009-06-11T00:00:00","slug":"fault-tolerance-results-for-some-families-of-graphs","status":"publish","type":"post","link":"https:\/\/www.deberes.net\/tesis\/matematicas\/fault-tolerance-results-for-some-families-of-graphs\/","title":{"rendered":"Fault tolerance results for some families of graphs"},"content":{"rendered":"<h2>Tesis doctoral de <strong> Diego Antonio Gonzalez Moreno <\/strong><\/h2>\n<p>The main objective of this thesis is to study some fault-tolerance results in some families of graphs. The  fault-tolerance of a network is the property that enables it to continue working when some of its  components fails. Usually, networks and thus their representing graphs are connected; that is, there exists  a path between every  two vertices in the graph. Clearly, it is desirable that a network stays connected in  case faults should arise. In this thesis we mainly study a fault-tolerance measure in graphs (corresponding  to the removal of vertices or edges): the (vertex or edge) k-restricted connectivity, dened as the minimum  number of vertices or edges which must be removed such that the resulting graph is disconnected and the  survival components contain at least  k vertices. As particular cases 1-restricted (vertex or edge)  connectivities are just the standard connectivities \u00c2\u00bf and \u00c2\u00bf. The families of graphs that we mainly study are  permutation graphs, cages and (d;g)-cages.     for permutation graphs we establish upper and lower bounds for the k-restricted edge connectivity when  k=2,3, and we look for some  conditions for guaranteeing  optimal  values.  Some other results on the            k-restricted edge connectivity of k4   -free graphs and t-trees are also given.    an (r;g)-cage  (for short, a cage)  is an r-regular graph with girth g and the least possible number of  vertices. In this thesis an upper bound for the order of some (r;g)-cages is given  first. Furthermore, some  new results on the connectivity for some families of cages are presented.     a (d;g)-cage is a graph with degree set d, girth g and with the least possible number of vertices. When  d={r}, (d;g)-cages coincide with  (r;g)-cages. The goal of this part of the thesis is to approach some  structural properties of (d;g)-cages, as a natural extension of the known properties of  (r;g)-cages.  semiregular cages (d={r,r+1}) are mainly studied in this thesis, obtaining results for their order, diameter,  and vertex and edge connectivity.    el principal objetivo de esta tesis es el estudio de la tolerancia a fallos en algunas familias de grafos. La tolerancia  a fallos de una red es la propiedad que permite que \u00e9sta siga funcionando cuando algunas de sus componentes fallan.  usualmente las redes y por tanto los grafos que las modelan son conexos; es decir, para todo par de v\u00e9rtices del grafo  hay  un camino  entre ellos. Es deseable que una red se mantenga conexa si alg\u00fan fallo se produce. En esta tesis,  estudiamos principalmente  una medida de tolerancia a fallos en grafos (correspondiente a la eliminaci\u00f3n de v\u00e9rtices  o aristas): la k-conexidad restringida por v\u00e9rtices o aristas, definida como el m\u00ednimo n\u00famero de v\u00e9rtices o aristas que  deben eliminarse para que el grafo resultante no sea conexo y las componentes restantes contengan al menos k  v\u00e9rtices. Como casos particulares la 1-conexidad restringida (por v\u00e9rtices o aristas) corresponde a  las conexidades  est\u00e1ndar \u00c2\u00bf y  \u00c2\u00bf. La  familias de grafos que estudiamos principalmente  son  los grafos permutaci\u00f3n, las jaulas y las  (d;g)-jaulas.     para los grafos permutaci\u00f3n establecemos cotas superiores e inferiores para la k-conexidad restringida por aristas  cuando k=2,3, y  buscamos  algunas condiciones para garantizar  valores \u00f3ptimos.  Tambi\u00e9n se presentan otros  resultados sobre la k-conexidad por aristas de los grafos libres de k4   y de los t-\u00e1rboles.    una (r;g)-jaula  (de forma abreviada, una jaula)  es un grafo r-regular con cintura g y el menor n\u00famero posible de  v\u00e9rtices. En esta tesis damos en primer lugar un nueva cota superior para el orden de algunas  (r; g)-jaulas. Adem\u00e1s,  se dan algunos nuevos resultados sobre la conexidad de ciertas familias de jaulas.     una (d;g)-jaula es un grafo con conjunto de grados d, cintura g y el menor n\u00famero posible de  v\u00e9rtices. Cuando  d={r}, las (d;g)-jaulas coinciden con las  (r; g)-jaulas. El objetivo de esta parte de la tesis es abordar el estudio de  algunas propiedades estructurales de las  (d;g)-jaulas, como una extensi\u00f3n natural de las propiedades conocidas de  las jaulas. En esta tesis se estudian b\u00e1sicamente las jaulas semirregulares (d={r,r+1}), obteniendo resultados para el  orden, el di\u00e1metro, y la conexidad por v\u00e9rtices o aristas.<\/p>\n<p>&nbsp;<\/p>\n<h3>Datos acad\u00e9micos de la tesis doctoral \u00ab<strong>Fault tolerance results for some families of graphs<\/strong>\u00ab<\/h3>\n<ul>\n<li><strong>T\u00edtulo de la tesis:<\/strong>\u00a0 Fault tolerance results for some families of graphs <\/li>\n<li><strong>Autor:<\/strong>\u00a0 Diego Antonio Gonzalez Moreno <\/li>\n<li><strong>Universidad:<\/strong>\u00a0 Polit\u00e9cnica de catalunya<\/li>\n<li><strong>Fecha de lectura de la tesis:<\/strong>\u00a0 06\/11\/2009<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<h3>Direcci\u00f3n y tribunal<\/h3>\n<ul>\n<li><strong>Director de la tesis<\/strong>\n<ul>\n<li>Francisco Javier Marcote Ordax<\/li>\n<\/ul>\n<\/li>\n<li><strong>Tribunal<\/strong>\n<ul>\n<li>Presidente del tribunal: Miguel \u00e1ngel Fiol mora <\/li>\n<li>mirka Miller (vocal)<\/li>\n<li>gabriela Araujo pardo (vocal)<\/li>\n<li>josep F\u00ed\u00a0brega canudas (vocal)<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Tesis doctoral de Diego Antonio Gonzalez Moreno The main objective of this thesis is to study some fault-tolerance results in [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""}},"footnotes":""},"categories":[126,15596],"tags":[199070,67343,199071,29242,15610,45569],"class_list":["post-97068","post","type-post","status-publish","format-standard","hentry","category-matematicas","category-politecnica-de-catalunya","tag-diego-antonio-gonzalez-moreno","tag-francisco-javier-marcote-ordax","tag-gabriela-araujo-pardo","tag-josep-fi-brega-canudas","tag-miguel-angel-fiol-mora","tag-mirka-miller"],"_links":{"self":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts\/97068","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/comments?post=97068"}],"version-history":[{"count":0,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts\/97068\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/media?parent=97068"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/categories?post=97068"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/tags?post=97068"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}