To see the other types of publications on this topic, follow the link: Circulant graphs.
Dissertations / Theses on the topic 'Circulant 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 'Circulant 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
Kotzagiannidis, Madeleine S. "From spline wavelet to sampling theory on circulant graphs and beyond : conceiving sparsity in graph signal processing." Thesis, Imperial College London, 2017. http://hdl.handle.net/10044/1/56614.
Full textAbstract:
Graph Signal Processing (GSP), as the field concerned with the extension of classical signal processing concepts to the graph domain, is still at the beginning on the path toward providing a generalized theory of signal processing. As such, this thesis aspires to conceive the theory of sparse representations on graphs by traversing the cornerstones of wavelet and sampling theory on graphs. Beginning with the novel topic of graph spline wavelet theory, we introduce families of spline and e-spline wavelets, and associated filterbanks on circulant graphs, which lever- age an inherent vanishing moment property of circulant graph Laplacian matrices (and their parameterized generalizations), for the reproduction and annihilation of (exponen- tial) polynomial signals. Further, these families are shown to provide a stepping stone to generalized graph wavelet designs with adaptive (annihilation) properties. Circulant graphs, which serve as building blocks, facilitate intuitively equivalent signal processing concepts and operations, such that insights can be leveraged for and extended to more complex scenarios, including arbitrary undirected graphs, time-varying graphs, as well as associated signals with space- and time-variant properties, all the while retaining the focus on inducing sparse representations. Further, we shift from sparsity-inducing to sparsity-leveraging theory and present a novel sampling and graph coarsening framework for (wavelet-)sparse graph signals, inspired by Finite Rate of Innovation (FRI) theory and directly building upon (graph) spline wavelet theory. At its core, the introduced Graph-FRI-framework states that any K-sparse signal residing on the vertices of a circulant graph can be sampled and perfectly reconstructed from its dimensionality-reduced graph spectral representation of minimum size 2K, while the structure of an associated coarsened graph is simultaneously inferred. Extensions to arbitrary graphs can be enforced via suitable approximation schemes. Eventually, gained insights are unified in a graph-based image approximation framework which further leverages graph partitioning and re-labelling techniques for a maximally sparse graph wavelet representation.
2
Parshina, Olga. "Structures périodiques en mots morphiques et en colorations de graphes circulants infinis." Thesis, Lyon, 2019. http://www.theses.fr/2019LYSE1071/document.
Full textAbstract:
Cette thèse est composée de deux parties : l’une traite des propriétés combinatoires de mots infinis et l’autre des problèmes de colorations des graphes.La première partie du manuscrit concerne les structures régulières dans les mots apériodiques infinis, à savoir les sous-séquences arithmétiques et les premiers retours complets.Nous étudions la fonction qui donne la longueur maximale d’une sous-séquence arithmétique monochromatique (une progression arithmétique) en fonction de la différence commune d pour une famille de mots morphiques uniformes, qui inclut le mot de Thue-Morse. Nous obtenons la limite supérieure explicite du taux de croissance de la fonction et des emplacements des progressions arithmétiques de longueurs maximales et de différences d. Pour étudier des sous-séquences arithmétiques périodiques dans des mots infinis, nous définissons la notion d'indice arithmétique et obtenons des bornes supérieures et inférieures sur le taux de croissance de la fonction donnant l’indice arithmétique dans la même famille de mots.Dans la même veine, une autre question concerne l’étude de deux nouvelles fonctions de complexité de mots infinis basées sur les notions de mots ouverts et fermés. Nous dérivons des formules explicites pour les fonctions de complexité ouverte et fermée pour un mot d'Arnoux-Rauzy sur un alphabet de cardinalité finie.La seconde partie de la thèse traite des colorations parfaites (des partitions équitables) de graphes infinis de degré borné. Nous étudions les graphes de Caley de groupes additifs infinis avec un ensemble de générateurs fixé. Nous considérons le cas où l'ensemble des générateurs est composé d'entiers de l'intervalle [-n, n], et le cas où les générateurs sont des entiers impairs de [-2n-1, 2n+1], où n est un entier positif. Pour les deux familles de graphes, nous obtenons une caractérisation complète des colorations parfaites à deux couleursThe content of the thesis is comprised of two parts: one deals with combinatorial properties of infinite words and the other with graph coloring problems.The first main part of the manuscript concerns regular structures in infinite aperiodic words, such as arithmetic subsequences and complete first returns.We study the function that outputs the maximal length of a monochromatic arithmetic subsequence (an arithmetic progression) as a function of the common difference d for a family of uniform morphic words, which includes the Thue-Morse word. We obtain the explicit upper bound on the rate of growth of the function and locations of arithmetic progressions of maximal lengths and difference d. To study periodic arithmetic subsequences in infinite words we define the notion of an arithmetic index and obtain upper and lower bounds on the rate of growth of the function of arithmetic index in the same family of words.Another topic in this direction involves the study of two new complexity functions of infinite words based on the notions of open and closed words. We derive explicit formulae for the open and closed complexity functions for an Arnoux-Rauzy word over an alphabet of finite cardinality.The second main part of the thesis deals with perfect colorings (a.k.a. equitable partitions) of infinite graphs of bounded degree. We study Caley graphs of infinite additive groups with a prescribed set of generators. We consider the case when the set of generators is composed of integers from the interval [-n,n], and the case when the generators are odd integers from [-2n-1,2n+1], where n is a positive integer. For both families of graphs, we obtain a complete characterization of perfect 2-colorings
3
Roussel, Nicolas. "Circular coloring and acyclic choosability of graphs." Thesis, Bordeaux 1, 2009. http://www.theses.fr/2009BOR13889/document.
Full textAbstract:
Dans cette thèse, nous nous intéressons à la coloration circulaire des graphes planaires. Des bornes supérieures ont été données pour des graphes avec degré maximum borné, avec girth, la longueur de son plus petit cycle, bornée, avec des cycles manquants, etc. Ici nous donnerons de nouvelles bornes pour les graphes avec degré moyen maximum borné. Nous étudions également la coloration totale et la coloration (d,1)-totale de plusieurs familles infinies de graphes. Nous décrivons le nouveau concept de coloration (d,1)-totale circulaire. Enfin, nous discutons les conditions nécessaires pour qu'un graphe planaire admette une coloration acyclique par listes de taille 4In this thesis, we study the circular coloring of planar graphs. Upper bounds have been given for graphs with bounded maximum degree, with bounded girth, that is the length of its smallest cycle, with missing cycles, and so on. It has also been studied for graphs with bounded maximum average degree. Here we give new upper bounds for that latter case. We also study the total coloring and ($d,1$)-total labeling of a few infinite families of graphs and describe the new concept of circular ($d,1$)-total labeling of graphs. In the last part, we will discuss conditions for a planar graph to be acyclically $4$-choosable
4
Pêcher, Arnaud. "Des multiples facettes des graphes circulants." Habilitation à diriger des recherches, Université Sciences et Technologies - Bordeaux I, 2008. http://tel.archives-ouvertes.fr/tel-00332976.
Full textAbstract:
Ce document présente une vue synthétique de mes travaux de recherche menés ces cinq dernières années, au sein du LaBRI.Les activités de recherche d'un enseignant-chercheur ne s'inscrivent pas souvent dans un plan de recherche soigneusement pensé. Elles évoluent en fonction de multiples impondérables, dont notamment les rencontres avec d'autres chercheurs ou encore les opportunités ``stratégiques'' de financement. De ce fait, il n'est pas toujours facile de dégager un fil conducteur qui permette de regrouper un ensemble des résultats obtenus ``au fil de l'eau'' sans avoir recours à des raccourcis un peu ``artificiels''.
Lorsque je me suis efforcé de dégager un point commun à mes travaux, je me suis aperçu que des objets mathématiques bien particuliers n'étaient jamais très loin de mes activités: les groupes cycliques finis. En creusant un peu plus cette perception, il m'est apparu que mes travaux accordent une place considérable à des graphes élémentaires associés aux groupes cycliques, dits graphes ou encore webs.
Ce document est donc consacré à la mise en valeur des multiples facettes de ces graphes. ``Facettes'' est ici à double sens, puisqu'une partie conséquente de mes résultats est précisément dédiée à la détermination des facettes de certains polytopes associés aux graphes!
Sur la forme, les preuves ont été omises afin d'alléger le texte, à l'exception de quelques preuves sélectionnées pour leur brièveté et pour la pertinence du résultat qu'elles procurent. Des hyperliens pointent vers la version anglaise des preuves manquantes, telles qu'elles figurent dans le recueil d'articles en annexe. Pour faciliter également la lecture, l'index à la fin de l'ouvrage redonne toutes les principales définitions.
Sur le fond, ce document est structuré de la manière suivante.
Le premier chapitre est consacré aux principaux résultats connus sur les graphes parfaits. Ceci permet de définir les objets mathématiques utilisés par la suite, et de rappeler l'extraordinaire richesse conceptuelle des graphes parfaits.
Dans le second chapitre, nous abordons un raffinement de la coloration usuelles des graphes, appelé ``coloration circulaire''. Cette coloration est à l'origine d'une généralisation récente des graphes parfaits: les ``graphes circulaires-parfaits''. Nous étudions la possibilité d'une caractérisation analogue à celles des graphes parfaits, que ce soit par sous-graphes exclus ou bien polyédrale.
Dans le troisième chapitre, nous nous intéressons à une généralisation naturelle des webs: ``les graphes quasi-adjoints''. Il s'agit d'une sous-famille des graphes sans griffe, et à ce titre, l'étude de leur polytope des stables est de première importance.
Dans le quatrième chapitre, nous menons des investigations directes sur le polytope des stables des graphes sans griffe.
La conclusion est donnée dans le dernier et cinquième chapitre, qui contient également une brève présentation de quelques résultats préliminaires quant au calcul en temps polynomial du nombre circulaire-chromatique des graphes circulaires-parfaits et au calcul du nombre de stabilité des graphes quasi-adjoints. Tout repose sur l'introduction d'un nouveau polytope construit à partir des webs ...
5
Schubert, Michael [Verfasser]. "Circular flows on signed graphs / Michael Schubert." Paderborn : Universitätsbibliothek, 2018. http://d-nb.info/1161798684/34.
Full text
6
Micheneau, Cyrille. "Graphes récursifs circulants, communications vagabondes et simulation." Bordeaux 1, 1996. http://www.theses.fr/1996BOR10678.
Full textAbstract:
Le domaine des graphes et reseaux d'interconnexion se propose d'etudier les problemes de communications dans les machines paralleles. La premiere partie de cette these est une etude complete des graphes recursifs circulants g(cdm,d). Nous commencons par une etude structurelle de ces graphes (proprietes, diametre, construction recursive). Nous decomposons ensuite ces graphes en cycles hamiltoniens arete-disjoints. Puis, nous donnons un algorithme de construction d'arbres arcs-disjoints dans le temps pour effectuer un echange total en temps optimal selon le protocole delta-port, temps constant. Dans une seconde partie, nous nous interessons a la diffusion vagabonde et a l'echange total vagabond dans quelques graphes (chemin, cycle, arbres d-aires complets et hypercubes). Nous donnons des bornes maximales pour les temps necessaires a l'execution de ces schemas de communication, et des algorithmes atteignant ces bornes. Ce nouveau modele introduit en 1993, est adapte a des machines paralleles dont les routeurs auraient pas ou peu de memoire locale. Dans la troisieme partie de ce document, nous presentons notre realisation logicielle, griap, destinee a la validation de schemas de communication. Griap se compose de differents modules permettant de generer les listes d'adjacences de familles de graphes, de simuler l'execution de schemas de diffusion ou du routage intensif en modele hot potato. Une interface graphique a ete adaptee pour interpreter facilement la grande quantite d'informations emanant d'une simulation
7
Holt, Tracy Lance. "On the Attainability of Upper Bounds for the Circular Chromatic Number of K4-Minor-Free Graphs." Digital Commons @ East Tennessee State University, 2008. https://dc.etsu.edu/etd/1916.
Full textAbstract:
Let G be a graph. For k ≥ d ≥ 1, a k/d -coloring of G is a coloring c of vertices of G with colors 0, 1, 2, . . ., k - 1, such that d ≤ | c(x) - c(y) | ≤ k - d, whenever xy is an edge of G. We say that the circular chromatic number of G, denoted χc(G), is equal to the smallest k/d where a k/d -coloring exists. In [6], Pan and Zhu have given a function μ(g) that gives an upper bound for the circular-chromatic number for every K4-minor-free graph Gg of odd girth at least g, g ≥ 3. In [7], they have shown that their upper bound in [6] can not be improved by constructing a sequence of graphs approaching μ(g) asymptotically. We prove that for every odd integer g = 2k + 1, there exists a graph Gg ∈ G/K4 of odd girth g such that χc(Gg) = μ(g) if and only if k is not divisible by 3. In other words, for any odd g, the question of attainability of μ(g) is answered for all g by our results. Furthermore, the proofs [6] and [7] are long and tedious. We give simpler proofs for both of their results.
8
Zacharopoulos, Panagiotis [Verfasser]. "Asymmetric game perfect graphs and the circular coloring game of weighted graphs / Panagiotis Zacharopoulos. Fakultät für Mathematik." Bielefeld : Universitätsbibliothek Bielefeld, Hochschulschriften, 2012. http://d-nb.info/1024640639/34.
Full text
9
Lin, Wensong. "Circular chromatic numbers and distance two labelling numbers of graphs." HKBU Institutional Repository, 2004. http://repository.hkbu.edu.hk/etd_ra/591.
Full text
10
Wooten, Trina Marcella. "Finding Edge and Vertex Induced Cycles within Circulants." Digital Commons @ East Tennessee State University, 2008. https://dc.etsu.edu/etd/1985.
Full textAbstract:
Let H be a graph. G is a subgraph of H if V (G) ⊆ V (H) and E(G) ⊆ E(H). The subgraphs of H can be used to determine whether H is planar, a line graph, and to give information about the chromatic number. In a recent work by Beeler and Jamison [3], it was shown that it is difficult to obtain an automorphic decomposition of a triangle-free graph. As many of their examples involve circulant graphs, it is of particular interest to find triangle-free subgraphs within circulants. As a cycle with at least four vertices is a canonical example of a triangle-free subgraph, we concentrate our efforts on these. In this thesis, we will state necessary and sufficient conditions for the existence of edge induced and vertex induced cycles within circulants.
11
Kuhnert, Sebastian. "Space efficient algorithms for graph isomorphism and representation." Doctoral thesis, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät, 2016. http://dx.doi.org/10.18452/17447.
Full textAbstract:
Beim Graphisomorphieproblem geht es um die Frage, ob zwei Graphen bis auf Knotenumbenennungen die gleiche Struktur haben. Es ist eines der wenigen verbleibenden natürlichen Probleme, für die weder ein Polynomialzeitalgorithmus noch NP-Härte bekannt ist. Aus dieser Situation ist ein Forschungszweig erwachsen, der effiziente Isomorphiealgorithmen für eingeschränkte Graphklassen entwickelt. Der Hauptbeitrag dieser Arbeit besteht in Logspace-Algorithmen, die das Isomorphieproblem für k-Bäume, Intervallgraphen, sowie Helly- und Proper-Kreisbogengraphen lösen. Dies verbessert zuvor bekannte parallele Algorithmen und führt zu einer vollständigen Klassifikation der Komplexität dieser Probleme, da für sie auch Logspace-Härte nachgewiesen wird. Tatsächlich leisten die vorgestellten Algorithmen mehr: Im Fall der k-Bäume berechnet der Algorithmus kanonische Knotenbenennungen mit O(k log n) Platz. Eine alternative Implementation des Algorithmus kommt mit O((k+1)!n) Zeit aus – hierbei ist n die Anzahl der Knoten – und ist damit der schnellste bekannte FPT-Algorithmus für Isomorphie von k-Bäumen. Die Algorithmen für Intervall- und Kreisbogengraphen berechnen kanonische Repräsentationen – das heißt, sie weisen jedem Knoten ein Intervall (beziehungsweise einen Kreisbogen) zu, sodass diese sich genau dann schneiden, wenn die zugehörigen Knoten benachbart sind, und isomorphe Eingabegraphen das gleiche Intervallmodell (beziehungsweise Kreisbogenmodell) erhalten. Außerdem werden auch Logspace-Algorithmen angegeben, die Intervallrepräsentationen mit zusätzlichen Eigenschaften berechnen – oder erkennen, dass dies nicht möglich ist: Für die resultierenden Intervallmodelle kann gefordert werden, dass sie proper sind (also kein Intervall ein anderes enthält), dass sie unit sind (also alle Intervalle die gleiche Länge haben) oder dass die Längen der paarweisen Schnitte (und optional der einzelnen Intervalle) vorgegebenen Werten entsprechen.The graph isomorphism problem deals with the question if two graphs have the same structure up to renaming their vertices. It is one of the few remaining natural problems for which neither a polynomial-time algorithm nor NP-hardness is known. This situation has led to a branch of research that develops efficient algorithms for special cases of the graph isomorphism problem, where the input graphs are required to be from restricted graph classes. The main contribution of this thesis comprises of logspace algorithms that solve the isomorphism problem for k-trees, interval graphs, Helly circular-arc graphs and proper circular-arc graphs. This improves previously known parallel algorithms and leads to a complete classification of the complexity of these problems, as they are also shown to be hard for logspace. In fact, these algorithms achieve more: In the case of k-trees, the algorithm computes canonical labelings in space O(k log n). An alternative implementation runs in time O((k+1)!n), where n is the number of vertices, yielding the fastest known FPT algorithm for k-tree isomorphism. The algorithms for interval and circular-arc graphs actually compute canonical representations, i.e., each vertex is assigned an interval (or arc) such that these intersect each other if and only if the corresponding vertices are adjacent, and isomorphic input graphs receive the same interval (or arc) model. This thesis also presents logspace algorithms that compute interval representations with additional properties, or detect that this is not possible: The resulting interval models can be required to be proper (no interval contains another), unit (all intervals have the same length), or to satisfy prescribed lengths for pairwise intersections (and possibly prescribed lengths of intervals).
12
Topanotti, Daniel Rodrigues. "Trigonometria, relação entre movimentos circulares e gráficos com a ajuda do GeoGebra." reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, 2017. http://hdl.handle.net/10183/172962.
Full textAbstract:
Essa dissertação analisará uma abordagem investigativa de ensino de funções trigonométricas que prioriza a compreensão da relação entre movimentos circulares em diferentes velocidades com a formação gráfica gerada por esses movimentos. Com o auxílio do software Geogebra, diferentes movimentos foram criados, o que proporcionou a investigação gráfica por parte dos alunos. A atividade foi realizada no laboratório de informática onde, constantemente, houve investigação por parte dos alunos e intervenções significativas por parte do professor. Escolheu-se para essa pesquisa uma análise qualitativa embasada no processo descritivo das ações ocorridas em sala de aula. Para conhecer as características dessa abordagem, foi utilizado um estudo de casos. Após a atividade, os alunos conseguiram interpretar os principais movimentos gerados na circunferência e traduzi-los na sua forma gráfica. A análise mostra que os alunos não somente conseguiram desenvolver significados aos movimentos circulares, como também interpretaram corretamente situações cotidianas estabelecidas pelo professor ao fim do trabalhoThis dissertation will analyze an investigative approach to the teaching of trigonometric functions that prioritizes the understanding of the relation between circular movements at different speeds with the graphical formation generated by these movements. With the help of the software Geogebra, different movements were created, which provided the graphic investigation by the students. The activity was carried out in the computer lab where, constantly, there was investigation by the students and significant interventions by the teacher. For this research, a qualitative analysis based on the descriptive process of the actions taken in the classroom was chosen. To know the characteristics of this approach, a case study was used. After the activity, the students were able to interpret the main movements generated on the circumference and translate them into their graphic form. The analysis shows that the students not only managed to develop meanings to the circular movements, but also correctly interpreted daily situations established by the teacher at the end of the work
13
Noel, Jonathan A. "Extremal combinatorics, graph limits and computational complexity." Thesis, University of Oxford, 2016. https://ora.ox.ac.uk/objects/uuid:8743ff27-b5e9-403a-a52a-3d6299792c7b.
Full textAbstract:
This thesis is primarily focused on problems in extremal combinatorics, although we will also consider some questions of analytic and algorithmic nature. The d-dimensional hypercube is the graph with vertex set {0,1}d where two vertices are adjacent if they differ in exactly one coordinate. In Chapter 2 we obtain an upper bound on the 'saturation number' of Qm in Qd. Specifically, we show that for m ≥ 2 fixed and d large there exists a subgraph G of Qd of bounded average degree such that G does not contain a copy of Qm but, for every G' such that G ⊊ G' ⊆ Qd, the graph G' contains a copy of Qm. This result answers a question of Johnson and Pinto and is best possible up to a factor of O(m). In Chapter 3, we show that there exists ε > 0 such that for all k and for n sufficiently large there is a collection of at most 2(1-ε)k subsets of [n] which does not contain a chain of length k+1 under inclusion and is maximal subject to this property. This disproves a conjecture of Gerbner, Keszegh, Lemons, Palmer, Pálvölgyi and Patkós. We also prove that there exists a constant c ∈ (0,1) such that the smallest such collection is of cardinality 2(1+o(1))ck for all k. In Chapter 4, we obtain an exact expression for the 'weak saturation number' of Qm in Qd. That is, we determine the minimum number of edges in a spanning subgraph G of Qd such that the edges of E(Qd)\E(G) can be added to G, one edge at a time, such that each new edge completes a copy of Qm. This answers another question of Johnson and Pinto. We also obtain a more general result for the weak saturation of 'axis aligned' copies of a multidimensional grid in a larger grid. In the r-neighbour bootstrap process, one begins with a set A0 of 'infected' vertices in a graph G and, at each step, a 'healthy' vertex becomes infected if it has at least r infected neighbours. If every vertex of G is eventually infected, then we say that A0 percolates. In Chapter 5, we apply ideas from weak saturation to prove that, for fixed r ≥ 2, every percolating set in Qd has cardinality at least (1+o(1))(d choose r-1)/r. This confirms a conjecture of Balogh and Bollobás and is asymptotically best possible. In addition, we determine the minimum cardinality exactly in the case r=3 (the minimum cardinality in the case r=2 was already known). In Chapter 6, we provide a framework for proving lower bounds on the number of comparable pairs in a subset S of a partially ordered set (poset) of prescribed size. We apply this framework to obtain an explicit bound of this type for the poset 𝒱(q,n) consisting of all subspaces of 𝔽qnordered by inclusion which is best possible when S is not too large. In Chapter 7, we apply the result from Chapter 6 along with the recently developed 'container method,' to obtain an upper bound on the number of antichains in 𝒱(q,n) and a bound on the size of the largest antichain in a p-random subset of 𝒱(q,n) which holds with high probability for p in a certain range. In Chapter 8, we construct a 'finitely forcible graphon' W for which there exists a sequence (εi)∞i=1 tending to zero such that, for all i ≥ 1, every weak εi-regular partition of W has at least exp(εi-2/25log∗εi-2) parts. This result shows that the structure of a finitely forcible graphon can be much more complex than was anticipated in a paper of Lovász and Szegedy. For positive integers p,q with p/q ❘≥ 2, a circular (p,q)-colouring of a graph G is a mapping V(G) → ℤp such that any two adjacent vertices are mapped to elements of ℤp at distance at least q from one another. The reconfiguration problem for circular colourings asks, given two (p,q)-colourings f and g of G, is it possible to transform f into g by recolouring one vertex at a time so that every intermediate mapping is a p,q-colouring? In Chapter 9, we show that this question can be answered in polynomial time for 2 ≤ p/q < 4 and is PSPACE-complete for p/q ≥ 4.
14
Dutta, Atri. "Optimal cooperative and non-cooperative peer-to-peer maneuvers for refueling satellites in circular constellations." Diss., Atlanta, Ga. : Georgia Institute of Technology, 2009. http://hdl.handle.net/1853/28082.
Full textAbstract:
Thesis (M. S.)--Aerospace Engineering, Georgia Institute of Technology, 2009.Committee Chair: Panagiotis Tsiotras; Committee Member: Eric Feron; Committee Member: Joseph Saleh; Committee Member: Ryan Russell; Committee Member: William Cook
15
Lamme, Anton. "Återbruksbyn : Grafiskt arbete som identifierar Återbruksbyn i Växjö." Thesis, Linnéuniversitetet, Institutionen för design (DE), 2015. http://urn.kb.se/resolve?urn=urn:nbn:se:lnu:diva-43662.
Full textAbstract:
Detta projektet handlar om att ge Återbruksbyn i Växjö en grafisk identitet och profil. Återbruksbyn är ett arbete startat av Växjö kommun och kooperativet Macken som handlar om att bygga en mötesplats för oss som vill byta, köpa, sälja, skänka och återbruka begagnade saker i stället för att slänga dem. Det är en plats som kommer fokusera på cirkulär ekonomi och introducera detta system som ett alternativ till det vi har i dagsläget. Min roll och syftet med detta projekt har varit att analysera verksamheten och skapa en logotyp med tillhörande grafisk profil där de äkta värderingarna visas och representeras på ett korrekt sätt. Detta är min process.This project is about creating a graphic identity and profile for Återbruksbyn, Växjö. Återbruksbyn is a project created by Växjö municipality and the cooperative Macken, and it is about building a central space and meeting point for people who want to buy, sell, exchange, give away and reuse old products instead of throwing them away. It is a place that focuses on circular economy and wants to introduce this alternative system to the people of Växjö. My role and purpose with this project has been to analyse Återbruksbyn and its values, and through that, create a graphic identity that reflects these values and goals. This is my process.
16
Lesur, Benoît. "Validations de modèles numériques de grands réseaux pour l'optimisation d'antennes à pointage électronique en bande Ka." Thesis, Limoges, 2017. http://www.theses.fr/2017LIMO0111/document.
Full textAbstract:
L'essor des communications par satellites et des nouvelles technologies de l'information et de la communication conduisent à une demande croissante de la part des utilisateurs. Ainsi, afin de répondre à ces nouveaux besoins, des services proposant de la connectivité en vol pour les passagers des compagnies aériennes voient le jour. Les travaux présentés dans ce mémoire portent sur la réalisation de modèles numériques rigoureux de grands réseaux d'antennes destinés à couvrir ce champ applicatif. Après une mise en contexte et un rappel des contraintes liées aux réseaux d'antennes, des véhicules de test numériques et expérimentaux, permettant de valider les méthodologies de modélisation, sont réalisés. La modélisation d'un grand panneau rayonnant à bipolarisation circulaire et acceptant d'importants angles de dépointage est enfin abordée. Cette étude permet alors de statuer sur les performances du panneau, en fonction des consignes de pointage et des dispersions éventuelles des chaînes activesThe rapid expansion of satellite communications and information and communications technology led to an increasing demand from end-users. Hence, services offering In-Flight Connectivity for airlines passengers are emerging. This work is focused on the implementation of accurate numerical models of large antenna arrays meant for this scope. After having put things into context and recalled issues linked to antenna arrays, numerical and experimental test vehicles are made, allowing to validate the modelling methodologies. Finally, the modelling of a large, dual circular polarization and wide-angle scanning radiating panel is addressed. This study then allows to estimate the performance of the panel function of steering requirements and possible dispersions from the active channels
17
Tu, Sheng-hsien, and 涂勝獻. "Star extremal of circulant graphs." Thesis, 2004. http://ndltd.ncl.edu.tw/handle/55848476597136511381.
Full textAbstract:
碩士國立中山大學
應用數學系研究所
92
A graph is called star extremal if its fractional chromatic number is equal to its circular chromatic number. Given integers n,k,k'' such that 1<=k<=k''<=n/2,the circulant graph G(n,S_k,k'') has vertex set [n]={0,1,2,...,n-1} in which i~j if k<=|i-j|<=k'' or n-k''<= |i-j|<=n-k. It was known that for n=q(k+k'')+r,where 0<=r
18
Yen, Chi-Mei, and 顏綺美. "Independence Number of Circulant Graphs." Thesis, 2015. http://ndltd.ncl.edu.tw/handle/64224102993530882083.
Full textAbstract:
碩士國立交通大學
應用數學系所
103
Let G = (V,E) be a simple graph. An independent set I is a vertex subset of V such that no two vertices in I are adjacent in G. A maximum independent set is an independent set with the largest cardinality, this cardinality is known as the independence number of G, denoted by α(G). Given n ≥ 1 and a set S ⊆ {1,2,··· ,⌊n/2⌋}, the circulant graph C_{n,S} of order n with generating set S is a graph whose vertex set is V = Z_n and for i,j ∈ V with i > j, {i,j} is an edge of C_{n,S} if and only if min{i−j,n−i + j}∈ S. Finding the independence number of a general graph, even a planar graph, is known to be NP-hard. Therefore, the study of this parameter focuses on special graphs over the years, this thesis is of no exception. Motivated by its applications on communications, we focus on the class of circulant graphs. As a consequence of study, we are able to derive bounds of α(C_{n,S}) mainly when S is a set of consecutive integers. Furthermore, with the application of Pigeon-hole Principle, we obtain several exact values of α(C_{n,S}), i.e., for some special n and respectively S, we have the answer of α(C_{n,S}).
19
Chen, Y.-Chuang, and 陳玉專. "Hamiltonian Decompositions of Recursive Circulant Graphs." Thesis, 2000. http://ndltd.ncl.edu.tw/handle/26045657867042044696.
Full textAbstract:
碩士國立交通大學
資訊科學系
88
A k-regular graph G is hamiltonian decomposable if its edge-set can be partitioned into k/2 hamiltonian cycles when k is even or (k-1)/2 hamiltonian cycles and a perfect matching when k is odd. In this paper, we prove that every recursive circulant graph is hamiltonian decomposable.
20
Chen, Wen-Wei, and 陳文暐. "Connected Domination Number in Circulant Graphs." Thesis, 2017. http://ndltd.ncl.edu.tw/handle/f4vm83.
Full textAbstract:
碩士國立交通大學
應用數學系所
105
Let G be a graph. A set S⊆V(G) is a connected dominating set of G if S is a dominating set of G and the subgraph induced by S is connected. The minimum size among connected dominating sets of G is the connected domination number of G, denoted by γ_c(G). For an integer n, let D be a subset of {1,2,...,⌊n/2⌋}. A circulant graph of order n with the jump set D, denoted by G(n;D), is a graph whose vertex set and edge set are, respectively, defined by V(G(n;D)) = {v_i | i ∈ {0,1,...,n-1}}, and E(G(n;D)) = {{v_i,v_j} | |i-j|_n ∈ D, i,j ∈ {0,1,...,n-1}}, where |i-j|_n = min{|i-j|, n-|i-j|}. In this thesis, we study γ_c(G(n;D)), where D is a set of consecutive integers. As a consequence, for certain D and n, we obtained the exact value of γ_c(G(n;D)).
21
MengYu-Lin and 林孟玉. "Independent Spanning Trees on Recursive Circulant Graphs." Thesis, 2003. http://ndltd.ncl.edu.tw/handle/94651256289912105016.
Full textAbstract:
碩士國立臺灣科技大學
資訊管理系
91
Two spanning trees of a given graph G = (V, E) are said to be independent if they are rooted at the same vertex, say r, and for each vertex v Î V\{r} the two paths from r to v, one path in each tree, are internally disjoint. A set of spanning trees of G is said to be independent if they are pairwise independent. Zehavi and Itai conjectured that any k-connected graph has k independent spanning trees rooted at an arbitrary vertex. This conjecture is still open for k > 3. Broadcasting in a distributed system is the message dissemination from a source node to every other node in the system. We can design a fault-tolerant broadcasting scheme based on independent spanning trees of a network. The fault-tolerance can be achieved by sending k copies of the message along k independent spanning trees rooted at the source node. The recursive circulant graph was proposed by Park and Chwa in 1994. Let G(cdm,d) denote a recursive circulant graph. Then G has N=cdm vertices, where 0
22
Cheng, Fei-Wen, and 鄭斐文. "Fault-Tolerant Pancyclicity of Recursive Circulant Graphs." Thesis, 2003. http://ndltd.ncl.edu.tw/handle/64178977378467872165.
Full textAbstract:
碩士國立交通大學
資訊科學系
91
In this thesis, we consider the weakly pancyclic property on the faulty recursive circulant graph, $G(N,d)$. $G(N,d)$ was proposed in 1994 by Park and Chwa \cite{Park}. They also proved that $G(cd^k,d)$ is regular graph. Let $F$ be any faulty set in $G(cd^k,d)$ such that $F\subset E(G(cd^k,d))\cup V(G(cd^k,d))$. In this thesis, we proved that $G(cd^k,d)-F$ with $|F|\leq deg(G(cd^k,d))-2$ is weakly pancyclic where $c$ is odd, and $c\geq 3$. Moreover, this bound is tight.
23
Lin, Xuan-Yun, and 林軒筠. "Integer {k}-Domination Number of Circulant Graphs." Thesis, 2018. http://ndltd.ncl.edu.tw/handle/6ntxrs.
Full textAbstract:
碩士國立交通大學
應用數學系所
106
Let G(V,E) be a simple graph, i.e., G is undirected, no multiple edges and loopless. Let k be a positive integer. A function f: V(G)→Ν∪{0} is an integer {k}-dominating function if ∀v∈V(G), f(v)+∑_(uv∈E(G))▒〖f(u)≥〗 k. In addition, for all integer {k}-dominating functions f of G, 〖min┬f ∑_(x∈V(G))▒〖f(x)〗〗 is the integer {k}-domination number of G (denoted byγ_({k})(G)). The problem of integer {k}-dominating number is necessary since the starting value k=1 is exactly the problem of domination number. Therefore, it is important to consider a version which generalizes the classical domination problem. In this study, we focus on finding the exact value ofγ_({k})(G) of the circulant graphs whose the difference sets are {1,2,...,t} (t ∈Ν) and {1,n/2}. As a consequence, when the difference sets are {1, n/2} and {1,2,…,t}, t≤5, we are able to determineγ_({k})(G).
24
Hattingh, Johannes Hendrik. "Some aspects of the theory of circulant graphs." Thesis, 2014. http://hdl.handle.net/10210/9738.
Full text
25
Lin, Feng-Yuan, and 林逢源. "Edge-Disjoint Hamiltonian Cycles of Generalized Recursive Circulant Graphs." Thesis, 2013. http://ndltd.ncl.edu.tw/handle/98320180736966735554.
Full textAbstract:
碩士明新科技大學
資訊管理研究所
101
A hamiltonian cycle is a cycle which traverses every vertex exactly once in a graph. A graph is called k-regular if deg(v) = k for every vertex v in this graph. A k-regular graph G is hamiltonian decomposable if its edge set can be partitioned into k/2 edge-disjoint hamiltonian cycles when k is even or (k−1)/2 edge-disjoint hamiltonian cycles and a perfect matching when k is odd. Biss and Tsai et al. proved that every recursive circulant graph is hamiltonian decomposable. The generalized recursive circulant graph is a generalization of the recursive circulant graph. In this thesis, we discuss hamiltonian decomposition of generalized recursive circulant graphs.
26
Tsai, Chang-Hsiung, and 蔡正雄. "Fault-tolerant hamiltonian properties on butterflies, recursive circulant graphs, and hypercubes." Thesis, 2002. http://ndltd.ncl.edu.tw/handle/12055600187371514451.
Full textAbstract:
博士國立交通大學
資訊科學系
90
The performance of a distributed system is significantly determined by its network topology. Designing the topology of interconnection network involves mutually conflicting requirements. One of the major requirements in designing the topology of networks is the hamiltonicity. On the other hand, fault tolerance is highly desirable for massive parallel systems which have relative high probability of failure. For a positive integer k, a graph G = (V,E) is k-hamiltonian if G-F is hamiltonian for any F Í VÈE with |F| £ k. A k-hamiltonian graph G is optimal if it contains the least number of edges among all k-hamiltonian graphs with the same number of vertices as G. The study of optimal k-hamiltonian graphs is motivated from the design of optimal fault-tolerant token rings in computer networks. This research studied fault-tolerant hamiltonicities of three famous family interconnection networks, namely wrapped butterfly graphs, recursive circulant graphs, and hypercubes. In this thesis, F denotes the fault set of the graph and fv denotes the number of faulty node in F. When the hamiltonicity of a graph G is concerned, it is usual to investigate whether G is hamiltonian or hamiltonian-connected. Since a bipartite graph is not hamiltonian-connected, Simmons[35] introduced the concept of hamiltonian laceability for class of bipartite graphs. It is known that every hypercube Qn is a bipartite graph. Assume that n ³ 2 and F is a subset of edges with |F| £ n-2. We prove that there exists a hamiltonian path in Qn -F between any two vertices of different partite sets. Moreover, there exists a path of length 2n-2 between any two vertices of the same partite set. Assume that n ³ 3 and |F| £ n-3. We prove that there exists a hamiltonian path in Qn-{v}-F between any two vertices in the partite set without node v. In addition, it is shown that Qn contains every even cycle even if it has n-2 edge faults. Let BFn denote the n-dimensional wrapped butterfly graph with n2n vertices. When |F| £ 2, we prove that BFn-F contains a cycle of length n2n-2fv. Moreover, BFn-F contains a cycle of length n2n-fv if n is an odd integer. In other words, BFn is optimal 2-hamiltonian regular graph if n is an odd integer. A recursive circulant graph G(cdk,d) is a circulant graph with cdk vertices and jumps of powers of d where d ³ 2 and 2£c£d. We also prove that G(cdk,d)-F remains hamiltonian when it is not a bipartite graph and |F| £ deg(G(cdk,d))-2, where deg(G(cdk,d)) denotes a degree of G(cdk,d). Moreover, we prove that for any two vertices u and v in V(G(cdk,d))-F, there exists a hamiltonian path of G(cdk,d)-F joining u and v, when it is not a bipartite graph and |F| £ deg(G(cdk,d))-3. Furthermore, all bounds are tight.
27
Feria, Puron Ramiro. "Large interconnection networks with given degree and diameter." Thesis, 2015. http://hdl.handle.net/1959.13/1295870.
Full textAbstract:
Research Doctorate - Doctor of Philosophy (PhD)This thesis investigates and provides several answers for one of the most representative open problems in the design of interconnection networks. In the last few decades, the ability to design interconnection networks satisfying practical requirements and constraints has become a topic of major interest. In most circumstances, however, this has turned out to be a rather challenging task, leading to questions that have become the source of more than one interesting unsolved problem. One of these problems that has received significant attention deals with the design of networks as large as possible in terms of the number of nodes, given a limit on the number of connections attached to a node and a limit on the distance between any two nodes of the network. When translated to graph-theoretical terms this leads to the Degree/Diameter Problem, which asks for the largest number of vertices in a graph (and the graph itself) with a given maximum degree and diameter. The Degree/Diameter problem has been investigated since it was stated in 1964, yet is has endured as an open problem for more than fifty years now. A generous number of partial outcomes have been obtained to date, without narrowing the considerable gap remaining between the currently known upper and lower bounds for most degrees and diameters. The networks in question may be subject to further classification, such as being planar or bipartite, which restricts the Degree/Diameter Problem to the class of graphs under consideration. In this thesis we make substantial contributions to the Degree/Diameter Problem by providing improvements in the two traditional research directions: lowering the upper bounds for by proving the non-existence of graphs, and increasing the lower bounds by finding or giving constructions of ever larger graphs with given degree and diameter. The methodology used relies on a mixture of combinatorial approaches, graph compounding techniques, as well as algorithmic techniques and computer search. Our outcomes cover four of the most prominent classes of graphs studied: general graphs, bipartite graphs, circulant graphs, and graphs embeddable on surfaces. Among others, we obtain the following results: For the class of bipartite graphs, we use combinatorial approaches to improve the current upper bounds for more than two thirds of all possible combinations of degree and diameter. In a partially computer assisted proof, we prove that the largest known bipartite graph of degree 7 and diameter 3 is optimal. We also find by computer search a bipartite graph of degree 11 and diameter 3, thus improving the former lower bound by 4 vertices. ; For the class of general graphs, we use a similar strategy to improve the current upper bounds for more than one half of all possible combinations of degree and diameter. ; For the class of circulant graphs, we design and implement an efficient algorithm to find circulant graphs of small diameter. We find 15 largest known circulant graphs, with diameters ranging from 3 to 5 and degrees between 8 and 15. Using a combination of this algorithm and the cartesian product of graphs, we develop a search procedure to find 41 circulant graphs, with diameters ranging from 4 to 10 and degrees between 10 and 16, for which no previous graph had been found in the past. ; For the class of graphs embeddable in an arbitrary fixed surface, we use graph compounding to obtain graphs with orders improving the former lower bounds by a factor of 4. In addition, we construct a number of largest known planar and toroidal graphs. Finally, we present some final considerations about our work, and state a few conjectures providing support for future research in the design of interconnection networks and the Degree/Diameter Problem.
28
Chen, Guan Hua, and 陳冠華. "Embedding in recursive circulant graph." Thesis, 1996. http://ndltd.ncl.edu.tw/handle/01609429754578444844.
Full textAbstract:
碩士國立臺灣大學
資訊工程學研究所
84
We embed d-ary complete tree, complete binary tree higher dimensional mesh, hypercube into recursive circulant graph and embed recursive circulant graph into hypercube. We use load, expansion, dilation and congestion to evaluate our embedding results. And we compare this results to the embedding results of hypercube at the least.
29
Belkale, Naveen. "Hadwiger's Conjecture On Circular Arc Graphs." Thesis, 2007. http://hdl.handle.net/2005/475.
Full textAbstract:
Conjectured in 1943, Hadwiger’s conjecture is one of the most challenging open problems in graph theory. Hadwiger’s conjecture states that if the chromatic number of a graph G is k, then G has a clique minor of size at least k. In this thesis, we give motivation for attempting Hadwiger’s conjecture for circular arc graphs and also prove the conjecture for proper circular arc graphs. Circular arc graphs are graphs whose vertices can be represented as arcs on a circle such that any two vertices are adjacent if and only if their corresponding arcs intersect. Proper circular arc graphs are a subclass of circular arc graphs that have a circular arc representation where no arc is completely contained in any other arc. It is interesting to study Hadwiger’s conjecture for circular arc graphs as their clique minor cannot exceed beyond a constant factor of its chromatic number as We show in this thesis. Our main contribution is the proof of Hadwiger’s conjecture for proper circular arc graphs. Also, in this thesis we give an analysis and some basic results on Hadwiger’s conjecture for circular arc graphs in general.
30
Yu, Shan-Chan, and 余善謙. "Embedding Mesh into Recursive Circulant Graph." Thesis, 2004. http://ndltd.ncl.edu.tw/handle/81174069497659401308.
Full textAbstract:
碩士南台科技大學
資訊管理系
92
In these years, many efficient parallel algorithms have been designed for interconnection networks to solve all kind of problems. Among them, the embedding problems have received much attention. Embedding can help us to easily apply an algorithm that is designed on some interconnection network to another interconnection network. In terms of graph theory, we can view a network as a graph. We say a guest graph H can be embedded into a host graph G if G contains a subgraph isomorphic to H. For two networks A and B, if A can be embedded into B, then we can emulate A with B. That is, any algorithm designed on A can be executed on B. Recursive circulant graphs was proposed by J. H. Park and K. Y. Chwa recently. They own many good topological properties, such as symmetry, recursiveness, hamiltonicity, and fault-tolerant ability. In order to easily apply the efficient algorithms developed for mesh onto recursive circulant graphs, we propose an algorithm to embed meshes into recursive circulant graphs in this paper.
31
Lin, Che-Yu, and 林哲宇. "The circular chromatic numbers of line graphs and total graphs." Thesis, 2014. http://ndltd.ncl.edu.tw/handle/emq79n.
Full textAbstract:
博士國立中山大學
應用數學系研究所
102
A circular r-colouring of a graph G is a mapping c : V (G) → [0, r) such that for any two adjacent vertices x and y, 1 ≤ |c(x) − c(y)| ≤ r−1. The circular chromatic number of G is χc(G) = inf{r : G has a circular r-colouring}. A circular r-edge-colouring of a graph G is a circular r-colouring of its line graph L(G). The circular chromatic index, written χ′c(G), is defined by χ′c(G) = χc(L(G)). It is known that for r ∈ (2, 3], there is a graph G with χ′c(G) = r if and only if r = 2 + 1/k for k ∈ N. In [23], Lukot’ka and Maz´ak proved that for any rational r ∈ (3, 10/3), there is a finite graph G with χ′c(G) = r. We prove that if k ≥ 3 is an odd integer, then for any rational r ∈ (k, k + 1/4), there is a finite graph G with χ′c(G) = r (Corollary 3.1.3); if k ≥ 4 is an even integer, then for any rational r ∈ (k, k + 1/6), there is a finite graph G with χ′ c(G) = r (Corollary 3.1.4). A circular r-total-colouring of a graph G is a circular r-colouring of its total graph T(G). The circular total chromatic number, written χ′′c(G), is defined by χ′′c (G) = χc(T(G)). In [10], it was proved that for r ∈ (3, 4], there is a graph G with χ′′c (G) = r if and only if r = 3 + 1/k for k ∈ N. We prove that for any integer n ≥ 5 and any rational r ∈ (n, n + 1/3), there is a finite graph G with χ′′c (G) = r (Theorem 3.2.2).
32
Hsieh, Chin-chih, and 謝金池. "Circular chromatic number of Kneser Graphs." Thesis, 2004. http://ndltd.ncl.edu.tw/handle/38071375706867304525.
Full textAbstract:
碩士國立中山大學
應用數學系研究所
92
This thesis studies the circular chromatic number of Kneser graphs. It was known that if m is greater than 2n^{2}(n-1), then the Kneser graph KG(m,n) has its circular chromatic number equal its chromatic number . In particular, if n = 3, then KG(m,3) has its circular chromatic number equal its chromatic number when m is greater than 36. In this thesis, we improve this result by proving that if m is greaer than 24, then chi_c(KG(m,3)) = chi(KG(m,3)).
33
ZHANG, XIU-JUAN, and 張秀娟. "Parallel algorithms for recognizing proper interval graphs and proper circular-arc graphs." Thesis, 1991. http://ndltd.ncl.edu.tw/handle/73961357349982571331.
Full text
34
KUN-FENG, WU, and 吳坤峰. "Circular L(d,1)-labellings on Graphs." Thesis, 1999. http://ndltd.ncl.edu.tw/handle/13122230518247215290.
Full textAbstract:
碩士逢甲大學
應用數學系
88
It is well-known that the vertex-labelling of graphs , where the labels are non-negative integers , provides a natural setting in which to study problems of radio channel assignment. Vertices correspond to transmitter locations and their labels to radio channels. In order to avoid interference in real radio system , each pair of vertices has , depending on their separation , a constraint on the difference between the labels that can be assigned. A distance two labelling of a graph G is a vertex-labelling that sets constraints both on adjacent vertices and on vertices of distance two apart. For any position d. Two types of measurements on distance two labellings are considered in this article. One (using the regular absolute difference) is called the L(d,1)-labelling of G ; the other (using the circular difference) is called the circular L(d,1)-labelling of (or c-L(d,1)-labelling in short) of G. In this article , we shall apply the L(d,1)-labelling to investigate the c-L(d,1)-labelling on some graphs (cycles , trees , the join of graphs and the complete multipartite graph) , and then make a comparison in between. Besides , a circular distance d labelling of a graph G is also a vertex-labelling such that the circular difference of the labels is at least d for adjacent vertices. In this article , we only to investigate the circular d-labelling (or c-d-labelling in short) of an odd n-cycle Cn.
35
HUI, HUANG CHIAO, and 黃巧慧. "Circular L(p,q)-labelling of graphs." Thesis, 2000. http://ndltd.ncl.edu.tw/handle/29005532046994798849.
Full textAbstract:
碩士國立東華大學
應用數學系
88
Given a graph G, a k-L(p,q)_{c} -labeling of G is a function f : V(G) → {0,1,2,…. ,k-1\}, such that |f(u)-f(v)|_{k}≧ p , if uv in E(G) and |f(u)-f(v)|_{k}≧ q if d_{G}(u,v)=2, where |x|_{k}:=min {|x|,k-|x|\} is the circular difference modulo k. The L(p,q)_{c}-labeling number of G, denoted by sigma_{p,q}(G), is the smallest number k such that G has a k-L(p,q)_{c}-labeling. In this thesis, we study the L(p,q)_{c}-labeling problem for cycles, Cartesian product of paths, and join of k graphs G_{1},G_{2},……,G_{k}.
36
Roussel, Nicolas, and 盧賽爾. "Circular colorings and acyclic choosability of graphs." Thesis, 2009. http://ndltd.ncl.edu.tw/handle/18684723073324507189.
Full textAbstract:
博士國立中山大學
應用數學系研究所
98
Abstract: This thesis studies five kinds of graph colorings: the circular coloring, the total coloring, the (d; 1)-total labeling, the circular (r; 1)-total labeling, and the acyclic list coloring. We give upper bounds on the circular chromatic number of graphs with small maximum average degree, mad for short. It is proved that if mad(G)<22=9 then G has a 11=4-circular coloring, if mad(G) < 5=2 then G has a 14=5-circular coloring. A conjecture by Behzad and Vizing implies that Δ+2 colors are always sufficient for a total coloring of graphs with maximum degree Δ. The only open case for planar graphs is for Δ = 6. Let G be a planar in which no vertex is contained in cycles of all lengths between 3 and 8. If Δ(G) = 6, then G is total 8-colorable. If Δ(G) = 8, then G is total 9-colorable. Havet and Yu [23] conjectured that every subcubic graph G ̸=K4 has (2; 1)-total number at most 5. We confirm the conjecture for graphs with maximum average degree less than 7=3 and for flower snarks. We introduce the circular (r; 1)-total labeling. As a relaxation of the aforementioned conjecture, we conjecture that every subcubic graph has circular (2; 1)-total number at most 7. We confirm the conjecture for graphs with maximum average degree less than 5=2. We prove that every planar graph with no cycles of lengths 4, 7 and 8 is acyclically 4-choosable. Combined with recent results, this implies that every planar graph with no cycles of length 4;k; l with 5 6 k < l 6 8 is acyclically 4-choosable.
37
Babu, Jasine. "Algorithmic and Combinatorial Questions on Some Geometric Problems on Graphs." Thesis, 2014. http://etd.iisc.ernet.in/2005/3485.
Full textAbstract:
This thesis mainly focuses on algorithmic and combinatorial questions related to some geometric problems on graphs. In the last part of this thesis, a graph coloring problem is also discussed.
Boxicity and Cubicity: These are graph parameters dealing with geomet-ric representations of graphs in higher dimensions. Both these parameters are known to be NP-Hard to compute in general and are even hard to approximate within an O(n1− ) factor for any > 0, under standard complexity theoretic assumptions.
We studied algorithmic questions for these problems, for certain graph classes, to yield efficient algorithms or approximations. Our results include a polynomial time constant factor approximation algorithm for computing the cubicity of trees and a polynomial time constant (≤ 2.5) factor approximation algorithm for computing the boxicity of circular arc graphs. As far as we know, there were no constant factor approximation algorithms known previously, for computing boxicity or cubicity of any well known graph class for which the respective parameter value is unbounded.
We also obtained parameterized approximation algorithms for boxicity with various edit distance parameters. An o(n) factor approximation algorithm for computing the boxicity and cubicity of general graphs also evolved as an interesting corollary of one of these parameterized algorithms. This seems to be the first sub-linear factor approximation algorithm known for computing the boxicity and cubicity of general graphs.
Planar grid-drawings of outerplanar graphs: A graph is outerplanar, if it has a planar embedding with all its vertices lying on the outer face. We give an efficient algorithm to 2-vertex-connect any connected outerplanar graph G by adding more edges to it, in order to obtain a supergraph of G such that the resultant graph is still outerplanar and its pathwidth is within a constant times the pathwidth of G. This algorithm leads to a constant factor approximation algorithm for computing minimum height planar straight line grid-drawings of outerplanar graphs, extending the existing algorithm known for 2-vertex connected outerplanar graphs.
n−1
3
Maximum matchings in triangle distance Delaunay graphs: Delau-nay graphs of point sets are well studied in Computational Geometry. Instead of the Euclidean metric, if the Delaunay graph is defined with respect to the convex distance function defined by an equilateral triangle, it is called a Trian-gle Distance Delaunay graph. TD-Delaunay graphs are known to be equivalent to geometric spanners called half-Θ6 graphs.
It is known that classical Delaunay graphs of point sets always contain a near perfect matching, for non-degenerate point sets. We show that Triangle Distance Delaunay graphs of a set of n points in general position will always l m contain a matching of size and this bound is tight. We also show that Θ6 graphs, a class of supergraphs of half-Θ6 graphs, can have at most 5n − 11 edges, for point sets in general position.
Heterochromatic Paths in Edge Colored Graphs: Conditions on the coloring to guarantee the existence of long heterochromatic paths in edge col-ored graphs is a well explored problem in literature. The objective here is to obtain a good lower bound for λ(G) - the length of a maximum heterochro-matic path in an edge-colored graph G, in terms of ϑ(G) - the minimum color degree of G under the given coloring. There are graph families for which λ(G) = ϑ(G) − 1 under certain colorings, and it is conjectured that ϑ(G) − 1 is a tight lower bound for λ(G).
We show that if G has girth is at least 4 log2(ϑ(G))+2, then λ(G) ≥ ϑ(G)− 2. It is also proved that a weaker requirement that G just does not contain four-cycles is enough to guarantee that λ(G) is at least ϑ(G) −o(ϑ(G)). Other special cases considered include lower bounds for λ(G) in edge colored bipartite graphs, triangle-free graphs and graphs without heterochromatic triangles.
38
Pan, Zhi-Shi, and 潘志實. "Construction of Graphs with Given Circular Chrotmatic Number or Circular Flow number." Thesis, 2003. http://ndltd.ncl.edu.tw/handle/01222847836257426912.
Full textAbstract:
博士國立中山大學
應用數學系研究所
91
This thesis constructs special graphs with given circular chromatic numbers or circular flow numbers. Suppose $G=(V,E)$ is a graph and $rgeq 2$ is a real number. An $r$-coloring of a graph $G$ is a mapping $f:V ightarrow [0,r)$ such that for any adjacent vertices $x,y$ of $G$, $1leq |f(x)-f(y)|leq r-1$. The circular chromatic number $chi_c(G)$ is the least $r$ for which there exists an $r$-coloring of $G$. The circular chromatic number was introduced by Vince in 1988 in cite{vince}, where the parameter is called the {em star chromatic number} and denoted by $chi^*(G)$. Vince proved that for any rational number $k/dgeq 2$ there is a graph $G$ with $chi_c(G)=k/d$. In this thesis, we are interested in the existence of special graphs with given circular chromatic numbers. A graph $H$ is called a minor of a graph $G$ if $H$ can be obtained from $G$ by deleting some vertices and edges, and contracting some edges. A graph $G$ is called $H$-minor free if $H$ is not a minor of G. The well-known Hadwiger''s conjecture asserts that for any positive integer $n$, any $K_n$-minor free graph $G$ is $(n-1)$-colorable. If this conjecture is true, then for any $K_n$-minor free graph $G$, we have $chi_c(G)leq n-1$. On the other hand, for any graph $G$ with at least one edge we have $chi_c(G)geq 2$. A natural question is this: Is it true that for any rational number $2leq rleq n-1$, there exist a $K_n$-minor free graph $G$ with $chi_c(G)=r$? For $n=4$, the answer is ``no". It was proved by Hell and Zhu in cite{hz98} that if $G$ is a $K_4$-minor free graph then either $chi_c(G)=3$ or $chi_c(G)leq 8/3$. So none of the rational numbers in the interval $(8/3,3)$ is the circular chromatic number of a $K_4$-minor free graph. For $ngeq 5$, Zhu cite{survey} proved that for any rational number $rin[2,n-2]$, there exists a $K_n$-minor free graph $G$ with $chi_c(G)=r$. The question whether there exists a $K_n$-minor free graph $G$ with $chi_c(G)=r$ for each rational number $rin(n-2,n-1)$ remained open. In this thesis, we answer this question in the affirmative. For each integer $ngeq 5$, for each rational number $rin[n-2,n-1]$, we construct a $K_n$-minor free graph $G$ with $chi_c(G)=r$. This implies that for each $ngeq 5$, for each rational number $rin[2,n-1]$, there exists a $K_n$-minor free graph $G$ with $chi_c(G)=r$. In case $n=5$, the $K_5$-minor free graphs constructed in this thesis are actually planar graphs. So our result implies that for each rational number $rin[2,4]$, there exists a planar graph $G$ with $chi_c(G)=r$. This result was first proved by Moser cite{moser} and Zhu cite{3-4}. To be precise, Moser cite{moser} proved that for each rational number $rin[2,3]$, there exist a planar graph $G$ with $chi_c(G)=r$, and Zhu cite{3-4} proved that for each rational number $rin[3,4]$, there exists a planar graph $G$ with $chi_c(G)=r$. Moser''s and Zhu''s proofs are quite complicated. Our construction is conceptually simpler. Moreover, for $ngeq 5$, $K_n$-minor free graphs, including the planar graphs are constructed with a unified method. For $K_4$-minor free graphs, although Hell and Zhu cite{hz98} proved that there is no $K_4$-minor free graph $G$ with $chi_c(G)in (8/3,3)$. The question whether there exists a $K_4$-minor free graph $G$ with $chi_c(G)=r$ for each rational number $rin[2,8/3]$ remained open. This thesis solves this problem: For each rational number $rin[2,8/3]$, we shall construct a $K_4$-minor free $G$ with $chi_c(G)=r$. This thesis also studies the relation between the circular chromatic number and the girth of $K_4$-minor free graphs. For each integer $n$, the supremum of the circular chromatic number of $K_4$-minor free graphs of odd girth (the length of shortest odd cycle) at least $n$ is determined. It is also proved that the same bound is sharp for $K_4$-minor free graphs of girth $n$. By a classical result of ErdH{o}s, for any positive integers $l$ and $n$, there exists a graph $G$ of girth at least $l$ and of chromatic number $n$. Using probabilistic method, Zhu cite{unique} proved that for each integer $l$ and each rational number $rgeq 2$, there is a graph $G$ of girth at least $l$ such that $chi_c(G)=r$. Construction of such graphs for $rgeq 3$ was given by Nev{s}etv{r}il and Zhu cite{nz}. The question of how to construct large girth graph $G$ with $chi_c(G)=r$ for given $rin(2,3)$ remained open. In this thesis, we present a unified method that constructs, for any $rgeq 2$, a graph $G$ of girth at least $l$ with circular chromatic number $chi_c(G) =r$. Graphs $G$ with $chi_c(G)=chi(G)$ have been studied extensively in the literature. Many families of graphs $G$ are known to satisfy $chi_c(G)=chi(G)$. However it remained as an open question as how to construct arbitrarily large $chi$-critical graphs $G$ of bounded maximum degree with $chi_c(G)=chi(G)$. This thesis presents a construction of such graphs. The circular flow number $Phi_c(G)$ is the dual concept of $chi_c(G)$. Let $G$ be a graph. Replace each edge $e=xy$ by a pair of opposite arcs $a=overrightarrow{xy}$ and $a^{-1}=overrightarrow{yx}$. We obtain a symmetric directed graph. Denote by $A(G)$ the set of all arcs of $G$. A chain is a mapping $f:A(G) ightarrow I!!R$ such that for each arc $a$, $f(a^{-1})=-f(a)$. A flow is a chain such that for each subset $X$ of $V(G)$, $sum_{ain[X, ar{X}]}f(a)=0$, where $[X, ar{X}]$ is the set of all arcs from $X$ to $V-X$. An $r$-flow is a flow such that for any arc $ain A(G)$ , $1leq |f(a)| leq r-1$. The circular flow number of $G$ is $Phi_c(G)=mbox{ inf}{r: G mbox{ admits a } rmbox{-flow}}$. It was conjectured by Tutte that every graph $G$ has $Phi_c(G)leq 5$. By taking the geometrical dual of planar graphs, Moser''s and Zhu''s results concerning circular chromatic numbers of planar graphs imply that for each rational number $rin[2,4]$, there is a graph $G$ with $Phi_c(G)=r$. The question remained open whether for each $rin(4,5)$, there exists a graph $G$ with $Phi_c(G)=r$. In this thesis, for each rational number $rin [4,5]$, we construct a graph $G$ with $Phi_c(G)=r$.
39
Hung, Ruo-Wei, and 洪若偉. "The Path Cover and Related Problems on Circular-Arc Graphs and Distance-Hereditary Graphs." Thesis, 2005. http://ndltd.ncl.edu.tw/handle/62409733602692036678.
Full textAbstract:
博士國立中正大學
資訊工程所
93
A Hamiltonian path of a graph G is a simple path that visits each vertex of G exactly once. A Hamiltonian cycle of a graph is a simple cycle with the same property. The Hamiltonian path and Hamiltonian cycle problems involve testing whether a Hamiltonian path and a Hamiltonian cycle exist in a graph, respectively. The Hamiltonian problems include the Hamiltonian path and Hamiltonian cycle problems. A path cover of a graph G is a set of pairwise vertex-disjoint paths of G that covers all vertices in G. The path cover problem is to find a path cover of the minimum number of paths of a graph. The path cover problem contains the Hamiltonian path problem as a special case since finding a path cover, consisting of a single path, corresponds directly to the Hamiltonian path problem. The Hamiltonian problems are called the path cover related problems. It is well known that the path cover and related problems for general graphs are classic NP-complete problems. Hence researchers studying the path cover and related problems always focus on special classes of graphs. Perfect graphs have received much attentions. The path cover and related problems on some special classes of perfect graphs have been shown to be NP-complete. However, they admit polynomial-time algorithms when the input is restricted to be in some other special classes of perfect graphs. On the other hand, some researchers also considered some special classes of graphs not in perfect graphs for the path cover and related problems. In the dissertation, we will focus on solving the path cover and related problems on distance-hereditary graphs and circular-arc graphs. Distance-hereditary graphs form a subclass of perfect graphs, but circular-arc graphs are not contained in the class of perfect graphs. A graph is a distance-hereditary graph if each pair of vertices is equidistant in every connected induced subgraph containing them. A graph G is a circular-arc graph if there exist a set F of arcs on a circle and a one-to-one mapping of the vertices of G and the arcs in F such that two vertices in G are adjacent if and only if their corresponding arcs in F intersect. The Hamiltonian cycle problem on circular-arc graphs has been shown to be polynomially solvable. The Hamiltonian problems on distance-hereditary graphs have been shown to be solvable in polynomial time, but the complexity of the path cover problem on these graphs is still unknown. In this dissertation, we first present a simple O(n)-time approximation algorithm for the path cover problem on circular-arc graphs given a set of n arcs with endpoints sorted and show that the cardinality of the path cover found by the approximation algorithm is at most one more than the optimal one. Using the result, we reduce the path cover problem on circular-arc graphs to the Hamiltonian problems on the same class of graphs in O(n) time. Hence the complexity of the path cover problem on circular-arc graphs is the same as those of the Hamiltonian problems on circular-arc graphs. Next we present a unified approach to solving the Hamiltonian problems on distance-hereditary graphs in linear time. This improves the best known results. Finally, we propose the first polynomial-time algorithm to solve the path cover problem on distance-hereditary graphs.
40
Hung, Ruo-Wei, and 洪若偉. "Algorithms on Circular-arc Graphs and Multiple Stacks." Thesis, 1992. http://ndltd.ncl.edu.tw/handle/55297478991501787651.
Full textAbstract:
碩士國立中正大學
資訊工程研究所
80
In this thesis, we shall present two efficient algorithms on circular-arc graphs and multiple stacks manipulation, respectively. It is divided into two parts as follows: PART I: An O(n) Time Algorithm for the Minimum Connected Dominating Set Problem on Circular-Arc Graphs. In this part, we shall present an algorithm to solve the minimum-cardinality connected domination problem on circular-arc graphs. Given the ar model with endpoints sorted, the algorithm takes only O(n) time and O(n) space where n is the number of arcs (vertices). PART II: An Efficient Algorithm Using Linked Blocks for Multiple Stacks Manipulation. A new and efficient algorithm for multiple stacks manipulation is proposed in this part. Initially, our algorithm assigns the storage to blocks of almost equal size and starts out with all empty stacks and a linked free-blocked list which is a linked list constructed by the blocks. After performing the initialization step, the basic operations of each stack such as PUSH and POP can be done efficiently. According to our simulation results, it is not hard to see that our algorithm is more efficient than the best previous algorithms [Yang et al. 1991; Chang et al. 1991].
41
Chen, kuo_Long, and 陳國隆. "A Study of the Maximum Clique Problem in Dynamic Interval Graphs and Circular-arc Graphs." Thesis, 1995. http://ndltd.ncl.edu.tw/handle/80617720216933574537.
Full text
42
YU, MING-XING, and 余明興. "Parallel algorithms for some problems on circular-arc graphs." Thesis, 1989. http://ndltd.ncl.edu.tw/handle/39975392271901392784.
Full text
43
Lin, Shu-yuan, and 林淑媛. "Simultaneously Uniquely Circular Colourable and Uniquely Fractional Colourable Graphs." Thesis, 2006. http://ndltd.ncl.edu.tw/handle/99346751270596706705.
Full textAbstract:
博士國立中山大學
應用數學系研究所
94
This thesie discusses uniquely circular colourable and uniquely fractional colourable graphs. Suppose G = (V;E) is a graph and r ¸ 2 is a real number. A circular r-colouring of G is a mapping f : V (G) ! [0; r) such that for any edge xy of G, 1 · jf(x) ¡ f(y)j · r ¡ 1. We say G is uniquely circular r-colourable if there is a circular r-colouring f of G and any other circular r-colouring of G can obtained from f by a rotation or a °ip of the colours. Let I(G) denote the family of independent sets of G. A fractional r-colouring of G is a mapping f : I(G) ! [0; 1] such that for any vertex x, Px2I f(I) = 1 and PI2I(G) f(I) · r. A graph G is called uniquely fractional r-colourable if there is exactly one fractional r-colouring of G. Uniquely circular r-colourable graphs have been studied extensively in the literature. In particular, it is known that for any r ¸ 2, for any integer g, there is a uniquely circular r- colourable graph of girth at least g. Uniquely fractional r-colouring of graphs is a new concept. In this thesis, we prove that for any r ¸ 2 for any integer g, there is a uniquely fractional r-colourable graph of girth at least g. It is well-known that for any graph G, Âf (G) · Âc(G). We prove that for any rational numbers r ¸ r0 > 2 and any integer g, there is a graph G of girth at least g, which is uniquely circular r-colourable and at the same time uniquely fractional r0-colourable.
44
Hsu, Kevin. "Obstructions for local tournament orientation completions." Thesis, 2020. http://hdl.handle.net/1828/12024.
Full textAbstract:
The orientation completion problem for a hereditary class C of oriented graphs asks whether a given partially oriented graph can be completed to a graph belonging to C. This problem was introduced recently and is a generalization of several existing problems, including the recognition problem for certain classes of graphs and the representation extension problem for proper interval graphs. A local tournament is an oriented graph in which the in-neighbourhood as well as the out-neighbourhood of each vertex induces a tournament. Local tournaments are a well-studied class of oriented graphs that generalize tournaments and their underlying graphs are intimately related to proper circular-arc graphs. Proper interval graphs are precisely those which can be oriented as acyclic local tournaments. The orientation completion problems for the class of local tournaments and the class of acyclic local tournaments have been shown to be polynomial-time solvable. In this thesis, we characterize the partially oriented graphs that can be completed to local tournaments by finding a complete list of obstructions. These are in a sense the minimal partially oriented graphs that cannot be completed to local tournaments. We also determine the minimal partially oriented graphs that cannot be completed to acyclic local tournaments.Graduate
45
Yang, Chung-Ying, and 楊宗穎. "Colouring, circular list colouring and adapted game colouring of graphs." Thesis, 2010. http://ndltd.ncl.edu.tw/handle/264n52.
Full textAbstract:
博士國立中山大學
應用數學系研究所
98
This thesis discusses colouring, circular list colouring and adapted game colouring of graphs. For colouring, this thesis obtains a sufficient condition for a planar graph to be 3-colourable. Suppose G is a planar graph. Let H_G be the graph with vertex set V (H_G) = {C : C is a cycle of G with |C| ∈ {4, 6, 7}} and edge set E(H_G) = {CiCj : Ci and Cj have edges in common}. We prove that if any 3-cycles and 5-cycles are not adjacent to i-cycles for 3 ≤ i ≤ 7, and H_G is a forest, then G is 3-colourable. For circular consecutive choosability, this thesis obtains a basic relation among chcc(G), X(G) and Xc(G) for any finite graph G. We show that for any finite graph G, X(G) − 1 ≤ chcc(G) < 2 Xc(G). We also determine the value of chcc(G) for complete graphs, trees, cycles, balanced complete bipartite graphs and some complete multi-partite graphs. Upper and lower bounds for chcc(G) are given for some other classes of graphs. For adapted game chromatic number, this thesis studies the adapted game chromatic number of various classes of graphs. We prove that the maximum adapted game chromatic number of trees is 3; the maximum adapted game chromatic number of outerplanar graphs is 5; the maximum adapted game chromatic number of partial k-trees is between k + 2 and 2k + 1; and the maximum adapted game chromatic number of planar graphs is between 6 and 11. We also give upper bounds for the Cartesian product of special classes of graphs, such as the Cartesian product of partial k-trees and outerplanar graphs, or planar graphs.
46
Lai, Yi-Chung, and 賴意中. "Fault Tolerance Measures in Recursive Circulant Graph on Forbidden Faulty Sets." Thesis, 2006. http://ndltd.ncl.edu.tw/handle/82876669243424318338.
Full textAbstract:
碩士南台科技大學
資訊管理系
94
Fault tolerance analysis is very important on interconnection network. In tradition, we use the connectivity of node and edge to measure the fault tolerance capability of interconnection networks. In this paper, we introduce the concept of the forbidden faulty sets that was proposed by Esfahanian. Under the restriction of forbidden faulty sets, we analyze the fault tolerance capability of the recursive circulant graphs. The recursive circulant graph has many good topology properties such as Hamiltonian cycle, node symmetric and can be recursively constructed. Finally, we will prove the connectivity of the recursive circulant with the restriction of forbidden faulty sets. The connectivity can achieve 4m – 4 if c = 1 and d = 2; 4m – 2 if c = 1 and d ≠ 2; 4m if c = 2; 4m + 2 if c > 2.
47
Kuo, Wenling, and 郭玟伶. "An Upper Bound for the Circular Chromatic Number of Mycielski Graphs." Thesis, 2006. http://ndltd.ncl.edu.tw/handle/10891479438170228481.
Full textAbstract:
碩士大葉大學
資訊工程學系碩士在職專班
94
In a search for triangle-free graphs with arbitrarily large chromatic numbers, Mycielski ([15]) developed a graph transformation that transforms a graph G into a new graph (G), we now call the Mycielskian of G. For t
48
chien, chih-yun, and 簡志雲. "The circular chromatic number of series-parallel graphs with large girth." Thesis, 1999. http://ndltd.ncl.edu.tw/handle/55042933756732907849.
Full textAbstract:
碩士國立中山大學
應用數學系
87
The circular chromatic number $\chi_c(G)$ of a graph $G$ is a natural generalization of the chromatic number of a graph. In this thesis, we consider the circular chromatic number $\chi_c(G)$ of series-parallel graphs $G$. The class of series-parallel graphs is a surprisingly rich class of graphs. There are many equivalent definitions for this class of graphs, and hence has many different names. One name is $K_4$-minor free graphs, i.e., this is the class of graphs which contains no $K_4$ as minors. A well known conjecture in graph theory, Hadwiger Conjecture, says that $K_n$-minor free graphs have chromatic number at most $n-1$. While this conjecture remains open, the complement in term of circular chromatic number of this question attracted some recent attention. The question is whether or not every rational number between $2$ and $n-1$ is the circular chromatic number of a $K_n$-minor free graph. A surprising negative answer to this question for $n=4$ was obtained by Hell and Zhu. They proved that any $K_4$-minor free graph of girth at least $2 \lfloor (3k-1)/2 \rfloor$ has circular chromatic number at most $4k/(2k-1)$. It follows that the circular chromatic number of a series-parallel graph is either $3$ (when it contains a triangle) or at most $8/3$ (when it is trangle free). The result of Hell and Zhu also provoked a research in another direction: what is the relation between the girth and the circular chromatic number of $K_n$-minor free graphs. While it is not difficult to prove that $K_n$-minor free graphs of ``large girth'' has circular chromatic number ``close to'' $2$, it seems to be very difficult to derive the precise quantitative relation between these two parameters. In this thesis, we shall derive a precise quantitative relation between the girth and circular chromatic number of $K_4$-minor free graphs. We shall prove the girth requirement in Hell and Zhu's result is sharp. To be precise, for any $k \geq 2$, we can construct a series-parallel graph $G$ of girth $2 \lfloor (3k-1)/2 \rfloor -1$ such that $\chi_c(G) > 4k/(2k-1)$.
49
"On-line Coloring of Partial Orders, Circular Arc Graphs, and Trees." Doctoral diss., 2012. http://hdl.handle.net/2286/R.I.15995.
Full textAbstract:
abstract: A central concept of combinatorics is partitioning structures with given constraints. Partitions of on-line posets and on-line graphs, which are dynamic versions of the more familiar static structures posets and graphs, are examined. In the on-line setting, vertices are continually added to a poset or graph while a chain partition or coloring (respectively) is maintained. %The optima of the static cases cannot be achieved in the on-line setting. Both upper and lower bounds for the optimum of the number of chains needed to partition a width $w$ on-line poset exist. Kierstead's upper bound of $\frac{5^w-1}{4}$ was improved to $w^{14 \lg w}$ by Bosek and Krawczyk. This is improved to $w^{3+6.5 \lg w}$ by employing the First-Fit algorithm on a family of restricted posets (expanding on the work of Bosek and Krawczyk) . Namely, the family of ladder-free posets where the $m$-ladder is the transitive closure of the union of two incomparable chains $x_1\le\dots\le x_m$, $y_1\le\dots\le y_m$ and the set of comparabilities $\{x_1\le y_1,\dots, x_m\le y_m\}$. No upper bound on the number of colors needed to color a general on-line graph exists. To lay this fact plain, the performance of on-line coloring of trees is shown to be particularly problematic. There are trees that require $n$ colors to color on-line for any positive integer $n$. Furthermore, there are trees that usually require many colors to color on-line even if they are presented without any particular strategy. For restricted families of graphs, upper and lower bounds for the optimum number of colors needed to maintain an on-line coloring exist. In particular, circular arc graphs can be colored on-line using less than 8 times the optimum number from the static case. This follows from the work of Pemmaraju, Raman, and Varadarajan in on-line coloring of interval graphs.Dissertation/Thesis
Ph.D. Mathematics 2012
50
Lai, Hsing-Hsueh, and 賴星學. "An Upper Bound of the Routing Number of Circular Complete Graphs." Thesis, 2016. http://ndltd.ncl.edu.tw/handle/35239183713088052739.
Full textAbstract:
碩士淡江大學
中等學校教師在職進修數學教學碩士學位班
104
The routing number rt(G) of a connected graph G is the minimum integer r so that every permutation of vertices can be routed in r steps by swapping the ends of disjoint edges. In this paper, we study and prove the routing number of circular complete graph K_(p/q) is rt(K_(p/q) )≤2q， "for all" p≥3q，p,q∈Z^+.