Dissertations / Theses on the topic 'Graceful graph'

A labeling of a graph is an assignment of a natural number to each vertex of a graph. Graceful labelings are very important types of labelings. The study of graceful labelings is very difficult and little has been shown about such labelings. Vertex-relaxed graceful labelings of graphs are a class of labelings that include graceful labelings, and their study gives an approach to the study of graceful labelings. In this thesis we generalize the congruence approach of Rosa to obtain new criteria for vertex-relaxed graceful labelings of graphs. To do this, we generalize Faulhaber’s Formula, which is a famous result about sums of powers of integers.

A decomposition D of a graph H by a graph G is a partition of the edge set of H such that the subgraph induced by the edges in each part of the partition is isomorphic to G. A mixed graph on V vertices is an ordered pair (V,C), where V is a set of vertices, |V| = v, and C is a set of ordered and unordered pairs, denoted (x, y) and [x, y] respectively, of elements of V [8]. An ordered pair (x, y) ∈ C is called an arc of (V,C) and an unordered pair [x, y] ∈ C is called an edge of graph (V,C). A path on n vertices is denoted as Pn. A partial orientation on G is obtained by replacing each edge [x, y] ∈ E(G) with either (x, y), (y, x), or [x, y] in such a way that there are twice as many arcs as edges. The complete mixed graph on v vertices, denoted Mv, is the mixed graph (V,C) where for every pair of distinct vertices v1, v2 ∈ V , we have {(v1, v2), (v2, v1), [v1, v2]} ⊂ C. The goal of this thesis is to establish necessary and sufficient conditions for decomposition of Mv by all possible partial orientations of P4.

For k∈{Z}+ and G a simple connected graph, a k-radio labeling f:VG→Z+ of G requires all pairs of distinct vertices u and v to satisfy |f(u)-f(v)|≥ k+1-d(u,v). When k=1, this requirement gives rise to the familiar labeling known as vertex coloring for which each vertex of a graph is labeled so that adjacent vertices have different "colors". We consider k-radio labelings of G when k=diam(G). In this setting, no two vertices can have the same label, so graphs that have radio labelings of consecutive integers are one extreme on the spectrum of possibilities; graphs that can be labeled with such a labeling are called radio graceful. In this thesis, we give four main results on the existence of radio graceful graphs, which focus on Hamming graphs (Cartesian products of complete graphs) and a generalization of the Petersen graph. In particular, we prove the existence of radio graceful graphs of arbitrary diameter, a result previously unknown. Two of these main results show that, under certain conditions, the tth Cartesian power Gt of a radio graceful graph G is also radio graceful. We will also speak to occasions when Gt is not radio graceful despite G being so, as well as some partial results about necessary and sufficient conditions for a graph G so that Gt is radio graceful.

Les systèmes distribués sont des systèmes composés de plusieurs processus communiquants et coopérants ensemble pour résoudre des tâches communes. C’est un modèle générique pour de nombreux systèmes réels comme les réseaux sans fil ou mobiles, les systèmes multiprocesseurs à mémoire partagée, etc. D’un point de vue algorithmique, il est reconnu que de fortes hypothèses (comme l’asynchronisme ou la mobilité) sur de tels systèmes mènent souvent à des résultats d’impossibilité ou à de fortes bornes inférieures sur les complexités. Dans cette thèse, nous étudions des algorithmes qui s’auto-adaptent à leur environnement (i.e., l’union de toutes les hypothèses sur le système) en se concentrant sur les deux approches suivantes. La dégradation progressive contourne les résultats d’impossibilité en dégradant les propriétés offertes par l’algorithme lorsque l’environnement devient fort. La spéculation contourne les bornes inférieures élevées sur les complexités en optimisant l’algorithme seulement sur les environnements les plus probables. Les réseaux de robots représentent un cas particulier des systèmes distribués où les processus, dotés de capteurs, sont capables de bouger d’une localisation à une autre. Nous considérons des environnements dynamiques dans lesquels cette capacité peut évoluer avec le temps. Cette thèse répond positivement à la question ouverte de savoir s’il est possible et bénéfique d’appliquer les approches progressivement dégradante et spéculative aux réseaux de robots dans des environnements dynamiques. Cette réponse est obtenue en étudiant le rassemblement (où tous les robots doivent se retrouver à la même localisation en temps fini) progressivement dégradant et l’exploration perpétuelle (où les robots doivent visiter infiniment souvent chaque localisation) spéculative
Distributed systems are systems composed of multiple communicant processes cooperating to solve a common task. This is a generic model for numerous real systems as wired or mobile networks, shared-memory multiprocessor systems, and so on. From an algorithmic point of view, it is well-known that strong assumptions (as asynchronism or mobility) on such systems lead often to impossibility results or high lower bounds on complexity. In this thesis, we study algorithms that adapt themselves to their environment (i.e., the union of all assumptions on the system) by focusing on the two following approaches. Graceful degradation circumvents impossibility results by degrading the properties offered by the algorithm as the environment become stronger. Speculation allows to bypass high lower bounds on complexity by optimizing the algorithm only on more probable environments. Robot networks are a particular case of distributed systems where processes are endowed with sensors and able to move from a location to another. We consider dynamic environments in which this ability may evolve with time. This thesis answers positively to the open question whether it is possible and attractive to apply gracefully degrading and speculative approaches to robot networks in dynamic environments. This answer is obtained through contributions on gracefully degrading gathering (where all robots have to meet on the same location in finite time) and on speculative perpetual exploration (where robots must visit infinitely often each location)

