The interplay between spectrum and structure of graphs is the recurring theme of the three more or less independent chapters of this thesis. The first chapter provides a method to relate the eigensolutions of two matrices, one being the principal submatrix of the other, via an arbitrary annihilating polynomial. This is extended to lambda-matrices and to matrices the entries of which are rational functions in one variable. The extension may be interpreted as a possible generalization of other known techniques which aim at reducing the size of a matrix while preserving the spectral information. Several aspects of an application in order to reduce the computational costs of ordinary eigenvalue problems are discussed. The second chapter considers the straightforward extension of the well known concept of equitable partitions to weighted graphs, i.e. complex matrices. It provides a method to divide the eigenproblem into smaller parts corresponding to the front divisor and its complementary factor in an easy and stable way with complexity which is only quadratic in matrix size. The exploitation of several equitable partitions ordered by refinement is discussed and a suggestion is made that preserves hermiticity if present. Some generalizations of equitable partitions are considered and a basic procedure for finding an equitable partition of complex matrices is given. The third chapter deals with isospectral and unitary equivalent graphs. It introduces a construction for unitary equivalent graphs which contains the well known GM-switching as a special case. It also considers an algebra of graph matrices generated by the adjacency matrix that corresponds to the 1-dimensional Weisfeiler-Lehman stabilizer in a way that mimics the correspondence of the coherent closure and the 2-dimensional Weisfeiler-Lehman stabilizer. The algebra contains the degree matrix, the (combinatorial, signless and normalized) Laplacian and the Seidel matrix. An easy construction produces graph pairs that are simultaneously unitary equivalent w.r.t. that algebra.

Aquest treball és una contribució a l'estudi de diferents problemes que sorgeixen de dues àrees fortament connexes de la Teoria de Grafs: etiquetaments i descomposicions. Molts etiquetaments de grafs deuen el seu origen als presentats l'any 1967 per Rosa. Un d'aquests etiquetaments, àmpliament conegut com a etiquetament graceful, va ser definit originalment com a eina per atacar la conjectura de Ringel, la qual diu que el graf complet d'ordre 2m+1 pot ser descompost en m copies d'un arbre donat de mida m. Aquí, estudiem etiquetaments relacionats que ens donen certes aproximacions a la conjectura de Ringel, així com també a una altra conjectura de Graham i Häggkvist que, en una forma dèbil, demana la descomposició d'un graf bipartit complet per un arbre donat de mida apropiada. Les principals contribucions que hem fet en aquest tema són la prova de la darrera conjectura per grafs bipartits complets del doble de mida essent descompostos per arbres de gran creixement i un nombre primer d'arestes, i la prova del fet que cada arbre és un subarbre gran de dos arbres pels quals les dues conjectures es compleixen respectivament. Aquests resultats estan principalment basats en una aplicació del mètode polinomial d'Alon. Un altre tipus d'etiquetaments, els etiquetaments magic, també són tractats aquí. Motivats per la noció de quadrats màgics de Teoria de Nombres, en aquest tipus d'etiquetaments volem asignar nombres enters a parts del graf (vèrtexs, arestes, o vèrtexs i arestes) de manera que la suma de les etiquetes assignades a certes subestructures del graf sigui constant. Desenvolupem tècniques basades en particions de certs conjunts d'enters amb algunes condicions additives per construir etiquetaments cycle-magic, un nou tipus d'etiquetament introduït en aquest treball i que estén la noció clàssica d'etiquetament magic. Els etiquetaments magic no donen cap descomposició de grafs, però les tècniques usades per obtenir-los estan al nucli d'un altre problema de descomposició, l'ascending subgraph decomposition (ASD). Alavi, Boals, Chartrand, Erdös i Oellerman, van conjecturar l'any 1987 que tot graf té un ASD. Aquí, estudiem l'ASD per grafs bipartits, una classe de grafs per la qual la conjectura encara no ha estat provada. Donem una condició necessària i una de suficient sobre la seqüència de graus d'un estable del graf bipartit de manera que admeti un ASD en que cada factor sigui un star forest. Les tècniques utilitzades estan basades en l'existència de branca-acoloriments en multigrafs bipartits. També tractem amb el sumset partition problem, motivat per la conjectura ASD, que demana una partició de [n] de manera que la suma dels elements de cada part sigui igual a un valor prescrit. Aquí donem la millor condició possible per la versió modular del problema que ens permet provar els millors resultats ja coneguts en el cas enter per n primer. La prova està de nou basada en el mètode polinomial. / This work is a contribution to the study of various problems that arise from two strongly connected areas of the Graph Theory: graph labelings and graph decompositions. Most graph labelings trace their origins to the ones presented in 1967 by Rosa. One of these labelings, widely known as the graceful labeling, originated as a means of attacking the conjecture of Ringel, which states that the complete graph of order 2m+1 can be decomposed into m copies of a given tree of size m. Here, we study related labelings that give some approaches to Ringel's conjecture, as well as to another conjecture by Graham and Häggkvist that, in a weak form, asks for the decomposition of a complete bipartite graph by a given tree of appropriate size. Our main contributions in this topic are the proof of the latter conjecture for double sized complete bipartite graphs being decomposed by trees with large growth and prime number of edges, and the proof of the fact that every tree is a large subtree of two trees for which both conjectures hold respectively. These results are mainly based on a novel application of the so-called polynomial method by Alon. Another kind of labelings, the magic labelings, are also treated. Motivated by the notion of magic squares in Number Theory, in these type of labelings we want to assign integers to the parts of a graph (vertices, edges, or vertices and edges) in such a way that the sums of the labels assigned to certain substructures of the graph remain constant. We develop techniques based on partitions of certain sets of integers with some additive conditions to construct cycle-magic labelings, a new brand introduced in this work that extends the classical magic labelings. Magic labelings do not provide any graph decomposition, but the techniques that we use to obtain them are the core of another decomposition problem, the ascending subgraph decomposition (ASD). In 1987, was conjectured by Alavi, Boals. Chartrand, Erdös and Oellerman that every graph has an ASD. Here, we study ASD of bipartite graphs, a class of graphs for which the conjecture has not been shown to hold. We give a necessary and a sufficient condition on the one sided degree sequence of a bipartite graph in order that it admits an ASD by star forests. Here the techniques are based on the existence of edge-colorings in bipartite multigraphs. Motivated by the ASD conjecture we also deal with the sumset partition problem, which asks for a partition of [n] in such a way that the sum of the elements of each part is equal to a prescribed value. We give a best possible condition for the modular version of the sumset partition problem that allows us to prove the best known results in the integer case for n a prime. The proof is again based on the polynomial method.

