Advanced search options

Advanced Search Options 🞨

Browse by author name (“Author name starts with…”).

Find ETDs with:

in
/  
in
/  
in
/  
in

Written in Published in Earliest date Latest date

Sorted by

Results per page:

Sorted by: relevance · author · university · dateNew search

Language: English

You searched for subject:(Packing Chromatic Number). Showing records 1 – 3 of 3 total matches.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters

1. Mortada, Maidoun. The b-chromatic number of regular graphs : Le nombre b-chromatique de graphe régulier.

Degree: Docteur es, Informatique, 2013, Université Claude Bernard – Lyon I

Les deux problèmes majeurs considérés dans cette thèse : le b-coloration problème et le graphe emballage problème. 1. Le b-coloration problème : Une coloration des sommets de G s'appelle une b-coloration si chaque classe de couleur contient au moins un sommet qui a un voisin dans toutes les autres classes de couleur. Le nombre b-chromatique b(G) de G est le plus grand entier k pour lequel G a une b-coloration avec k couleurs. EL Sahili et Kouider demandent s'il est vrai que chaque graphe d-régulier G avec le périmètre au moins 5 satisfait b(G) = d + 1. Blidia, Maffray et Zemir ont montré que la conjecture d'El Sahili et de Kouider est vraie pour d ≤ 6. En outre, la question a été résolue pour les graphes d-réguliers dans des conditions supplémentaires. Nous étudions la conjecture d'El Sahili et de Kouider en déterminant quand elle est possible et dans quelles conditions supplémentaires elle est vrai. Nous montrons que b(G) = d + 1 si G est un graphe d-régulier qui ne contient pas un cycle d'ordre 4 ni d'ordre 6. En outre, nous fournissons des conditions sur les sommets d'un graphe d-régulier G sans le cycle d'ordre 4 de sorte que b(G) = d + 1. Cabello et Jakovac ont prouvé si v(G) ≥ 2d3 - d2 + d, puis b(G) = d + 1, où G est un graphe d-régulier. Nous améliorons ce résultat en montrant que si v(G) ≥ 2d3 - 2d2 + 2d alors b(G) = d + 1 pour un graphe d-régulier G. 2. Emballage de graphe problème : Soit G un graphe d'ordre n. Considérer une permutation σ : V (G) → V (Kn), la fonction σ* : E(G) → E(Kn) telle que σ *(xy) = σ *(x) σ *(y) est la fonction induite par σ. Nous disons qu'il y a un emballage de k copies de G (dans le graphe complet Kn) s'il existe k permutations σi : V (G) → V (Kn), où i = 1, …, k, telles que σi*(E(G)) ∩ σj (E(G)) = ɸ pour i ≠ j. Un emballage de k copies d'un graphe G est appelé un k-placement de G. La puissance k d'un graphe G, noté par Gk, est un graphe avec le même ensemble de sommets que G et une arête entre deux sommets si et seulement si le distance entre ces deux sommets est au plus k. Kheddouci et al. ont prouvé que pour un arbre non-étoile T, il existe un 2-placement σ sur V (T). Nous introduisons pour la première fois le problème emballage marqué de graphe dans son graphe puissance

Two problems are considered in this thesis: the b-coloring problem and the graph packing problem. 1. The b-Coloring Problem : A b-coloring of a graph G is a proper coloring of the vertices of G such that there exists a vertex in each color class joined to at least a vertex in each other color class. The b-chromatic number of a graph G, denoted by b(G), is the maximum number t such that G admits a b-coloring with t colors. El Sahili and Kouider asked whether it is true that every d-regular graph G with girth at least 5 satisfies b(G) = d + 1. Blidia, Maffray and Zemir proved that the conjecture is true for d ≤ 6. Also, the question was solved for d-regular graphs with supplementary conditions. We study El Sahili and Kouider conjecture by determining when it is possible and under what supplementary conditions…

Advisors/Committee Members: Kheddouci, Hamamache (thesis director).

Subjects/Keywords: Coloration de graphe; B-coloration; Nombre b-chromatique; Graphe régulier; Emballage de graphe; Emballage marqué de graphe; Graphe puissance; Arbre non-étoile; Graph coloring; B-coloring; B-chromatic number; Regular graph; Graph packing; Labeled packing of graph; Power graph; Non-star tree; 004.0151

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Mortada, M. (2013). The b-chromatic number of regular graphs : Le nombre b-chromatique de graphe régulier. (Doctoral Dissertation). Université Claude Bernard – Lyon I. Retrieved from http://www.theses.fr/2013LYO10116

Chicago Manual of Style (16th Edition):