In this thesis, we consider the decomposition of the complete mixed graph on v vertices denoted Mv, into every possible mixed graph on three vertices which has (like Mv) twice as many arcs as edges. Direct constructions are given in most cases. Decompositions of theλ-fold complete mixed graph λMv, are also studied.

The graceful tree conjecture was first introduced over 50 years ago, and to this day it remains largely unresolved. Ideas for how to label arbitrary trees have been sparse, and so most work in this area focuses on demonstrating that particular classes of trees are graceful. In my research, I continue this effort and establish the gracefulness of some new tree types using previously developed techniques for constructing graceful trees. Meanwhile, little work has been done on developing computational methods for obtaining graceful labelings, as direct approaches are computationally infeasible for even moderately large trees. With this in mind, I have designed a new computational approach for constructing a graceful labeling for trees with sufficiently many leaves. This approach leverages information about the local structures present in a given tree in order to construct a suitable labeling. It has been shown to work for many small cases and thoughts on how to extend this approach for larger trees are put forth.
McAnulty College and Graduate School of Liberal Arts;
Computational Mathematics
MS;
Thesis;

碩士
淡江大學
中等學校教師在職進修數學教學碩士學位班
103
Let G be a simple graph with q edges. If there exists a function f from V(G) to {0, 1, 2, ..., q} and f is one-to-one. If from f we can get a function g, g : E(G)→{1, 2, ..., q} defined by g(e) =│ f (u) − f (v)│for every edge e = {u, v}∈E(G), and g is a bijective function, then we call f is a graceful labeling of G and the graph G is a graceful graph. Let Cn⊙Pm be the graph obtained by attaching a path Pm to each vertex of an n-cycle Cn. Let Cn⊙[(n－1)Pm∪Pu] be the graph obtained by attaching a path Pu to a vertex of an n-cycle Cn and attaching a path Pm to the other vertices. In this thesis, we obtain the following results. (1) Let m be a positive integer. If n≡0, 3(mod 4), then Cn⊙Pm is a graceful graph. (2) Let m be a positive integer. If n≡1, 2(mod 4), then Cn⊙P2m is a graceful graph. (3) Let m and u be a positive integers. If n≡0, 3(mod 4), then Cn⊙[(n－1)Pm∪Pu] is a graceful graph.

