1,722,637 research outputs found
On the 1-edge Hamiltonicity and the caterpillar-forest decomposition of Halin graphs
No full textIn this thesis, we prove that the Halin graph which deletes anyone edge results in a hamiltonian graph, and design an algorithm to find all hamiltonian cycles of Halin graph. We also confirm that Halin graph can be decomposed into two caterpillar forests.1。 Introduction P.4
2。 The 1-edge hamiltonicity algorithm for Halin graphs P.8
3。 On the 1-edge hamiltonicity of Halin graphs P.14
4。 Caterpillar-forest decomposition P.19
5。 Conclusion and future work P.2
Linear arrangement of Halin graphs
Full text linkWe study the Optimal Linear Arrangement (OLA) problem of Halin graphs, one of the simplest classes of non-outerplanar graphs. We present several properties of OLA of general Halin graphs. We prove a lower bound on the cost of OLA of any Halin graph, and define classes of Halin graphs for which the cost of OLA matches this lower bound. We show for these classes of Halin graphs, OLA can be computed in nlog n, where n is the number of vertices
On Halin subgraphs and supergraphs
No full textAbstractIn this paper, we present two complexity results. The first pertains to the problem of finding Halin subgraphs while the second is a supergraph version which asks if a given graph is a subgraph of any Halin graph. Both of these problems are shown to be hard which, in turn, provides somewhat damaging evidence relative to the veracity of heuristic approaches employing Halin graphs as approximations
Design of self-stabilizing algorithms for Halin graphs
No full textDescomponer un grafo en componentes más simples es una tarea fundamental para el diseño de muchos algoritmos. En el caso de los grafos Halin, al estar construidos con un árbol y un ciclo, resulta de especial interés identificar estos componentes, dado que los mismos se han estudiado ampliamente. Existen algunos algoritmos que realizan una identificación de estos componentes en un número de pasos que es proporcional al número de vértices en el grafo; sin embargo, estos algoritmos son muy complejos. En este trabajo se propone una serie de algoritmos para realizar esta tarea. Estos algoritmos se ejecutan tan rápido como los anteriores, son mucho más sencillos, y además tienen la propiedad de ser auto-estabilizantes. Los algoritmos auto-estabilizantes son algoritmos ejecutados coordinadamente por varios procesadores en los que se asegura el correcto funcionamiento del sistema computacional, aún en la presencia de fallas transitorias. Una falla transitoria es el cambio del valor de alguna variable de un procesador, generalmente producido por ruido eléctrico. Estas fallas provocan errores lógicos en la ejecución del algoritmo, pero no alteran el funcionamiento de los procesadores. El algoritmo auto-estabilizante es capaz de detectar estos errores lógicos y corregirlos. Además, usando una lógica similar al primer algoritmo propuesto, se propone un segundo algoritmo que parte al conjunto de aristas del grafo en clases llamadas orejas. Las aristas de cada oreja tienen la propiedad de formar trayectorias simples en el grafo. Este tipo de algoritmos es fundamental para resolver algunos problemas más complejos, dado que facilitan el realizar una búsqueda exhaustiva sobre el grafo. Hasta donde el autor de este trabajo de investigación tiene conocimiento, estos son los primeros algoritmos auto-estabilizantes que resuelven estos problemas para los grafos Halin.Many algorithms benefit from decomposing a graph into simpler components. A Halin graph is the combination of a tree and a cycle. Both of these structures are heavily studied. For this reason, it is helpful to identify these components in Halin graphs. There are some algorithms in Halin graphs that identify the mentioned components in a time that is proportional to the number of vertices; nevertheless, these algorithms are complex. In this document, we propose an algorithm that solves this problem. Our algorithm is as fast as previous algorithms, but it is simpler and have the self-stabilization property. Self-stabilizing algorithms are algorithms that run on several processors and guarantee that the algorithms work properly, even in the presence of transient faults. A transient fault is a change in any variable’s value on any processor, generally produced by electric noise. These faults generate logical errors in the algorithm’s execution but do not alter the processors’ general behavior. A self-stabilizing algorithm is capable of detecting these logical errors and fixing them without external intervention. Using a similar approach, we also propose an algorithm that divides the graph’s edges into classes named ears. The edges of each ear have the property that they simple paths. This algorithm is fundamental to solve more complex problems, as it eases the searching process in a graph. As far as the author of this thesis knows, these are the first self-stabilizing algorithms that solve Halin graphs’ problems
Game chromatic number of Halin graphs
No full textThis thesis discusses the game chromatic number of Halin graphs. We shall
prove that with a few exceptions, all Halin graphs have game chromatic
number 4
Spanning Halin Subgraphs Involving Forbidden Subgraphs
Full text linkIn structural graph theory, connectivity is an important notation with a lot of applications. Tutte, in 1961, showed that a simple graph is 3-connected if and only if it can be generated from a wheel graph by repeatedly adding edges between nonadjacent vertices and applying vertex splitting. In 1971, Halin constructed a class of edge-minimal 3-connected planar graphs, which are a generalization of wheel graphs and later were named “Halin graphs” by Lovasz and Plummer. A Halin graph is obtained from a plane embedding of a tree with no stems having degree 2 by adding a cycle through its leaves in the natural order determined according to the embedding. Since Halin graphs were introduced, many useful properties, such as Hamiltonian, hamiltonian-connected and pancyclic, have been discovered. Hence, it will reveal many properties of a graph if we know the graph contains a spanning Halin subgraph. But unfortunately, until now, there is no positive result showing under which conditions a graph contains a spanning Halin subgraph. In this thesis, we characterize all forbidden pairs implying graphs containing spanning Halin subgraphs. Consequently, we provide a complete proof conjecture of Chen et al. Our proofs are based on Chudnovsky and Seymour’s decomposition theorem of claw-free graphs, which were published recently in a series of papers
The strong chromatic index of complete cubic Halin graphs
No full textAbstractA complete cubic Halin graph is a cubic Halin graph whose characteristic tree is a complete cubic tree, in which all leaves are at the same distance from the root vertex. In this work, we determine the strong chromatic index of the complete cubic Halin graph
On Strong Chromatic Index of Halin Graph
No full textA strong k-edge-coloring of a graph G is an assignment of k colors to the edges of G in such a way that any two edges meeting at a common vertex, or being adjacent to the same edge of G, are assigned different colors. The strong chromatic index of G is the smallest number k for which G has a strong k-edge-coloring. A Halin graph is a planar graph consisting of a tree with no vertex of degree two and a cycle connecting the leaves of the tree. A caterpillar is a tree such that the removal of the leaves becomes a path. In this paper, we show that the strong chromatic index of cubic Halin graph is at most 9. That is, every cubic Halin graph is edge-decomposable into at most 9 induced matchings. Also we study the strong chromatic index of a cubic Halin graph whose tree is a caterpillar
Hamiltonicity of cubic 3-connected k -Halin graphs
No full textAbstract We investigate here how far we can extend the notion of a Halin graph such that hamiltonicity is preserved. Let H = T ∪ C be a Halin graph, T being a tree and C the outer cycle. A k-Halin graph G can be obtained from H by adding edges while keeping planarity, joining vertices of H − C, such that G − C has at most k cycles. We prove that, in the class of cubic 3-connected graphs, all 14-Halin graphs are hamiltonian and all 7-Halin graphs are 1-edge hamiltonian. These results are best possible
On the Halin Tur\'an number of short cycles
Full text linkA Halin graph is a graph constructed by embedding a tree with no vertex of
degree two in the plane and then adding a cycle to join the tree's leaves. The
Halin Tur\'an number of a graph , denoted as \ex_{\hh}(n,F), is the
maximum number of edges in an -vertex Halin graph. In this paper, we give
the exact value of \ex_{\mathcal{H}}(n,C_4), where is a cycle of length
4. We also pose a conjecture for the Halin Tur\'an number of longer cycles.Comment: 17 pages, 8 figure
- …