Mortada, Maidoun. “The b-chromatic number of regular graphs : Le nombre b-chromatique de graphe régulier.” 2013. Doctoral Dissertation, Université Claude Bernard – Lyon I. Accessed August 04, 2020. http://www.theses.fr/2013LYO10116.

MLA Handbook (7th Edition):

Mortada, Maidoun. “The b-chromatic number of regular graphs : Le nombre b-chromatique de graphe régulier.” 2013. Web. 04 Aug 2020.

Vancouver:

Mortada M. The b-chromatic number of regular graphs : Le nombre b-chromatique de graphe régulier. [Internet] [Doctoral dissertation]. Université Claude Bernard – Lyon I; 2013. [cited 2020 Aug 04]. Available from: http://www.theses.fr/2013LYO10116.

Council of Science Editors:

Mortada M. The b-chromatic number of regular graphs : Le nombre b-chromatique de graphe régulier. [Doctoral Dissertation]. Université Claude Bernard – Lyon I; 2013. Available from: http://www.theses.fr/2013LYO10116

2. Moustrou, Philippe. Geometric distance graphs, lattices and polytopes : Graphes métriques géométriques, réseaux et polytopes.

Degree: Docteur es, Mathématiques pures, 2017, Bordeaux

Un graphe métrique G(X;D) est un graphe dont l’ensemble des sommets est l’ensemble X des points d’un espace métrique (X; d), et dont les arêtes relient les paires fx; yg de sommets telles que d(x; y) 2 D. Dans cette thèse, nous considérons deux problèmes qui peuvent être interprétés comme des problèmes de graphes métriques dans Rn. Premièrement, nous nous intéressons au célèbre problème d’empilements de sphères, relié au graphe métrique G(Rn; ]0; 2r[) pour un rayon de sphère r donné. Récemment, Venkatesh a amélioré d’un facteur log log n la meilleure borne inférieure connue pour un empilement de sphères donné par un réseau, pour une suite infinie de dimensions n. Ici nous prouvons une version effective de ce résultat, dans le sens où l’on exhibe, pour la même suite de dimensions, des familles finies de réseaux qui contiennent un réseaux dont la densité atteint la borne de Venkatesh. Notre construction met en jeu des codes construits sur des corps cyclotomiques, relevés en réseaux grâce à un analogue de la Construction A. Nous prouvons aussi un résultat similaire pour des familles de réseaux symplectiques. Deuxièmement, nous considérons le graphe distance-unité G associé à une norme k_k. Le nombre m1 (Rn; k _ k) est défini comme le supremum des densités réalisées par les stables de G. Si la boule unité associée à k _ k pave Rn par translation, alors il est aisé de voir que m1 (Rn; k _ k) > 1 2n . C. Bachoc et S. Robins ont conjecturé qu’il y a égalité. On montre que cette conjecture est vraie pour n = 2 ainsi que pour des régions de Voronoï de plusieurs types de réseaux en dimension supérieure, ceci en se ramenant à la résolution de problèmes d’empilement dans des graphes discrets.

A distance graph G(X;D) is a graph whose set of vertices is the set of points X of a metric space (X; d), and whose edges connect the pairs fx; yg such that d(x; y) 2 D. In this thesis, we consider two problems that may be interpreted in terms of distance graphs in Rn. First, we study the famous sphere packing problem, in relation with thedistance graph G(Rn; (0; 2r)) for a given sphere radius r. Recently, Venkatesh improved the best known lower bound for lattice sphere packings by a factor log log n for infinitely many dimensions n. We prove an effective version of this result, in the sense that we exhibit, for the same set of dimensions, finite families of lattices containing a lattice reaching this bound. Our construction uses codes over cyclotomic fields, lifted to lattices via Construction A. We also prove a similar result for families of symplectic lattices. Second, we consider the unit distance graph G associated with a norm k _ k. The number m1 (Rn; k _ k) is defined as the supremum of the densities achieved by independent sets in G. If the unit ball corresponding with k _ k tiles Rn by translation, then it is easy to see that m1 (Rn; k _ k) > 1 2n . C. Bachoc and S. Robins conjectured that the equality always holds. We show that this conjecture is true for n = 2 and for several Voronoï cells of lattices in higher dimensions, by…

Advisors/Committee Members: Bachoc, Christine (thesis director), Pêcher, Arnaud (thesis director).