碩士
國立東華大學
應用數學系
95
Given a graph $G$ with $n$ vertices and a function $L:V(G) ightarrow2^{mathbb{N}}$, Let $G$ be a graph with $|V(G)|=n$ and $|E(G)|=m$, a extit{graceful labeling} of is a one-to-one function $f:V(G) ightarrow {0,1,2,...,m}$ such that ${|f(u)-f(v)|:uvin E(G)}={1,2,cdots ,m}$. A graph is graceful if it has a graceful labeling. Given integers $n,k$ with $kgeq 2$, we use $n_{k ext{ }}$to denote the number $n mod k$, and use $n_{/k,i}$ to denote the number $leftlfloor frac{n}{k} ight floor +delta _{i}$, where [ delta _{i}=left{ egin{array}{ll} 1. & ext{if }ileq ((m+1) mod k)-1, 0, & ext{if }igeq (m+1) mod k.% end{array}% ight. ] For a given graph $G$, an extit{orientation} of $G$ is a digraph $D$ obtained from $G$ by choosing an orientation $(x ightarrow y$ or $% y ightarrow x)$for each edge $xyin E(G)$. For a digraph $D$, a labeling $% f:V(D) ightarrow {0,1,2,cdots ,k-1}$ is called a $k$ extit{-graceful labeling} of $D$ if $max {(m+1)_{/k,i}+n-m-1,0}leq |f^{-1}(i)|leq (m+1)_{/k,i}$ for each $i,$ $0leq ileq k-1,$ and for all $j,$ $0leq jleq k-1,$ the sets $A_{j}={uv$ $:(f(v)-f(u))_{k}=j,$ $uvin E(D)}$ satisfy the condition that $leftlfloor frac{m}{k} ight floor leq leftvert A_{0} ightvert leq leftvert A_{k-1} ightvert leq leftvert A_{k-2} ightvert leq cdots leq leftvert A_{2} ightvert leq leftvert A_{1} ightvert leq leftlceil frac{m}{k} ight ceil .$ And we say that $G$ is extit{oriented-}$k$ extit{-graceful }if there exists an acyclic orientation $D$ of $G$ which has a $k$-graceful labeling $f$ defined on it. In this thesis, we fix some notation and terminologies and derive some basic properties in Section 2. And we show that every tree is oriented-2-graceful, oriented-3-graceful and oriented-4-graceful in Section 3. In Section 4, we give necessary and sufficient conditions for union of cycle to be oriented-2-graceful, oriented-3-graceful and oriented-4-graceful.

碩士
真理大學
數理科學研究所
89
Given a graph G, a graceful labeling f of G is an injection from f:V→{0,1,…,|E|} such that the function f':E→{1,2,3, …,|E|}, defined by f'(uv)=|f(u)-f(v)| for every edge uv in E,is a bijection. In this thesis, we study the graceful labeling for the union of two graphs G1 and G2, where G1 is a path, cycle or P_{a,b} and G2 is a path. We also study graceful labeling for the graph K_{n}\square S_{2^{n-1}- \binom{n}{2}-1}

碩士
淡江大學
中等學校教師在職進修數學教學碩士學位班
103
Let G be a simple graph with m edges. If there is a function f : V(G)→{0,1,2,…,m} and fis one-to-one. From the function f we can get a function g : E(G)→{1,2,…,m}, defined by g(e)=|f(u)-f(v)|, for e={u,v}∈E(G), and g is bijective, then we call f is a graceful labeling and G is a grace graph. In this thesis, we obtain the following results. (1)Let m and n be positive integers. If G is a graph with n vertices and n–1 edges and G is graceful, then GvKm is a graceful graph. (2)Let t be appositive integer. If m=3,4,or 5,then CmvKtis a graceful graph.

碩士
東海大學
應用數學系
104
The following condition (due to A. Rosa) is known to be necessary for an Eulerian graph G admitting a graceful valuation: jE(G)j 0 or 3 (mod 4). The condition is thus sucient if G is a cycle Cn on n vertices. In 1994 J. Abrham and A. Kotzig proved that the 2-regular graph kC4, the disjoint union of k copies of 4-cycles, admits graceful labeling for every positive integer k. In 1996 they also showed that the 2-regular graph Cp and Cq, the disjoint union of Cp and Cq, admits a graceful valuation if p + q 0 or 3 (mod 4). In this thesis we study the notion graceful deciency, which measures how far a graph is away from being graceful. We completely determine the graceful deciency for cycles Cn and windmill graphs, and conjecture that the graceful deciency of the 2-regular graph Cp and Cq is 1 with p + q 1 or 2 (mod 4).

碩士
國立交通大學
資訊科學與工程研究所
98
Let G be a simple graph with m edges and let f：V(G) → {0,1, ...,m} be an injection. The vertex labeling is called a graceful labeling if every edge (u,v) is assigned an edge label |f(x)–f(y)|and the resulting edge labels are mutually distinct. A graph possessing a graceful labeling is called a graceful graph. With an additional property that there exists an boundary value k so that for each edge (u,v) either f(u)≤k