The minimum k-partition (MkP) problem is a well-known optimization problem encountered in various applications most notably in telecommunication and physics. Formulated in the early 1990s by Chopra and Rao, the MkP problem is the problem of partitioning the set of vertices of a graph into k disjoint subsets so as to minimize the total weight of the edges joining vertices in different partitions. In this thesis, we design and implement a branch-and-cut algorithm based on semidefinite programming (SBC) for the MkP problem. We describe and study the properties of two relaxations of the MkP problem, the linear programming and the semidefinite programming relaxations. We then derive a new strengthened relaxation based on semidefinite programming. This new relaxation provides tighter bounds compared to the other two discussed relaxations but suffers in term of computational time. We further devise an iterative clustering heuristic (ICH), a novel heuristic that finds feasible solution to the MkP problem and we compare it to the hyperplane rounding techniques of Goemans and Williamson and Frieze and Jerrum for k=2 and for k=3 respectively. Our computational results support the conclusion that ICH provides a better feasible solution for the MkP. Furthermore, unlike the hyperplane rounding, ICH remains very effective in the presence of negative edge weights. Next we describe in detail the design and implementation of a branch-and-cut algorithm based on semidefinite programming (SBC) to find optimal solution for the MkP problem. The ICH heuristic is used in our SBC algorithm to provide feasible solutions at each node of the branch-and-cut tree. Finally, we present computational results for the SBC algorithm on several classes of test instances with k=3, 5, and 7. Complete graphs with up to 60 vertices and sparse graphs with up to 100 vertices arising from a physics application were considered.