Subjects/Keywords: Graphes métriques; Réseaux Euclidiens; Empilement de sphères; Borne de Minkowski-Hlawka; Codes linéaires; Polytopes pavant l’espace par translation; Nombre chromatique; Distance graphs; Euclidean lattices; Sphere packing; Minkowski- Hlawka bound; Linear codes; Parallelohedra; Chromatic number

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Moustrou, P. (2017). Geometric distance graphs, lattices and polytopes : Graphes métriques géométriques, réseaux et polytopes. (Doctoral Dissertation). Bordeaux. Retrieved from http://www.theses.fr/2017BORD0802

Chicago Manual of Style (16th Edition):

Moustrou, Philippe. “Geometric distance graphs, lattices and polytopes : Graphes métriques géométriques, réseaux et polytopes.” 2017. Doctoral Dissertation, Bordeaux. Accessed August 04, 2020. http://www.theses.fr/2017BORD0802.

MLA Handbook (7th Edition):

Moustrou, Philippe. “Geometric distance graphs, lattices and polytopes : Graphes métriques géométriques, réseaux et polytopes.” 2017. Web. 04 Aug 2020.

Vancouver:

Moustrou P. Geometric distance graphs, lattices and polytopes : Graphes métriques géométriques, réseaux et polytopes. [Internet] [Doctoral dissertation]. Bordeaux; 2017. [cited 2020 Aug 04]. Available from: http://www.theses.fr/2017BORD0802.

Council of Science Editors:

Moustrou P. Geometric distance graphs, lattices and polytopes : Graphes métriques géométriques, réseaux et polytopes. [Doctoral Dissertation]. Bordeaux; 2017. Available from: http://www.theses.fr/2017BORD0802

3. Changiz Rezaei, Seyed Saeed. Entropy and Graphs.

Degree: 2014, University of Waterloo

The entropy of a graph is a functional depending both on the graph itself and on a probability distribution on its vertex set. This graph functional originated from the problem of source coding in information theory and was introduced by J. Körner in 1973. Although the notion of graph entropy has its roots in information theory, it was proved to be closely related to some classical and frequently studied graph theoretic concepts. For example, it provides an equivalent definition for a graph to be perfect and it can also be applied to obtain lower bounds in graph covering problems. In this thesis, we review and investigate three equivalent definitions of graph entropy and its basic properties. Minimum entropy colouring of a graph was proposed by N. Alon in 1996. We study minimum entropy colouring and its relation to graph entropy. We also discuss the relationship between the entropy and the fractional chromatic number of a graph which was already established in the literature. A graph G is called \emph{symmetric with respect to a functional FG(P)} defined on the set of all the probability distributions on its vertex set if the distribution P^* maximizing FG(P) is uniform on V(G). Using the combinatorial definition of the entropy of a graph in terms of its vertex packing polytope and the relationship between the graph entropy and fractional chromatic number, we prove that vertex transitive graphs are symmetric with respect to graph entropy. Furthermore, we show that a bipartite graph is symmetric with respect to graph entropy if and only if it has a perfect matching. As a generalization of this result, we characterize some classes of symmetric perfect graphs with respect to graph entropy. Finally, we prove that the line graph of every bridgeless cubic graph is symmetric with respect to graph entropy.

Subjects/Keywords: Entropy; Probability distribution; Graphs; Fractional Chromatic Number; Vertex packing polytope; Perfect Graphs; Line Graphs

…Entropy and Fractional Chromatic Number . . . . . . . . . . . . . . 28 3.7 Probability… …the the graph entropy and perfect graphs and fractional chromatic number of a graph. Chapter… …entropy of a graph with its fractional chromatic number in more detail. Furthermore, we obtain… …the fractional chromatic number of a vertex transitive graph using its properties along with… …chromatic number of F is denoted by χ(F ). Let T (n) = {U ⊆ V n : P n… 

Page 1 Page 2 Page 3 Page 4 Page 5 Page 6 Page 7

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Changiz Rezaei, S. S. (2014). Entropy and Graphs. (Thesis). University of Waterloo. Retrieved from http://hdl.handle.net/10012/8173

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16th Edition):

Changiz Rezaei, Seyed Saeed. “Entropy and Graphs.” 2014. Thesis, University of Waterloo. Accessed August 04, 2020. http://hdl.handle.net/10012/8173.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7th Edition):

Changiz Rezaei, Seyed Saeed. “Entropy and Graphs.” 2014. Web. 04 Aug 2020.

Vancouver:

Changiz Rezaei SS. Entropy and Graphs. [Internet] [Thesis]. University of Waterloo; 2014. [cited 2020 Aug 04]. Available from: http://hdl.handle.net/10012/8173.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Changiz Rezaei SS. Entropy and Graphs. [Thesis]. University of Waterloo; 2014. Available from: http://hdl.handle.net/10012/8173

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

.