We obtain a tight upper bound for the genus of a partition, and calculate the number of partitions of maximal genus. The generating series for genus zero and genus one rooted hypermonopoles is obtained in closed form by specializing the genus series for hypermaps. We discuss the connection between partitions and rooted hypermonopoles, and suggest how a generating series for genus one partitions may be obtained via the generating series for genus one rooted hypermonopoles. An involution on the poset of genus one partitions is constructed from the associated hypermonopole diagrams, showing that the poset is rank-symmetric. Also, a symmetric chain decomposition is constructed for the poset of genus one partitions, which consequently shows that it is strongly Sperner.

The minimum k-partition (MkP) problem is a well-known optimization problem encountered in various applications most notably in telecommunication and physics. Formulated in the early 1990s by Chopra and Rao, the MkP problem is the problem of partitioning the set of vertices of a graph into k disjoint subsets so as to minimize the total weight of the edges joining vertices in different partitions. In this thesis, we design and implement a branch-and-cut algorithm based on semidefinite programming (SBC) for the MkP problem. We describe and study the properties of two relaxations of the MkP problem, the linear programming and the semidefinite programming relaxations. We then derive a new strengthened relaxation based on semidefinite programming. This new relaxation provides tighter bounds compared to the other two discussed relaxations but suffers in term of computational time. We further devise an iterative clustering heuristic (ICH), a novel heuristic that finds feasible solution to the MkP problem and we compare it to the hyperplane rounding techniques of Goemans and Williamson and Frieze and Jerrum for k=2 and for k=3 respectively. Our computational results support the conclusion that ICH provides a better feasible solution for the MkP. Furthermore, unlike the hyperplane rounding, ICH remains very effective in the presence of negative edge weights. Next we describe in detail the design and implementation of a branch-and-cut algorithm based on semidefinite programming (SBC) to find optimal solution for the MkP problem. The ICH heuristic is used in our SBC algorithm to provide feasible solutions at each node of the branch-and-cut tree. Finally, we present computational results for the SBC algorithm on several classes of test instances with k=3, 5, and 7. Complete graphs with up to 60 vertices and sparse graphs with up to 100 vertices arising from a physics application were considered.

We obtain a tight upper bound for the genus of a partition, and calculate the number of partitions of maximal genus. The generating series for genus zero and genus one rooted hypermonopoles is obtained in closed form by specializing the genus series for hypermaps. We discuss the connection between partitions and rooted hypermonopoles, and suggest how a generating series for genus one partitions may be obtained via the generating series for genus one rooted hypermonopoles. An involution on the poset of genus one partitions is constructed from the associated hypermonopole diagrams, showing that the poset is rank-symmetric. Also, a symmetric chain decomposition is constructed for the poset of genus one partitions, which consequently shows that it is strongly Sperner.

Water, suspended particle and sediment samples from Kao-ping estuary were collected and measured for concentrations of polycyclic aromatic hydrocarbons (PAHs) during March 2004 and April 2005. In addition, sediments from neighboring coastal area were also analyzed to estimate distribution, transportation and possible sources of PAHs. Total PAH concentrations varied from 33.0 to 910 ng/g dry weight (dw) in coastal sediments, and diagnostic ratios reflect a mixed sources of petrogenic and pyrolytic inputs. Due to the contribution of Kao-ping River, spatial distribution of PAH concentrations at coastal sediments near river mouth varied dramatically. Results of hierachical cluster analysis showed that PAH concentration distribution was influenced by Kao-ping canyon, and biogenic source might be the major PAH source for offshore sediments. Total PAH concentrations in river sediment varied from 63.0 to 720 ng/g dw. Higher concentration was measured between the Water Main pipe and Shuang-yuan Bridge, and possible sources were from both petrogenic and pyrolytic sources. Sediment of Dung-gang harbour had highest concentration, 28,000ng/g dw, in this study, which was contributed from petrogenic sources due to its intensive boating activities. Except fluorene and phenanthrene in harbour sediments, individual PAH concentrations of other sediments are lower or near the Effect Range Low value, concentrations might lead to possible adverse effects upon organism. Total PAH concentrations varied from 5.0 to 82.0 ng/L in suspended particulate phase and from 5.5ng/L to 46.0ng/L in dissolved phase, respectively. Most of high molecular weight PAH concentrations (>5-ring PAHs) in dissolved phase were below method detection limits. The partition coefficients¡]Koc¡^values of PAHs were 1 to 2 orders higher than predicted values. It might be attributed to soot particles which have extremely high sorption capacities. Correlation coefficients between total PAH concentrations in sediments versus total organic carbon¡]TOC¡^ and fine particle content¡]<63£gm%¡^were significant ¡]R=0.575, 0.800, 0.851 and 0.657, P<0.01¡^. In addition, PAHs in suspended particulate phase and dissolved phase were also significantly correlated to particulate organic carbon¡]POC¡^ and dissolved organic carbon¡]DOC¡^, respectively. The distribution of calculated PAH concentrations from organic carbon was higher in surface water than bottom water. Unlike salinity, there was no decreasing or increasing trend of these concentrations among river samples. It is possible that contamination was not come from upstream, but from estuary area where plume was lifted and diffused upstream by neat seawater. The flux in Wan-da Bridge was higher than downstream estuary area that might be due to PAH concentrations reduction by sedimentation or degradation.

This thesis aims comparative analysis of the state of the art shot boundary detection algorithms. The major methods that have been used for shot boundary detection such as pixel intensity based, histogram-based, edge-based, and motion vectors based, are implemented and analyzed. A recent method which utilizes &ldquo / graph partition model&rdquo / together with the support vector machine classifier as a shot boundary detection algorithm is also implemented and analyzed. Moreover, a novel graph theoretic concept, &ldquo / dominant sets&rdquo / , is also successfully applied to the shot boundary detection problem as a contribution to the solution domain.

Cette thèse est une contribution à l'étude combinatoire des groupes de Coxeter et des groupes d'Artin-Tits. Dans la première partie, nous complétons la description du groupe des automorphismes d'un groupe de Coxeter à angles droits en étudiant le second des deux sous-groupes qui apparaissent dans la décomposition en produit semi-direct établie par Tits (le premier est décrit par Mühlherr). Nous retrouvons ainsi le résultat de Radcliffe sur la rigidité des groupes de Coxeter à angles droits. Dans la deuxième partie, nous introduisons et étudions la notion de sous-monoïde d'un monoïde d'Artin-Tits induit par une partition admissible du graphe de Coxeter, au sens de Mühlherr. Nous montrons qu'un tel sous-monoïde est un monoïde d'Artin-Tits, et que cette notion généralise et unifie les situations des sous-monoïdes des points fixes d'un monoïde d'Artin-Tits sous l'action d'automorphismes du graphe, et des LCM-homomorphismes de Crisp et Godelle. Nous achevons la classification des partitions admissibles des graphes de Coxeter sphériques, commencée par Mühlherr ; elle nous fournit la classification des LCM-homomorphismes de Crisp. Dans la troisième partie, nous étudions la représentation de Krammer-Paris d'un monoïde d'Artin-Tits de type simplement lacé et sans triangle. Le sous-monoïde des points fixes d'un tel monoïde sous l'action d'un groupe d'automorphismes du graphe stabilise le sous-espace des points fixes de l'espace de la représentation sous l'action de ce groupe. Nous utilisons des notions développées par Hée pour prouver que la représentation ainsi obtenue est fidèle. Cela généralise, en évitant tout cas par cas, des résultats établis par Digne dans les cas sphériques.

Nous étudions certains processus de fragmentation qui sont liés à des processus de coalescence. Nous nous intéressons en premier lieu au coalescent de Bolthausen et Sznitman qui, retourné dans le temps, devient un processus de fragmentation inhomogène en temps. Nous décrivons alors sa mesure de dislocation instantanée en fonction de lois de Poisson-Dirichlet et en déduisons des asymptotiques sur la taille des blocs en temps grands et petits. Nous étudions aussi une classe de coalescents additifs après retournement de temps en tant que processus de fragmentation. Nous montrons alors que les lois de tous ces coalescents additifs sont absolument continues les unes par rapport aux autres et nous explicitons cette densité. Enfin, nous caractérisons la loi des fragmentations d'intervalle en la mettant en bijection avec les fragmentations de partitions ordonnées.